输入一串括号包含以下括号种类:(、)、[、]、{、}。试利用顺序栈或链栈检查输入括号序列的匹配情况;
时间: 2023-10-30 08:37:17 浏览: 46
算法思路:
1. 初始化一个空的栈。
2. 从左到右扫描输入串中的每一个字符。
3. 若当前字符是左括号(即“(”、“[”、“{”),则将其压入栈中。
4. 若当前字符是右括号(即“)”、“]”、“}”),则从栈顶取出一个左括号。若取出的左括号与当前右括号不匹配,则输入串中的括号不匹配。
5. 若扫描完所有字符后,栈为空,则输入串中的括号匹配;否则,输入串中的括号不匹配。
代码实现:
C++ 代码:
#include <iostream>
#include <stack>
#include <string>
using namespace std;
bool isMatch(char c1, char c2) {
return (c1 == '(' && c2 == ')') || (c1 == '[' && c2 == ']') || (c1 == '{' && c2 == '}');
}
bool check(string s) {
stack<char> st;
for (int i = 0; i < s.length(); i++) {
if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
st.push(s[i]);
} else if (s[i] == ')' || s[i] == ']' || s[i] == '}') {
if (st.empty() || !isMatch(st.top(), s[i])) {
return false;
}
st.pop();
}
}
return st.empty();
}
int main() {
string s;
cout << "请输入一串包含括号的字符串:" << endl;
cin >> s;
if (check(s)) {
cout << "输入的括号序列是匹配的。" << endl;
} else {
cout << "输入的括号序列不匹配。" << endl;
}
return 0;
}