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

Question

I'm making a converter from infix to postfix notation in Python (using the Shunting-Yard algorithm, of course). It seems to work for things like the following:

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

However, it is acting up (by not returning) whenever the function receives an expression like:

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

i.e., it doesn't return when there are operators with higher precedence to the right of one with lower precedence, unless there are parentheses.

Here's the full code I'm using. It seems to be following the algorithm pretty closely, but I could be wrong.

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

What happens in your code when it reaches the while loop and the expression in the if statement evaluates to false?

Bolded the important part from the Wikipedia article you linked to:

• 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,