假设算术表达式中允许包含两种括号:圆括号和方括号,其嵌套的顺序随意,即([][]) 或[([]())]等为正确格式,而[(]或()))或 [())均为不正确的格式。请使用栈结构,写一算法检验某表达式中的括号是否匹配
时间: 2024-01-10 17:02:03 浏览: 120
方括号下载:下载方括号(正在下降)
1. 初始化一个空栈
2. 从左到右遍历表达式的每个字符,如果是左括号(圆括号或方括号),则将其压入栈中
3. 如果是右括号,则判断栈是否为空,如果为空,说明没有左括号与之匹配,返回false;如果栈不为空,则取出栈顶元素,判断是否与当前右括号匹配,如果不匹配,返回false;如果匹配,则继续遍历表达式。
4. 当遍历完整个表达式后,如果栈为空,则说明所有左括号都有与之匹配的右括号,返回true;否则,说明还有左括号没有匹配的右括号,返回false。
代码如下:
```
bool checkBrackets(string exp) {
stack<char> s;
for (int i = 0; i < exp.size(); i++) {
if (exp[i] == '(' || exp[i] == '[') {
s.push(exp[i]);
} else if (exp[i] == ')' || exp[i] == ']') {
if (s.empty()) {
return false;
}
char top = s.top();
s.pop();
if ((exp[i] == ')' && top != '(') || (exp[i] == ']' && top != '[')) {
return false;
}
}
}
return s.empty();
}
```
阅读全文