假设表达式中允许包含3种括号:圆括号、方括号和大括号。即(,[,'{'。编写一个算法判断表达式中的括号是否正确配对, 要求利用栈的结构实现。 ###输入要求 输入一行带上述括号字符串 ###输出要求 若匹配,输出yes。若不匹配,输出当前栈顶元素再换行输出no,并。若栈顶为空,则输出no。 实现该程序的c++代码
时间: 2023-05-18 18:02:33 浏览: 101
可以使用栈来判断表达式中的括号是否正确配对。具体步骤如下:
1. 创建一个空栈。
2. 从左到右遍历表达式中的每个字符。
3. 如果当前字符是左括号(即圆括号、方括号或大括号),则将其入栈。
4. 如果当前字符是右括号,则判断栈顶元素是否与之匹配。如果匹配,则将栈顶元素出栈;否则,表达式中的括号不正确配对,直接返回 false。
5. 遍历完表达式中的所有字符后,如果栈为空,则表达式中的括号正确配对;否则,表达式中的括号不正确配对,返回 false。
下面是具体的实现代码:
```
bool isParenthesesMatch(string s) {
stack<char> st;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
st.push(s[i]);
} else if (s[i] == ')') {
if (st.empty() || st.top() != '(') {
return false;
}
st.pop();
} else if (s[i] == ']') {
if (st.empty() || st.top() != '[') {
return false;
}
st.pop();
} else if (s[i] == '}') {
if (st.empty() || st.top() != '{') {
return false;
}
st.pop();
}
}
return st.empty();
}
```
该算法的时间复杂度为 O(n),其中 n 是表达式中字符的个数。
阅读全文