Python前缀转后缀表达式函数中乘法运算符位置异常问题排查

你现在写的函数逻辑是经典的中缀表达式转后缀表达式的调度场算法，完全不符合前缀表达式的转换规则，前两个测试用例通过纯属巧合：

• 单数字输入"5"无论转换逻辑只要输出原字符就符合预期
• 二级前缀输入"+ 10 20"的字符遍历顺序刚好误打误撞输出了符合预期的结果，碰到多层嵌套的前缀表达式就会直接出错。

除此之外你还有两个明显的实现错误：

• 没有拆分输入的token：前缀表达式是用空格分隔每个运算单元（运算符、多位数），你直接按单个字符遍历，会把空格、多位数的不同数位都当作独立字符处理
• 运算符优先级规则对前缀转后缀完全无用，前缀表达式的运算顺序已经由表达式的结构直接决定，不需要靠优先级判断

你遍历输入"* + 1 2 - 5 3"时，第一个字符*识别为运算符压入栈；遇到第二个字符+时，判断+优先级低于栈顶的*，因此先把*弹出追加到输出开头，这就是你看到*出现在输出最前面的直接原因。

前缀表达式转后缀的标准处理逻辑是：

1. 先把输入字符串按空格拆分，得到独立的token列表，过滤空字符串
2. 从右往左遍历所有token
3. 遇到操作数直接压入栈
4. 遇到运算符时，弹出栈顶两个操作数，按照操作数1 操作数2 运算符的格式拼接后重新压入栈
5. 遍历结束后栈中唯一剩余的元素就是最终的后缀表达式

def prefix_to_postfix(expression):
    OPERATORS = set(['+', '-', '*', '/', '^'])
    # 拆分token
    tokens = expression.split()
    stack = []
    # 从右往左遍历
    for token in reversed(tokens):
        if token not in OPERATORS:
            stack.append(token)
        else:
            # 弹出两个操作数
            op1 = stack.pop()
            op2 = stack.pop()
            # 拼接成后缀格式压栈
            stack.append(f"{op1} {op2} {token}")
    return stack.pop()

# 测试断言
assert(prefix_to_postfix("5") == "5")
assert(prefix_to_postfix("+ 10 20") == "10 20 +")
assert(prefix_to_postfix("* + 1 2 - 5 3") == "1 2 + 5 3 - *")

运行上面的代码可以通过所有三个断言。

内容的提问来源于stack exchange，提问作者tuf001