用栈判断是否匹配

╰+哭是因爲堅強的太久メ 2024-03-23 20:11 41阅读 0赞

**1** **问题**

写代码的时候用到的括号都是成双成对的出现，并且大小也相同。在集成编辑环境中，IDE就会为我们自己动检查括号是否匹配。那么为了避免在报错，如何判断是否有无括号不匹配？

**2** **方法**

**![6da6237b26dcd1ba017ebbccfe6af734.png][]**利用栈来实现这种功能。当遇见一个左括号，就表示入栈，遇见一个右括号就表示出栈。出栈后的左括号，与刚遇见的右括号进行匹配，如类型相同则匹配成功，反之则报错。

代码清单 1

<table> 
 <tbody> 
 <tr> 
 <td>class SqStack: &nbsp; &nbsp;def __init__(self): &nbsp; &nbsp; &nbsp; &nbsp;self.data = [] &nbsp; &nbsp;def empty(self): &nbsp; &nbsp; &nbsp; &nbsp;if len(self.data) == 0: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;return True &nbsp; &nbsp; &nbsp; &nbsp;return False &nbsp; &nbsp;def push(self,e): &nbsp; &nbsp; &nbsp; &nbsp;self.data.append(e) &nbsp; &nbsp;def pop(self): &nbsp; &nbsp; &nbsp; &nbsp;assert not self.empty() &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;return self.data.pop() &nbsp; &nbsp;def gettop(self): &nbsp; &nbsp; &nbsp; &nbsp;assert not self.empty() &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;return self.data[-1] stack = SqStack() def isMatch(str): &nbsp; &nbsp;st = SqStack() &nbsp; &nbsp;i = 0 &nbsp; &nbsp;while i &lt;len(str): &nbsp; &nbsp; &nbsp; &nbsp;e = str[i] &nbsp; &nbsp; &nbsp; &nbsp;if e =='(' or e =='[' or e == '{': &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;st.push(e) &nbsp; &nbsp; &nbsp; &nbsp;else: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;if e == ')': &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;if st.empty() or st.gettop()!='(': &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;return False &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;st.pop() &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;if e == ']': &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;if st.empty() or st.gettop()!='[': &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;return False &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;st.pop() &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;if e == '}': &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;if st.empty() or st.gettop()!='{': &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;return False &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;st.pop() &nbsp; &nbsp; &nbsp; &nbsp;i+=1 &nbsp; &nbsp;return st.empty() str=input('请输入：') if isMatch(str): &nbsp; &nbsp;print('True') else: &nbsp; &nbsp;print('False')</td> 
 </tr> 
 </tbody> 
</table>

**3** **结语**

针对用栈来判断括号是否匹配的问题，提出栈的基本用法的方法，通过运用进栈方法、出栈方法、判断栈是否为空方法以及遍历方法实验，证明该方法是有效的，但本文的方法较复杂，内容较多。未来可以在此基础上优化判断是否匹配方法。

[6da6237b26dcd1ba017ebbccfe6af734.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/5e06e108a9ee4cbf943dbc899f565e53.png