class Stack: def __init__(self): self.items=[] def isEmpty(self): return self.items==[] def push(self,item): #添加元素进站 self.items.append(item) def peek(self): #打印栈顶元素 return self.items[len(self.items)-1] def pop(self): #从栈顶取出元素 return self.items.pop() def size(self): #返回栈中元素的个数 return len(self.items)def infixToPostfix(infixexpr): # prec字典存储着运算符的优先级 prec = {} prec["*"] = 3 prec["/"] = 3 prec["+"] = 2 prec["-"] = 2 prec["("] = 1 # 定义空栈存储运算符出栈和进栈操作结果 openStack = Stack() # 存储最后的后缀表达式的结果list postficList = [] # tokenList存储将表达式分割字符后的list,要求表达式中的字符之间必须有空格 tokenList = infixexpr.split() for token in tokenList: # 只要分割的字符在A-Z或者阿拉伯数字0-9之间放到postficList if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token.isnumeric(): #isnumeric()方法判断token是否是数字 postficList.append(token) # 左括弧匹配 elif token == '(': openStack.push(token) elif token == ')': toptoken = openStack.pop() # 非括弧符号匹配 while toptoken != '(': postficList.append(toptoken) toptoken = openStack.pop() else: # 运算符优先级比较 while (not openStack.isEmpty()) and (prec[openStack.peek()] >= prec[token]): postficList.append(openStack.pop()) openStack.push(token) while not openStack.isEmpty(): postficList.append(openStack.pop()) return " ".join(postficList)def postfixEval(postfixExpr): #后缀表达式的计算 operandStack=Stack() tokenList=postfixExpr.split() #对表达式进行分离 for token in tokenList: if token.isnumeric(): 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): if op=="*": return op1*op2 elif op=="/": return op1/op2 elif op=="+": return op1+op2 else: return op1-op2if __name__ == '__main__': print(infixToPostfix("A * B + C * D")) print(infixToPostfix("( ( A * B ) + ( C * D ) )")) print(infixToPostfix("A + B * C + D")) print(infixToPostfix("( A + B ) * ( C + D )")) print(infixToPostfix("A * B + C * D")) print(infixToPostfix("83 * 9 + 4")) postresult=infixToPostfix("70 * 9 + 4") #print(postresult) print(postfixEval(postresult)) 
