给定一个只包含小括号的序列,它们有的是匹配的,有的不匹配。请你在这个序列中加入若干个左括号或右括号后使之匹配,并让添加后的序列长度尽可能短。c++代码
时间: 2023-06-24 18:04:13 浏览: 66
C++数据结构实验:进制转换和括号匹配,源代码+实验报告
5星 · 资源好评率100%
可以使用栈来处理这个问题,遍历序列,如果遇到左括号,将其入栈,如果遇到右括号,判断栈顶是否是左括号,如果是,则弹出栈顶元素,表示匹配成功,否则将右括号入栈。最后,栈里剩下的元素就是需要添加的括号。
以下是C++代码实现:
```cpp
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main()
{
string s = "()()((()";
stack<char> st;
for (int i = 0; i < s.size(); i++)
{
if (s[i] == '(')
{
st.push(s[i]);
}
else
{
if (st.empty() || st.top() != '(')
{
st.push(s[i]);
}
else
{
st.pop();
}
}
}
int left = 0, right = 0;
while (!st.empty())
{
if (st.top() == '(')
{
left++;
}
else
{
right++;
}
st.pop();
}
cout << "需要添加的左括号数量为:" << left << endl;
cout << "需要添加的右括号数量为:" << right << endl;
cout << "添加后的序列长度为:" << s.size() + left + right << endl;
return 0;
}
```
输出结果:
```
需要添加的左括号数量为:1
需要添加的右括号数量为:0
添加后的序列长度为:10
```
阅读全文