氧气少年有一个长度为 n的括号序列,括号序列只包含 ‘(’‘)' 。 一个括号序列是合法的,当且仅当此括号序列可以通过插入加号 ‘+' 和数字1得到一个正确的算术表达式。括号序列“(())()”,“()”,和“(()(()))”都是合法的,而“)(”,“(()”和“(()))(”不是合法的 为了把这个输入的括号序列变合法,月色哥哥每次可以进行交换任意两个相邻括号。 如果无论月色哥哥怎么操作都无法使括号序列变合法,就输出−1;否则请输出他需要做的最少的操作次数。(c++)
时间: 2024-04-16 14:25:35 浏览: 135
您好!对于这个问题,我们可以使用栈来判断括号序列的合法性,并计算需要进行的最少操作次数。具体的C++代码如下:
```cpp
#include <iostream>
#include <stack>
int minOperations(std::string s) {
int n = s.length();
std::stack<char> st;
int count = 0;
for (int i = 0; i < n; i++) {
if (s[i] == '(') {
st.push(s[i]);
} else {
if (!st.empty()) {
st.pop();
} else {
count++;
}
}
}
// 需要将剩余的左括号变成右括号
count += st.size();
return (count % 2 == 0) ? count / 2 : -1;
}
int main() {
std::string s;
std::cin >> s;
int result = minOperations(s);
std::cout << result << std::endl;
return 0;
}
```
在这段代码中,我们使用了一个栈来模拟括号匹配过程。遍历输入的括号序列,如果遇到左括号,则将其入栈;如果遇到右括号,则检查栈顶是否是左括号,如果是,则将栈顶元素出栈,表示匹配成功;如果栈为空,表示无法匹配,则需要进行一次操作,并继续遍历;最后,需要将剩余的左括号变成右括号,每两个左括号需要一次操作。如果最终操作次数为偶数,则返回操作次数除以2,否则返回-1表示无法使括号序列变合法。
希望能解答您的问题!如果还有其他问题,请随时提问。
阅读全文