数据结构·栈

总结：

任意括号匹配问题

• 利用 dict简化匹配问题
• 用list 近似为stack
• pop返回self
  括号匹配

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s)%2!=0:
            return False
        st=[]
        dict={')':'(',']':'[','}':'{'}
        for str in s:
            if str not in dict:# 左括号
                st.append(str)
            elif not st or st.pop()!=dict[str]:
                return False
        return not st

十进制转换为二进制

• 栈的一个简单运用：倒序输出

from pythonds.basic import Stack
def Deci2Binary(n:int):
    st = Stack()
    while n>0:
        remainer=n%2
        quotient=n//2
        n=n//2
        st.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=984
    bina_n=Deci2Binary(deci_n)

中序转后序

无论什么序，运算数的相对顺序不变
在后序表达式中：优先级高的运算符靠左
利用这个特性：遇到优先级低于自己的，必须提前出栈；否则不用出栈

import string

from pythonds.basic import Stack
def infix2Postfix(infix_expression:str):
    dict={}
    dict[')']=4
    dict['*']=3
    dict['/']=3
    dict['+']=2
    dict['-']=2
    dict['(']=1
    def 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 res

if __name__ == "__main__":
    infix_expression="( A + B ) * ( C + D )"
    print(infix2Postfix(infix_expression))