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

Posted on Edited on In

要实现对括号对的匹配。

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

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('[[]{()}')
不合格

关注公众号 尹安灿