Reverse polish notation algorithm doesn`t work correctly with the same operands

Question

I've written polish notation algorithm. But it doesn`t work properly, if there are the same operands between operator. If we run this code with current list ['a', '+', 'a', '*', 'b'], it will work properly, but if we change(b) on (a) it won't. The result in the first case is (a, a, b, *, +) and in the second (a, a, +, a, *). Why does it happen?

operators = ["+", "-"]
operators1 = ["*", "/"]
operators2 = ["^"]
operators3 = ["(", ")"]
all_operators = ["+", "-", "*", "/", "^"]


def get_priority(operator):
    if operator in operators:
        priority = 1
    if operator in operators1:
        priority = 2
    if operator in operators2:
        priority = 3
    if operator in operators3:
        priority = 4
return priority


def notation():
exit = []
stack = []
list = ['a', '+', 'a', '*', 'b']
for i in list:

    if i not in all_operators:
        exit.append(i)

    else:
        stack.append(i)
        while len(stack) > 1 and get_priority(stack[-2]) >= get_priority(stack[-1]):
            exit.append(stack.pop(-2))

    if i is list[-1]:
        while len(stack) > 0:
            exit.append(stack.pop())

print(exit)
    


notation()

 

Answer 1

The error is i is list[-1] and it surfaces when the last element of the list is a value that occurs also earlier in the list. In the case of ['a', '+', 'a', '*', 'a'], the condition will be true on the first iteration of the loop (and the third, and the last). Obviously this will produce wrong results.

As you want to perform that while loop only when going through the last iteration of the for loop, you might as well move that while loop after the whole for block, and unconditionally.

I applied some other changes to your code that do not relate to your question, and are not fixes to the algorithm itself, but just seem better practice. And I removed the parentheses from the operator list, as your code does not support that feature yet (Polish notation should not include parentheses):

operator_priority = {
    "+": 1,
    "-": 1,
    "*": 2,
    "/": 2,
    "^": 3,
}

all_operators = list(operator_priority.keys())

def notation(tokens):
    result = []
    stack = []
    for token in tokens:
        if token not in all_operators:
            result.append(token)
        else:
            prio = operator_priority[token]
            while len(stack) > 0 and operator_priority[stack[-1]] >= prio:
                result.append(stack.pop())
            stack.append(token)
    while len(stack) > 0:
        result.append(stack.pop())
    return result
    
result = notation(['a', '+', 'a', '*', 'a'])
print(result)