总结：
任意括号匹配问题
- 利用 dict简化匹配问题
- 用list 近似为stack
- pop返回self
括号匹配
class Solution:def isValid(self, s: str) -> bool:if len(s)%2!=0:return Falsest=[]dict={')':'(',']':'[','}':'{'}for str in s:if str not in dict:# 左括号st.append(str)elif not st or st.pop()!=dict[str]:return Falsereturn not st
十进制转换为二进制
- 栈的一个简单运用：倒序输出
from pythonds.basic import Stack
def Deci2Binary(n:int):st = Stack()while n>0:remainer=n%2quotient=n//2n=n//2st.push(remainer)output_number=''while st.size()>0:output_number=output_number+str(st.pop())print(f'十进制{n}转换为二进制为{output_number}')return output_number
if __name__ == "__main__":deci_n=984bina_n=Deci2Binary(deci_n)中序转后序
无论什么序，运算数的相对顺序不变
在后序表达式中：优先级高的运算符靠左
利用这个特性：遇到优先级低于自己的，必须提前出栈；否则不用出栈
import stringfrom pythonds.basic import Stack
def infix2Postfix(infix_expression:str):dict={}dict[')']=4dict['*']=3dict['/']=3dict['+']=2dict['-']=2dict['(']=1def compare_prior(opa:str,opb:str):# 返回优先级的比较return dict[opa]>dict[opb]opstack=Stack()res=[]token_list=infix_expression.split()for token in token_list:"""三种情况：1.正常的数字或者字母2.优先级低：出栈3.优先级高：入栈"""if token in string.ascii_uppercase:res.append(token)elif token in string.digits:res.append(token)else:# if opstack.isEmpty() or compare_prior(token,opstack.peek()):# # 栈为空且优先级高:加入while not opstack.isEmpty() and compare_prior(token,opstack.peek()):# 如果栈顶元素优先级更大# 栈不为空且优先级低:pop_item=opstack.pop()if pop_item not in ['(',')']:# (*)-res.append(pop_item)opstack.push(token)# print(res)# print(opstack.peek())return resif __name__ == "__main__":infix_expression="( A + B ) * ( C + D )"print(infix2Postfix(infix_expression))
