假设一个算术表达式中包含圆括号、方括号、花括号这三种类型的括号,编写一个算法判断表达式中的括号是否配对。
时间: 2024-05-14 14:12:35 浏览: 31
可以使用栈来解决这个问题,遍历表达式,当遇到左括号时,将其压入栈中,当遇到右括号时,从栈中弹出一个左括号进行匹配,如果匹配成功则继续遍历,否则返回false。最后如果栈为空,则说明所有括号都匹配成功,返回true,否则返回false。
具体实现如下:
```
bool isMatched(string expression) {
stack<char> s;
for (char c : expression) {
if (c == '(' || c == '[' || c == '{') {
s.push(c);
} else if (c == ')') {
if (s.empty() || s.top() != '(') {
return false;
}
s.pop();
} else if (c == ']') {
if (s.empty() || s.top() != '[') {
return false;
}
s.pop();
} else if (c == '}') {
if (s.empty() || s.top() != '{') {
return false;
}
s.pop();
}
}
return s.empty();
}
```
该算法的时间复杂度为O(n),其中n为表达式的长度,空间复杂度为O(n)。
阅读全文