设计一个算法判断输入的表达式中左右圆括号是否配对,如果匹配,返回ture,否则返回false,并对重要步骤进行说明
时间: 2023-04-01 07:02:32 浏览: 133
可以使用栈来实现判断左右圆括号是否配对的算法,具体步骤如下:
1. 遍历输入的表达式,如果遇到左圆括号,将其入栈;如果遇到右圆括号,判断栈是否为空,如果为空则说明右圆括号没有匹配的左圆括号,返回false;如果栈不为空,则将栈顶元素出栈。
2. 遍历完表达式后,如果栈为空,则说明左右圆括号全部匹配,返回true;否则返回false。
重要步骤说明:
1. 入栈操作:将左圆括号入栈,可以使用栈的push()方法实现。
2. 出栈操作:将栈顶元素出栈,可以使用栈的pop()方法实现。
3. 判断栈是否为空:可以使用栈的empty()方法实现。
4. 判断左右圆括号是否匹配:如果遇到右圆括号时,栈为空,则说明没有匹配的左圆括号;如果栈不为空,则将栈顶元素出栈,表示匹配成功。
完整代码如下:
#include <iostream>
#include <stack>
using namespace std;
bool isMatch(string s) {
stack<char> st;
for (int i = ; i < s.size(); i++) {
if (s[i] == '(') {
st.push(s[i]);
} else if (s[i] == ')') {
if (st.empty()) {
return false;
} else {
st.pop();
}
}
}
return st.empty();
}
int main() {
string s = "((()))";
bool res = isMatch(s);
cout << res << endl;
return ;
}
阅读全文