数据结构栈应用括号匹配算法

发布网友发布时间：2022-05-24 05:29

共2个回答

热心网友时间：2024-11-04 10:04

算法如下：

从左开始向右扫描该表达式，
1、如遇左括号（不论哪一种），将该左括号入栈；
2、如是右括号，如栈为空则返回出错信息，不空就检查其是否与栈顶左括号是否配对，如是则栈顶元素出栈后继续扫描（转1 ），否则，返回出错信息（出错类型：右括号先出现，或左右括号不匹配，出错位置）；
3、如是其它字符，直接跳过，继续扫描，如表达式未完则转1；表达式结束转4。
4、如栈空，显示“匹配正确！”，否则显示“缺失右括号！”。

热心网友时间：2024-11-04 10:04

bool correct(char *str) {
Stack<char> s;
int n = strlen(str);
for(int i = 0; i < n; i++) {
switch(str[i]) {
case '(': ;
case '[': ;
case '{': s.Push(str[i]); break;
case ')': if(s.IsEmpty( ) || s.Pop( ) != '(') return false; break;
case ']': if(s.IsEmpty( ) || s.Pop( ) != '[') return false; break;
case '}': if(s.IsEmpty( ) || s.Pop( ) != '{') return false;
}
}
return s.IsEmpty( );
}