PTA数据结构,本题要求根据一个由(,),{,},[,],构成的以#结束的序列,通过栈来判断括号匹配问题,如果匹配输出yes!,否则输出no!
时间: 2024-05-14 20:18:46 浏览: 24
用栈判断括号是否匹配
这道题可以用栈来解决。遍历输入序列,如果遇到左括号(即 (、{、[),则将其压入栈中;如果遇到右括号(即 )、}、]),则将栈顶元素出栈并与该右括号进行匹配,如果匹配成功则继续遍历,否则输出no并结束程序。
以下是示例代码:
```c++
#include <iostream>
#include <stack>
using namespace std;
int main() {
string s;
cin >> s;
stack<char> st;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(' || s[i] == '{' || s[i] == '[') {
st.push(s[i]);
} else if (!st.empty()) {
char c = st.top();
if ((c == '(' && s[i] == ')') || (c == '{' && s[i] == '}') || (c == '[' && s[i] == ']')) {
st.pop();
} else {
cout << "no!";
return 0;
}
} else {
cout << "no!";
return 0;
}
}
if (st.empty()) {
cout << "yes!";
} else {
cout << "no!";
}
return 0;
}
```
注意在遍历完整个序列后还需要判断栈是否为空,如果不为空则说明还有未匹配的左括号,输出no。
阅读全文