判断栈中str中的括号是否匹

- 日理万妓 2024-03-08 09:07 60阅读 0赞

**1** **问题**

在数据结构中如何判断栈中str中的括号是否匹配？

**2** **方法**

解题思路：

1建立一个顺序栈

2给定一个字符串

3一个字符串一个字符串的处理

4给定一个字符，怎么处理它  
5如果这个字符串是左字符串，进栈;  
6如果这个字符串是右括号，按照下面进行处理：  
7如果栈为空，则不匹配，程序结束；  
8出栈一个元素，记为y;  
9如果x和y匹配，则继续；  
10如果x和y不匹配，则当前字符串不匹配，程序结束；  
11如果这个字符串x不是左右括号，则不匹配，程序结束  
12当所有字符串都处理完成后，如果栈内还有元素，则不匹配，程序结束：

代码清单 1

<table> 
 <tbody> 
 <tr> 
 <td>From SqStack import SqStack #引用顺序栈SqStack Def ismatch(str): #判断表达式的各种括号是否匹配的算法 St=SqStack() #建立一个顺序栈 i=0 While i&lt;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 ([])方括号是匹配的</td> 
 </tr> 
 <tr> 
 <td></td> 
 </tr> 
 </tbody> 
</table>

**3** **结语**

在各种括号的匹配过程中遵循着这样的原则，如何一个右括号与前面最靠近的未匹配的同类左括号进行匹配，所以采用一个栈来实现匹配过程。

用str字符串存放含有各种括号的表达式，建立一个字符串顺序栈st,用i遍历str,当遇到各种类型的左括号时进栈，当遇到右括号时，若栈空或栈顶元素不是匹配的左括号时返回False(中途就知道括号不匹配)，当str遍历完毕，栈st为空返回True,否则返回False。