中缀转后缀
from pythonds.basic.stack import Stackfrom string import *def infixToPostfix(infixexpr):# 这里创建一个字典是为了后面 优先级 的比较prec = {}prec["*"] = 3prec["/"] = 3prec["+"] = 2prec["-"] = 2prec["("] = 1# 实例化opstack = Stack()postfixList = []# 把输入的字符串分割开tokenList = infixexpr.split()for token in tokenList:# 这里用到的是string模块中的两个方法，源代码都是手敲的字母和数字if token in ascii_uppercase or token in digits:postfixList.append(token)elif token == "(":opstack.push(token)elif token == ")":topstack = opstack.pop()while topstack != "(":postfixList.append(topstack)topstack = 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)print(infixToPostfix("A + B * C "))
A B C * +
后缀表达式计算（这个程序只能计算个位数后缀表达式）
postfix = infixToPostfix("( 1 + 2 ) * 3")def postfixEval(postfix):opStack = Stack()postfixList = postfix.split()for v in postfixList:if v in "0123456789":opStack.push(int(v))else:right = opStack.pop()left = opStack.pop()result = domath(left, right, v)opStack.push(result)return opStack.pop()def domath(left, right, v):if v == "+":return left + rightif v == "-":return left -rightif v == "*":return left * rightif v == "/":return left / rightprint(postfixEval(postfix))
9
