定义如下规则: 空串是「平衡括号序列」 若字符串 � S 是「平衡括号序列」,那么 [ � ] [S] 和 ( � ) (S) 也都是「平衡括号序列」 若字符串 � A 和 � B 都是「平衡括号序列」,那么 � � AB(两字符串拼接起来)也是「平衡括号序列」。用c++写
时间: 2023-06-14 13:05:57 浏览: 152
以下是用 C++ 实现平衡括号序列的代码:
```c++
#include <iostream>
#include <stack>
#include <string>
using namespace std;
bool isBalanced(string s) {
stack<char> st;
for (char c : s) {
if (c == '(' || c == '[') {
st.push(c); // 左括号入栈
} else if (c == ')') {
if (st.empty() || st.top() != '(') {
return false; // 栈为空或栈顶不是对应的左括号
}
st.pop(); // 匹配成功,弹出栈顶元素
} else if (c == ']') {
if (st.empty() || st.top() != '[') {
return false; // 栈为空或栈顶不是对应的左括号
}
st.pop(); // 匹配成功,弹出栈顶元素
}
}
return st.empty(); // 栈为空说明所有括号都匹配成功
}
int main() {
string s;
cin >> s;
if (isBalanced(s)) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
return 0;
}
```
这个程序中,首先定义了一个 `isBalanced` 函数,用于判断给定的字符串是否为平衡括号序列。在函数中,使用了一个栈来存储左括号,遇到右括号时就与栈顶元素进行匹配。如果匹配成功,就将栈顶元素弹出。如果最后栈为空,说明所有括号都匹配成功,函数返回 `true`,否则返回 `false`。
在 `main` 函数中,首先读入一个字符串,然后调用 `isBalanced` 函数进行判断。如果是平衡括号序列,就输出 `YES`,否则输出 `NO`。
阅读全文