简单的括号匹配

发表于   |   分类于

栈的应用其一：括号匹配

处理逻辑

未考虑引号和注释中的括号情况

  • 顺序扫描正文字符串，跳过无关字符
  • 遇到开括号(,[,{则入栈
  • 遇到闭括号),],}则弹出栈顶元素与之匹配
  • 匹配成功则继续，否则失败结束

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#!/usr/bin/env python
#_*_ coding:utf-8 _*_
from stack_ import *
def checkParens(text):
    '''括号配对检查函数，text为被检查的正文串'''
    parens = '()[]{}'
    openParens = '([{'
    opposite = {')':'(',']':'[','}':'{'}        #配对关系的字典
    def parenstheses(text):
        i,textLen = 0,len(text)
        while True:
            while i < textLen and text[i] not in parens:
                i += 1
            if i >= textLen:
                return
            yield text[i],i
            i += 1
    st = SStack()                       #保存括号的栈
    for pr,i in parenstheses(text):     #对text里各括号和位置迭代
        if pr in openParens:            #开括号压栈
            st.push(pr)
        elif st.pop() != opposite[pr]:  #不匹配退出
            print 'Unmatching is found at',i,'for',pr
        else:
            pass
    print 'All parentheses are correctly matched.'
    return True
  • 程序出自 《数据结构与算法Python语言描述》