UU Blog

Python用栈实现匹配括号对语法是否正确

要实现对括号对的匹配。

假如不能双双配对,就是不合适的。举个例子

1
2
3
4
5
6
正确
'sd{sfsfs}[(s)]'
'[{()}]'

不正确
'[[]{()}'

思路就是用一个栈存储匹配到的左括号,匹配到右括号的话,就和栈顶的数据对比。因为两个括号的ASCII码,一般右括号总比左括号大1或者2.通过判断差值是否在这个区间,基本可以确定。匹配到一对括号,便消除一个。到最后如果栈为空,就是合格的。反之,不为空就是不合格的。

实现代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#!/usr/bin/python
#coding:utf-8

leftChar=['{','[','(']
rightChar=['}',']',')']

def check_format(sPath):
s=[]
for x in sPath:
if x in leftChar:
s.append(x)
if x in rightChar:
if s:
if abs(ord(x)-ord(s[-1]))<=2:
s.pop()
else:
s.append(x)
else:
s.append(x)
if s:
print u"不合格"
else:
print u"合格"

结果如下

1
2
3
4
check_format('sd{sfsfs}[(s)]')
合格
check_format('[[]{()}')
不合格
给作者打一针鸡血