栈的Python实现（列表）

太过爱你忘了你带给我的痛 2022-05-30 07:48 180阅读 0赞

# 栈 #

后入先出（LIFO）

class Stack(object):
        """栈的Python列表实现"""
        #初始化对象，生成空列表
        def __init__(self):
            self.item = []
    
        #判断栈是否为空，返回True or False
        def isEmpty(self):
            return self.item == []
    
        #入栈方法，添加至列表尾部
        def push(self, item):
            self.item.append(item)
    
        #出栈方法，从队列尾部弹出，并返回弹出值
        def pop(self):
            return self.item.pop()
    
        #查栈顶元素方法，返回栈顶元素值，但不弹出
        def peek(self):
            return self.item[len(self.item)-1]
    
        #查看栈的大小方法，返回int值
        def size(self):
            return len(self.item)
    
    def match_sympol(string):
        '''
        利用栈的特性（后进先出），对三种常见括号进行匹配
        对于左括号，直接压入栈，遇到右括号，弹出栈顶元素，若能一一对应，且最终栈为空，则完全匹配
        '''
        s = Stack()
        flag = True
        index = 0
        while index < len(string) and flag:
            symbol = string[index]
            if symbol in "({[":
                s.push(symbol)
            else:
                if s.isEmpty():
                    flag = False
                else:
                    top = s.pop()
                    if not matches_help(top, symbol):
                        flag = False
            index += 1
    
        if flag and s.isEmpty():
            return True
        else:
            return False
    
    def matches_help(open, close):
        '''
        匹配辅助函数
        传入两个char参数，判断是否对应，返回True or False
        '''
        opens = "({["
        closes = ")}]"
        return opens.index(open) == closes.index(close)
    
    def ten2two(num):
        '''
        十进制转二进制，原理是除二取余法
        将十进制数除二取余数，将余数压入栈，直到十进制数为0，然后栈逐个弹出
        '''
        s = Stack()
    
        while num > 0:
            rem = num%2
            s.push(rem)
            num = num//2
    
        binString = ""
        while not s.isEmpty():
            binString = binString + str(s.pop())
    
        return binString
    
    def infixToPostfix(infixexpr):
        '''
        中序表达式转后续表达式
        中序表达式转换后续表达式有个简单的方法，先将中序表达式的每一次运算都加上括号，接着从右往左，
        找到第一个算数符号替换掉最近的右括号，并将对应的左括号去除，继续往左执行，直到没有括号为止
        具体过程：
        1、创建一个名为 opstack 的空栈以保存运算符。给输出创建一个空列表。
        2、通过使用字符串方法拆分将输入的中缀字符串转换为标记列表。
        3、从左到右扫描标记列表。
              如果标记是操作数，将其附加到输出列表的末尾。
              如果标记是左括号，将其压到 opstack 上。
              如果标记是右括号，则弹出 opstack，直到删除相应的左括号。将每个运算符附加到输出列表的末尾。
              如果标记是运算符，*，/，+或 - ，将其压入 opstack。但是，首先删除已经在 opstack 中具有更高或相等优先级的任何运算符，并将它们加到输出列表中。
        4、当输入表达式被完全处理时，检查 opstack。仍然在栈上的任何运算符都可以删除并加到输出列表的末尾。
        理解过程可见：https://facert.gitbooks.io/python-data-structure-cn/3.%E5%9F%BA%E6%9C%AC%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/3.9.%E4%B8%AD%E7%BC%80%E5%89%8D%E7%BC%80%E5%92%8C%E5%90%8E%E7%BC%80%E8%A1%A8%E8%BE%BE%E5%BC%8F/
        '''
        prec = {}
        prec["*"] = 3
        prec["/"] = 3
        prec["+"] = 2
        prec["-"] = 2
        prec["("] = 1
        opStack = Stack()
        postfixList = []
        tokenList = infixexpr.split()
    
        for token in tokenList:
            if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token in "0123456789":
                postfixList.append(token)
            elif token == '(':
                opStack.push(token)
            elif token == ')':
                topToken = opStack.pop()
                while topToken != '(':
                    postfixList.append(topToken)
                    topToken = opStack.pop()
            else:
                while (not opStack.isEmpty()) and (prec[opStack.peek()] >= prec[token]):
                    postfixList.append(opStack.pop())
                opStack.push(token)
    
        while not opStack.isEmpty():
            postfixList.append(opStack.pop())
        return " ".join(postfixList)
    
    def postfixEval(postfixExpr):
        '''
        后缀表达式的算值
        根据后缀表达式的特点，很容易可以想到，将运算数压入栈，当出现符号时，弹出栈顶两个元素，计算完成后压入栈，
        等待下一个运算数或者运算符，最后栈顶元素就是后缀表达式的值。
        '''
        operandStack = Stack()
        tokenList = postfixExpr.split()
    
        for token in tokenList:
            if token in "0123456789":
                operandStack.push(int(token))
            else:
                operand2 = operandStack.pop()
                operand1 = operandStack.pop()
                result = doMath(token, operand1, operand2)
                operandStack.push(result)
            return operandStack.pop()
    
    def doMath(op, op1, op2):
        '''
        后缀表达式运算值的辅助函数
        输入三个参数（运算符，操作数1，操作数2），返回运算结果。
        '''
        if op == "*":
            return op1 * op2
        elif op == "/":
            return op1 / op2
        elif op == "+":
            return op1 + op2
        else:
            return op1 - op2
    
    #栈的测试
    # s= Stack()
    # print(s.isEmpty())
    # s.push(4)
    # s.push('dog')
    # print(s.peek())
    # s.push(True)
    # print(s.size())
    # print(s.isEmpty())
    # s.push(8.4)
    # print(s.pop())
    # print(s.pop())
    # print(s.size())
    #符号匹配的测试
    # print(match_sympol('{
        {([][])}()}'))
    #十进制数转二进制的测试
    # print(ten2two(100))
    #中缀表达式转后缀表达式的测试
    # print(infixToPostfix("( A + B ) * C - ( D - E ) * ( F + G )"))
    #后缀表达式的求求值
    # print(postfixEval('7 8 + 3 2 + /'))