中序表达式转后序表达式

什么是中序表达式

中序表达式就是我们日常使用的算术表达式，也称为中缀表达式。它的主要特点是操作符位于两个操作数之间，并且通常需要括号来改变运算的优先级

例如

3 + 4 × ( 5 + 6) - 8 / 2

什么是后序表达式

后序表达式，也被称为后缀表达式或逆波兰表示法（Reverse Polish notation，RPN），是一种算术表达式的书写方式，其中操作符位于其操作数之后。

例如

将 中序表达式 (1+4)×3+10/5 转后序表达式 1 4 + 3 * 10 5 / +

算法实现

class Stack:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return len(self.items) == 0
        
    def push(self,item):
        self.items.append(item)
    
    def pop(self):
        return self.items.pop()
    def peek(self):
        return self.items[len(self.items) - 1]
    
    def size(self):
        return len(self.items)

先定义好一个栈后续需要用到这个数据结构

import string
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)

结果输出

infixToPostfix("( A + B ) * ( C + D )")

'A B + C D + *'