中序表达式问题

davidmou

from pythonds.basic import Stack
import string

def hanshu(n):
    dict1 = {}
    dict1["*"] = 3
    dict1["/"] = 3
    dict1["+"] = 2
    dict1["-"] = 2
    dict1["("] = 1

    opstack = Stack()
    poslist = []

    tokenlist = n.split()
    for token in tokenlist:
        if token in string.ascii_uppercase:
            poslist.append(token)

        elif token == "(":
            opstack.push(token)

        elif token == ")":
            toptoken = opstack.pop()
            while toptoken != "(":
                poslist.append(toptoken)
                toptoken = opstack.pop()
        else:
            while not (opstack.isEmpty()) and dict1[opstack.peek()] >= dict1[token]:
                poslist.append(opstack.pop())
            opstack.push(token)

    while not opstack.isEmpty():
        poslist.append(opstack.pop())

    return "".join(poslist)


print(hanshu('( ( A  + B ) * D ) * N'))

这是中序表达式变为后续表达式的代码

有哪位大神能解释一下为什么会想出这样的代码，有什么依据吗

isdkz

这段代码是中序表达式转后序表达式的实现。中序表达式是指运算符位于操作数之间的表达式，而后序表达式是指运算符位于操作数之后的表达式。例如，中序表达式 A + B * C 可以转换为后序表达式 A B C * +。

这段代码的实现思路是使用栈来存储运算符和括号，并通过比较运算符的优先级来确定运算符的位置。具体来说，当遇到一个运算符时，如果该运算符的优先级小于等于栈顶运算符的优先级，则将栈顶运算符弹出并加入到后序表达式中，直到栈顶运算符优先级小于该运算符的优先级或者栈为空，然后将该运算符入栈。当遇到左括号时，直接将其入栈，当遇到右括号时，将栈顶运算符弹出并加入到后序表达式中，直到遇到左括号为止。

该实现的依据是栈的后进先出特性，以及运算符的优先级规则。