前言

1. 快速实现栈的两种方法和两个小应用

方法1：

# 代码 3-1 用python实现栈
class Stack:def __init__(self) -> None:self.items = []def push(self, item):self.items.append(item)def pop(self):return self.items.pop()def peek(self):return self.items[self.size()-1]def isEmpty(self):return self.size()==0def size(self):return len(self.items)

方法2:

# 代码3-2 栈的另一种实现
class Stack1:def __init__(self) -> None:self.items = []def push(self, item):self.items.insert(0,item) # 左侧第一个def peek(self):return self.items[len(self.items)-1]def isEmpty(self):return self.items == []def size(self):return len(self.items)

应用1：一个小应用，匹配括号 （（（）））
最左侧必须要和最右侧匹配

def parChecker(symbolString):s = Stack()balanced = Trueindex = 0 while index < len(symbolString) and balanced:symbol = symbolString[index]if symbol == '(':s.push(symbol)else:if s.isEmpty():balanced = Falseelse:s.pop()index = index + 1if balanced and s.isEmpty():return Trueelse:return False

symbolString = "((())"
parChecker(symbolString)
Flase

应用2：一个小应用，匹配括号 [{（）}]

def parChecker(symbolString):s = Stack()balanced = Trueindex = 0 while index < len(symbolString) and balanced:symbol = symbolString[index]if symbol in '({[':s.push(symbol)else:if s.isEmpty():balanced = Falseelif '({['.index(s.peek()) == ')}]'.index(symbol):s.pop()else:balanced = Falseindex = index + 1if balanced and s.isEmpty():return Trueelse:return False

symbolString = "([()])"
parChecker(symbolString)

应用3 10进制转2进制
原理：10进制的数据反复除以2，取余数，知道商为0，再反向取余即可。 取余为压栈，反向为出栈

def divideBy2(decNumber):remstack = Stack()while decNumber > 0:rem = decNumber % 2remstack.push(rem)decNumber = decNumber // 2binString = ""while not remstack.isEmpty():binString = binString + str(remstack.pop())return binString    

应用4 10进制转任意进制

def divideBy2(decNumber,base):remstack = Stack()while decNumber > 0:rem = decNumber % baseremstack.push(rem)decNumber = decNumber // basebinString = ""while not remstack.isEmpty():binString = binString + str(remstack.pop())return binString    

2.中序变前序表达式

奇不奇怪，这里也有我，考研的时候我记得我就没看明白这里。
前序表达式：要求所有的运算符出现在它所作用的两个操作数之前，后序表达式则相反。
中序表达式需要括号消除歧义，而前序和后序表达式对两个操作数是明确的，因此更适合做表达式。

import string
def infixToPostFix(infixexpr):prec = {}prec["*"] = 3prec["/"] = 3prec["+"] = 2prec["-"] = 2prec["("] = 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())print(postFixList)return " ".join(postFixList)

res = infixToPostFix(" ( A + B ) * C - ( D - E ) * ( F + G )")
print(res)

[‘A’, ‘B’, ‘+’, ‘C’, ‘', ‘D’, ‘E’, ‘-’, ‘F’, ‘G’, ‘+’, '’, ‘-’]
A B + C * D E - F G + * -
计算过程：想出这个算法是很难的， 但是复现这个计算过程是我们所需要的。

3.计算中序表达式的结果

# 代码3-8
def doMath(op, op1, op2):if op == "*":return op1 * op2elif op == "/":return op1/op2elif op == "+":return op1 + op2else:return op1 - op2
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()

注意点:

1. operandStack.push(int(token))
2. 只能计算10以内的各种组合

postfixExpr = "1 2 + 9 *"
postfixEval(postfixExpr)
# 27