利用栈来检查简单括号的匹配

利用栈来检查简单括号的匹配，检查括号是否是正确匹配识别是很多语言的编译器的基础算法。

正确的括号：(()),(((())))

错误的括号：(())),()))),(()()(()

括号匹配识别原理

1. 从左到右扫描括号串，利用栈的先进后出（LIFO）原理，最新打开的左括号，那么匹配最先遇到的右括号。

2. 第一个左括号（最早打开），会匹配到最后一个右括号（最后遇到）

括号匹配识别计算流程

1. 生成一个空栈

2. 从字符串中从左到右依次取括号

1. 如果是左括号，加入到栈顶中，如果为空，检查栈是否为空，如果为空，匹配失败，如果是空，匹配成功。

2. 如果是右括号，检查栈是否为空，如果不为空，从栈顶中移除，如果为空，匹配失败。

3. de
   

python3 利用列表实现一个简单的栈

class?Stack():
????def?__init__(self):
????????self.items=[]

????#?判断栈是否为空
????def?isEmpty(self):
????????return?len(self.items)==0

????#?把数据放入栈
????def?push(self,item):
????????self.items.append(item)

????#?从栈中取数据
????def?pop(self):
????????return?self.items.pop()

????#?栈顶
????def?peek(self):
????????return?self.items[-1]

????#?栈的长度
????def?size(self):
????????return?len(self.items)
????????
????????

def?parChecker(symbol_string):
????s=Stack()
????index=0
????#?标识符
????mark=True
????
????#?循环遍历字符串
????while?index<len(symbol_string)?and?mark:
????????#?获取当前索引的符号
????????symbol=symbol_string[index]
????
????????#?如果符号等于右括号，则放入到栈中
????????if?symbol?=='(':
????????????s.push(symbol)
????????else:
????????????#?判断栈是否为空，如果为空，那么代表括号部队称
????????????if?s.isEmpty():
????????????????mark=False
????????????else:
????????????????s.pop()

????????index+=1

????#?如果标记为True和栈为空，则代表括号匹配完整
????if?mark?and?s.isEmpty():
????????return?True
????return?False
????
????
if?__name__?==?'__main__':

????print(parChecker('(())'))
????
????
????print(parChecker('((())'))

????print(parChecker('(()()()()()))'))

输出结果

True
False
False

上述程序只适用于()的匹配，而实际代码中常用的括号会有(){}[]<>。

优化版代码

class?Stack():
????def?__init__(self):
????????self.items=[]

????#?判断栈是否为空
????def?isEmpty(self):
????????return?len(self.items)==0

????#?把数据放入栈
????def?push(self,item):
????????self.items.append(item)

????#?从栈中取数据
????def?pop(self):
????????return?self.items.pop()

????#?栈顶
????def?peek(self):
????????return?self.items[-1]

????#?栈的长度
????def?size(self):
????????return?len(self.items)


opens='([{<'
closers=')]}>'

def?parChecker(symbol_string):
????s=Stack()
????index=0
????#?标识符
????mark=True

????#?循环遍历字符串
????while?index<len(symbol_string)?and?mark:
????????#?获取当前索引的符号
????????symbol=symbol_string[index]

????????#?如果符号等于右括号，则放入到栈中
????????if?symbol?in?opens:
????????????s.push(symbol)
????????else:
????????????#?判断栈是否为空，如果为空，那么代表括号部队称
????????????if?s.isEmpty():
????????????????mark=False
????????????else:
????????????????top=s.pop()
????????????????if?not?match(top,symbol):
????????????????????mark=False
????????index+=1

????#?如果标记为True和栈为空，则代表括号匹配完整
????if?mark?and?s.isEmpty():
????????return?True
????return?False

def?match(open,close):
????return?opens.index(open)?==closers.index(close)


if?__name__?==?'__main__':

????print(parChecker('{{([])}}'))

????print(parChecker('[{<>}]'))

????print(parChecker('{()[]}'))
????
????print(parChecker('[{]}'))

输出结果：

True
True
True
False

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!