RPN（后缀表示法）算法 "breaking" 当具有更高优先级的运算符在其他运算符的右边时

Question

我正在将 Python 中的中缀符号转换为后缀符号（当然使用 Shunting-Yard algorithm）。它似乎适用于以下情况：

>>>rpn('9+6-5')
96+5+
>>>rpn('(5+6)/5')
56+5/
>>>rpn('5+(6/5)')
565/+

但是，每当函数接收到如下表达式时，它就会起作用（通过不 returning）：

>>>rpn('5+6/5')
^C 
"something borke"

即，当优先级较低的运算符右侧有较高优先级的运算符时，它不会 return，除非有括号。

这是我使用的完整代码。它似乎非常接近算法，但我可能是错的。

def defop(x):
    return {'+': [2, 'left'], '-': [2, 'left'], '*': [3, 'left'], '/': [3, 'left'], '^': [4, 'right']}[x]       

def rpn(exp):
    stack, queue = [],[]
    try:
        if len(exp) > 0:
            for token in list(exp):
                if token in "+-*/^":
                    _o1 = defop(token)
                    while stack and stack[-1] in '+-*/&^':
                        _o2 = defop(stack[-1])
                        if _o1[1] == 'left' and _o1[0] <= _o2[0] or _o1[1] == 'right' and _o1[0] < _o2[0]:
                            queue.append(stack.pop())                       
                    stack.append(token)
                elif token == '(':
                    stack.append(token)
                elif token == ')':
                    for item in reversed(stack):
                        if item != '(':     
                            queue.append(stack.pop())           
                        else:       
                            stack.pop()
                            break
                else:
                    queue.append(token)
            while stack:
                if stack[-1] in '()':
                    return "Mismatched parentheses"
                queue.append(stack.pop())
    except:
        return 'something borke'
    return ''.join(queue)

Answer 1

当代码到达 while 循环并且 if 语句中的表达式计算结果为 false 时，您的代码会发生什么？

将您链接到的维基百科文章中的重要部分加粗：

while there is an operator token, o2, at the top of the operator stack, and either

o1 is left-associative and its precedence is less than or equal to that of o2, or

o1 is right associative, and has precedence less than that of o2,

RPN（后缀表示法）算法 "breaking" 当具有更高优先级的运算符在其他运算符的右边时

RPN (postfix notation) algorithm "breaking" when operator with higher precedence is to the right of the others

python

postfix-notation