Question

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

一个算数表达式含有三种类型的括弧，且需含有一个correct（exp，tag）的函数判断括弧是否配对，exp为字符串类型变量，tag为布尔型的，急需一个完整的算法

Answer 1

算法如下：

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

追问

可是代码怎么实现呀？热心的亲们^o^

追答

你是要算法还是要程序啊？

追问

芙芙，那还是完整的程序吧，迫切需要，灰常感谢^o^善良的人粒

追答

对不起,我无能为力.

追问

好吧，同样感谢你

Answer 2

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( );
}