1 问题
在数据结构中如何判断栈中str中的括号是否匹配？
2 方法
解题思路：
1建立一个顺序栈
2给定一个字符串
3一个字符串一个字符串的处理
4给定一个字符，怎么处理它 5如果这个字符串是左字符串，进栈; 6如果这个字符串是右括号，按照下面进行处理： 7如果栈为空，则不匹配，程序结束； 8出栈一个元素，记为y; 9如果x和y匹配，则继续； 10如果x和y不匹配，则当前字符串不匹配，程序结束； 11如果这个字符串x不是左右括号，则不匹配，程序结束 12当所有字符串都处理完成后，如果栈内还有元素，则不匹配，程序结束：
代码清单 1
代码语言：javascript复制From SqStack import SqStack #引用顺序栈SqStack
Def ismatch(str): #判断表达式的各种括号是否匹配的算法
St=SqStack() #建立一个顺序栈
i=0
While i<len(str):
e=str[i]
if e==’(’or e==’[’or e==’{’:
St.push(e) #将左括号进栈
else:
If e==’)’:
If st.empty()or st.gettop()!=’(’:
Return False #栈空或者栈顶不是’(’时返回假
St.pop()
If e==’]’:
If st.empty()or st.gettop()!=’[’:
Return False #栈空或者栈顶不是’(’时返回假
St.pop()
If e==’}’:
If st.empty()or st.gettop()!=’{’:
Return false #栈空或者栈顶不是’(’时返回假
St.pop()
I =1 #继续遍历str
Return st.empty()
#主程序
Print(“测试 1”)
Str=”([)]”
If ismatch(str):
Print(str ”方括号匹配”)
Else:
Print(str ”方括号不匹配”)
Print(“测试2”)
Str=”([])”
If ismatch(str):
Print(str ”方括号匹配”)
Else:
Print(str ”方括号不匹配”)
上述程序的执行结果如下：
测试1
([)]方括号不匹配
测试2
([])方括号是匹配的3 结语
在各种括号的匹配过程中遵循着这样的原则，如何一个右括号与前面最靠近的未匹配的同类左括号进行匹配，所以采用一个栈来实现匹配过程。
用str字符串存放含有各种括号的表达式，建立一个字符串顺序栈st,用i遍历str,当遇到各种类型的左括号时进栈，当遇到右括号时，若栈空或栈顶元素不是匹配的左括号时返回False(中途就知道括号不匹配)，当str遍历完毕，栈st为空返回True,否则返回False。
