输入一个算术表达式,其中包含两种括号:圆括号“()”和方括号“[]”,嵌套顺序任意,编写一个算法用于判别表达式中括弧是否能够正确匹配。用文字分析历程
时间: 2024-01-21 19:17:01 浏览: 143
算法分析:
1. 创建一个空的栈,用于存储左括号。
2. 从头到尾遍历表达式中的每个字符。
3. 如果当前字符是左括号(即圆括号或方括号),将其压入栈中。
4. 如果当前字符是右括号(即圆括号或方括号),则需要进行匹配:
a. 如果栈为空,说明没有左括号与之匹配,返回false。
b. 如果栈顶元素是相同类型的左括号,则将其弹出栈。
c. 如果栈顶元素不是相同类型的左括号,则说明括号不匹配,返回false。
5. 如果表达式遍历完毕后,栈不为空,则说明存在左括号没有被匹配到,返回false。
6. 如果表达式遍历完毕后,栈为空,则说明所有括号都匹配了,返回true。
代码实现:
```
bool isBracketsMatch(string s) {
stack<char> stk;
for (char c : s) {
if (c == '(' || c == '[') {
stk.push(c);
} else if (c == ')' || c == ']') {
if (stk.empty()) {
return false;
} else if ((c == ')' && stk.top() == '(') || (c == ']' && stk.top() == '[')) {
stk.pop();
} else {
return false;
}
}
}
return stk.empty();
}
```
注:以上代码仅供参考,可能存在语法错误或逻辑漏洞。