Python数据结构—栈

​ 摸鱼ing… python栈基本实现和简单实例。

# python数据结构第一课 栈 2021/12/29
import string
class Stack:
    def __init__(self):
        self.items = []
    def isEmpty(self):
        return self.items == []
    # 入栈
    def push(self,item):
        self.items.append(item)
    # pop移除栈顶端的元素，并返回值
    def pop(self):
        return self.items.pop()
    # peek返回栈顶端元素但不移除
    def peek(self):
        return self.items[len(self.items)-1]

    def size(self):
        return len(self.items)
def test():
    s = Stack()
    print(s.isEmpty())
    s.push('cy')
    s.push('lzh')
    s.push(1)
    s.push({'f':'99'})
    print(s.isEmpty())
    print(s.pop())
    print(s.peek()) #不移除栈顶端的元素
    print(s.size())

# 栈的应用一:简单括号匹配
def parChecker1(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

# 栈的应用二:复杂括号匹配
def matches(open,close):
    opens = "([{"
    closes = ")]}"
    return opens.index(open) == closes.index(close)#应该是最简单的写法吧？

def parChecker2(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

# 栈的应用三:十进制数转二进制（除k取余法,k也可以取其他值，可将十进制转化为其他非二进制数）
def divideBy2(decNumber):
    remstack = Stack()

    while decNumber > 0:
        rem = decNumber % 2
        remstack.push(rem)
        decNumber = decNumber // 2

    binString = ''
    while not remstack.isEmpty():
        binString = binString + str(remstack.pop())

    return binString

# 栈的应用四:中序表达式到后序表达式的转化
def infixToPostfix(infixexpr):
    prec = {}
    #用字典将数字和运算符号对应以确定运算符的优先级
    prec["*"] = 3
    prec["/"] = 3
    prec["+"] = 2
    prec["-"] = 2
    prec["("] = 1

    opStack = Stack()
    postfixList = []

    tokenList = infixexpr.split()

    for token in tokenList:
        if token in string.ascii_uppercase:
            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)