# Python实现中缀表达式向后缀表达式

xiaoxiao2021-02-28  5

from pythonds.basic.stack import Stack 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 in "0123456789": 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) if __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("A + B + C + D")) 根据上面的求解后缀表达式算法，然后我们继续深入，根据表达式求出后缀表达式后在求出表达式的结果，就走完计算机存储体系中关于表达式计算的完整过程。

from pythonds.basic.stack import Stack 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 in "0123456789": 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 postficEval(infixexpr): openStack = Stack() # 先转换中缀表达式为后缀表达式 tokenList = infixToPostfix(infixexpr).split() # print(tokenList) for token in tokenList: # 遇到操作数就压栈 if token in "0123456789": openStack.push(int(token)) else: #　遇到操作运算符就出站，并且计算最近的两个操作数 #　这里因为操作数的相对顺序原因，第一个操作数是栈顶第二个元素 openTop2 = openStack.pop() openTop1 = openStack.pop() # 执行计算 result = opMath(token, openTop1, openTop2) # 返回结果继续压栈 openStack.push(result) # 直到栈空间只剩下一个操作数，那么就弹出即为最终结果 return openStack.pop() def opMath(op, op1, op2): if op == '*': return op1 * op2 elif op == '/': return op1 / op2 elif op == '+': return op1 + op2 else: return op1 - op2 if __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(type(infixToPostfix("A * B + C * D"))) print(len(infixToPostfix("A * B + C * D"))) print(infixToPostfix("A + B + C + D")) print('=================================') print(postficEval("3 * ( 2 - 3 )"))