栈的Python实现(列表)

后入先出(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 + /'))

发表评论

评论列表,共 0 条评论

    暂无评论