设计一个算法,判断一个可能含有花括号、中括号、和圆括号的表达式中各类括号是否匹配,若匹配,则返回1;否则返回0。表中表达式只包含三种括号,花括号{}、中括号[]、圆括号(),即它仅由 (、)、[、]、{、}六个字符组成。
时间: 2023-05-21 10:06:06 浏览: 81
以下是判断表达式中各类括号是否匹配的算法:
1. 初始化一个空栈 Stack
2. 从左到右扫描表达式中的每一个字符 ch
a. 如果 ch 是左括号 (、[、{,则将 ch 压入栈 Stack 中
b. 如果 ch 是右括号 )、]、},则取出栈顶元素 top,判断 top 和 ch 是否匹配
i. 如果匹配,继续扫描表达式;
ii. 如果不匹配,返回0,表示括号不匹配
3. 扫描完表达式之后,若栈为空,则返回1,否则返回0,表示括号不匹配
以下是算法的实现代码(使用C++):
bool isMatched(string expression) {
stack<char> s;
for (int i = 0; i < expression.length(); i++) {
char ch = expression[i];
if (ch == '(' || ch == '[' || ch == '{') {
s.push(ch);
} else if (ch == ')' || ch == ']' || ch == '}') {
if (s.empty()) {
return false;
}
char top = s.top();
s.pop();
if ((ch == ')' && top != '(') ||
(ch == ']' && top != '[') ||
(ch == '}' && top != '{')) {
return false;
}
}
}
return s.empty();
}
调用 isMatched 函数时,传入一个表达式字符串,例如:“[(1+2)*3-{5/2}]”,函数将返回true,表明表达式中的括号是匹配的。如果传入的表达式字符串中存在不匹配的括号,例如:“[{(1+2)*3}-{5/2)]”,函数将返回false。
阅读全文