括号与算法的关系
我们都写过这样的表达式: ( 5 + 6 ) * ( 7 + 8 ) / ( 4 + 3 )
这里的括号是用来指定表达式项的计算优先级
但括号的使用必须遵循 "平衡" 规则
首先, 每个开阔号要恰好对应一个闭括号~
其次,每对开阔号要正确的嵌套~
正确的括号: ( ( ) ( ) ( ) ( ) ), ( ( ( ( ) ) ) ), ( ( ) ( ( ( ) ) ( ) ) )
错误的括号: ( ( ( ( ( ( ( ) ), ( ) ) ), ( ( ) ( ) ( ( )
对括号的正确匹配和识别,是很多语言编译器的基础算法
如何构造括号匹配识别算法
从左到右扫描括号串,最新打开的左括号,应和最先遇到的右括号匹配
这样,第一个左括号(最早打开),就应该匹配最后一个右括号(最后遇到)
这种次序反转的识别,正好符合栈的特性!
class Stack:#Stack---->ADT def __init__(self): self.items =[] def isEmpty(self): return self.items == [] # 满足这些属性(行为)的是栈 def push(self,item): self.items.append(item) def pop(self): return self.items.pop() def peek(self): return self.items[len(self.items)-1] # def size(self): return len(self.items) def parChecker(symbolstring): print(symbolstring) #实例化栈(空栈) s = Stack() #括号匹配法则 balanced = True index = 0 while index < len(symbolstring) and balanced: symbol = symbolstring[index] if symbol == "(": s.push(symbol) else: #右括号多了或左括号少了 if s.isEmpty():#判断栈 是否为空 balanced = False else: s.pop() index = index + 1 if balanced and s.isEmpty(): return True else: return False result = parChecker("(())") print(result) print(parChecker("(()"))
运行结果:
如何构造各类型括号匹配识别算法
在实际的应用里,我们会碰到更多种括号
如 Python 中 列表的方括号[], 字典的花括号{}, 元组和表达式使用的圆括号().
这些不同的括号可能混合在一起使用,因此就要注意各自的开闭匹配情况.
上面我们只是匹配了括号,那如果我们要匹配多种类型的括号呢?
那我们要如何操作?
代码如下:
# 如何给其他类型的括号进行匹配---代码如下👇 class Stack:#Stack---->ADT def __init__(self): self.items =[] def isEmpty(self): return self.items == [] # 满足这些属性(行为)的是栈 def push(self,item): self.items.append(item) def pop(self): return self.items.pop() def peek(self): return self.items[len(self.items)-1] # def size(self): return len(self.items) def parChecker(symbolstring): print(symbolstring) #实例化栈(空栈) s = Stack() #括号匹配法则 balanced = True index = 0 while index < len(symbolstring) and balanced: symbol = symbolstring[index] if symbol in "([{": s.push(symbol) else: #右括号多了或左括号少了 if s.isEmpty():#判断栈 是否为空 balanced = False else: top = s.pop() if not matches(top,symbol): balanced = False index = index + 1 if balanced and s.isEmpty(): return True else: return False def matches(open,close): opens = "([{" closers = ")]}" return opens.index(open) == closers.index(close) result = parChecker("(())}") print(result) print(parChecker("[()]"))
对比匹配括号和其它各种类型的括号的代码可以学习到以下几个小知识点和技巧:
1.Python中 if...in和if...== 的区别
if...in和if...==都是Python中常见的条件语句，但是它们使用方式和判断条件的方式不同。
if...in是用来检查某个元素是否在一个集合（字符串、列表、元组、字典等）中，语法如下：
if element in collection: # do something
例如：
fruits = ["apple", "banana", "cherry"] if "banana" in fruits: print("Yes, banana is in the fruits list")
再比如:
x="banana" if "a" in x: print("a is in x") #a is in x
if...==则是用来检查一个变量或表达式是否等于某个值，语法如下：
if variable == value: # do something
例如：
x = 5 if x == 5: print("x is equal to 5")
上面两段代码的区别就是:
左边代码:单独判断括号是否匹配,为了防止用户输入其它类型的括号进行匹配,所以用==去限制匹配的括号类型
右边代码:因为字符串相当于列表,如果是各种类型的括号,用in的话相当于检查列表中某个元素是否存在,每种类型的括号都可以进行一一匹配
因此，if...in和if...==的区别在于，if...in是用来检查某个元素是否在一个集合中，而if...==是用来检查一个变量或表达式是否等于某个值。
2.括号匹配判断的区别
左边的只是进行括号的匹配,所以直接pop出来即可
而右边的还需要判断栈顶的括号是否和pop的是一对的,一对的才能成功被pop出来,所以利用 matches 进行判断匹配
运行过程:
3.matches函数的匹配小技巧
通过开闭区间下标索引进行位置判断,判断相同类型的括号位置是否一致,从而完成匹配pop出来,就可省去一堆的 if else 判断语句
运行过程:
