判断中缀表达式中的圆括号是否正确(isMatch成员函数)
时间: 2024-11-24 15:40:10 浏览: 4
在C++中,判断中缀表达式的圆括号是否匹配是一个经典的回溯问题,可以通过栈数据结构来实现。我们可以定义一个`isMatch`函数,它接受一个表示中缀表达式的字符串,并检查其中的左括号和右括号是否一一对应并且按照正确的顺序出现。这里的关键在于维护两个栈:一个用于存储左括号,另一个用于检查当前括号是否匹配。
以下是一个简单的示例实现:
```cpp
#include <stack>
bool isMatch(const std::string &s) {
stack<char> leftBrackets, current;
for (char c : s) {
if (c == '(') { // 遇到左括号,入栈
leftBrackets.push(c);
} else if (c == ')') { // 遇到右括号
if (leftBrackets.empty()) return false; // 如果没有对应的左括号,返回false
char left = leftBrackets.top(); // 获取最近的左括号
leftBrackets.pop();
if (left != '(') return false; // 检查是否是配对的括号
} else { // 非括号字符,直接无视
continue;
}
}
// 所有括号都检查过,如果左括号栈非空,则剩余未配对
return leftBrackets.empty();
}
```
这个函数的工作原理是遍历输入的字符串,每当遇到左括号就压入左括号栈,遇到右括号时检查是否有匹配的左括号。如果没有,或者当前不是左括号,就说明括号不匹配,返回`false`。遍历结束后,如果左括号栈为空,说明所有括号都已正确匹配,返回`true`;否则返回`false`。
阅读全文