对一个合法的数学表达式来说,其中的各大小括号“{”,“}”,“[”,“]”,“(”和“)”应是相互匹配的。设计算法对以字符串形式读入的表达式S,判断其中的各括号是否是匹配的。请用C++代码编写
时间: 2023-08-27 08:03:45 浏览: 33
以下是使用栈实现的 C++ 代码:
```c++
#include <iostream>
#include <stack>
#include <string>
using namespace std;
bool isMatching(char a, char b) {
return (a == '(' && b == ')') || (a == '[' && b == ']') || (a == '{' && b == '}');
}
bool isBalanced(string s) {
stack<char> st;
for (char c : s) {
if (c == '(' || c == '[' || c == '{') {
st.push(c);
} else if (c == ')' || c == ']' || c == '}') {
if (st.empty() || !isMatching(st.top(), c)) {
return false;
}
st.pop();
}
}
return st.empty();
}
int main() {
string s;
cout << "请输入一个包含括号的表达式:" << endl;
cin >> s;
if (isBalanced(s)) {
cout << "括号匹配" << endl;
} else {
cout << "括号不匹配" << endl;
}
return 0;
}
```
该算法的时间复杂度为 $O(n)$,其中 $n$ 为字符串的长度。