Convert infix to RPN ready postfix notation with exponents handling without parentheses

Question

I'm trying to convert infix like this:

1+(9-6)^2+3

to RPN ready Polish postfix notation format.

There is code for the purpose:

def toRPN(s):
    kv = {"+": 1, "-": 1, "*": 2, "/": 2, "^": 2, "(": 0, ")": 3}
    li = []
    ops = ["+", "-", "*", "/", "(", ")", "^"]
    result = ""
    for i in s:
        if i in ops:
            if i == "(":
                li.append(i)
            elif i == ")":
                while len(li) > 0 and li[-1] != "(":
                    p = li.pop()
                    result += p
                li.pop()
            elif len(li) == 0 or kv[li[-1]] < kv[i]:
                li.append(i)
            else:
                result += i
        else:
            result += i

    while len(li) > 0:
        result += li.pop()

    return result

Output for the given string is such: 196-2+3^+.

But it's not correct output. Calculation of this expression will not be correct.

Expected output: 196-2^+3+

I can achieve this with parentheses of course: 1+((9-6)^2)+3 and output will be correct as expected: 196-2^+3+. But I want to achieve behavior like in Chrome console (prioritize exponents without parentheses). Screenshot:

But I can't achieve such behavior.

Code for RPN calculation:

import operator

ops = {"+": operator.add, "-": operator.sub, "*": operator.mul, "/": operator.truediv, "^": operator.pow}

def evalRPN(s):
    st = []
    for tk in s:
        if tk in ops:
            b, a = st.pop(), st.pop()
            r = ops[tk](a, b)
        else:
            r = float(tk)
        st.append(r)
    return st.pop()

EDIT:

I find out the converter generate incorrect expression for simple input even like this: 1+9-4. For such input it was generate RPN like this: 19-4+ when should: 19+4-. So with debugger I fixed the converter behavior with adding the following:

if len(li) and li[-1] not in ['(', ')']:
    result += li.pop()

for the case when i is not operator (on line 19). And change priorities to {"+": 1, "-": 1, "*": 2, "/": 2, "^": 3, "(": 0, ")": 4}

So my code now:

def toRPN(s: str) -> str:
    priority = {"+": 1, "-": 1, "*": 2, "/": 2, "^": 3, "(": 0, ")": 4}
    li = []
    ops = ["+", "-", "*", "/", "(", ")", "^"]
    result = ""
    for i in s:
        if i in ops:
            if i == "(":
                li.append(i)
            elif i == ")":
                while len(li) > 0 and li[-1] != "(":
                    p = li.pop()
                    result += p
                li.pop()
            elif len(li) == 0 or priority[li[-1]] < priority[i]:
                li.append(i)
            else:
                result += i
        else:
            result += i
            if len(li) and li[-1] not in ['(', ')']:
                result += li.pop()

    while len(li) > 0:
        result += li.pop()

    return result

But after that change I got problems with some simple expressions like this "3+5/2". Before that "fix" it's worked right without parentheses. So my general question is how to fix the algorithm such that can handle all expressions correctly.

Answer 1

As @n-1-8e9-wheres-my-share-m said above, you don't have loop with pop operators with greater priority (or equal priority to left-associative). You do it for brackets only. I do not how small edit your code to correct but it is correct:

def toRPN(s: str) -> str:
    priority = {"+": 1, "-": 1, "*": 2, "/": 2, "^": 3, "(": -1, ")": 0}
    right_associative_operators = {"^"}
    li = []
    ops = ["+", "-", "*", "/", "(", ")", "^"]
    result = ""
    for i in s:
        if i in ops:
            if i == "(":
                li.append(i)
            else:
                while li and (
                    priority[li[-1]] > priority[i] or
                    priority[li[-1]] == priority[i] and i not in right_associative_operators
                ):
                    result += li.pop()
                if i == ')':
                    li.pop()
                else:
                    li.append(i)
        else:
            result += i

    while li:
        result += li.pop()

    return result

I set priority["("] as -1 and priority[")"] as 0 to don't write a separate loop for brackets and other operators.

This condition:

priority[li[-1]] == priority[i] and i not in right_associative_operators

to correct work with right-associative operators. If it is unnecessary then you can use simpler the condition:

while li and priority[li[-1]] >= priority[i]:

Some outputs:

toRPN('1+(9-6)^2+3') = '196-2^+3+'
toRPN('1+9-4') = '19+4-'
toRPN('2^3^4') = '234^^'
toRPN('1+2+3+4') = '12+3+4+'

Answer 2

Your implementation is incorrect. Look at the Wikipedia article describing the algorithm:

- an operator o1:
    while (
        there is an operator o2 other than the left parenthesis at the top
        of the operator stack, and (o2 has greater precedence than o1
        or they have the same precedence and o1 is left-associative)
    ):
        pop o2 from the operator stack into the output queue
    push o1 onto the operator stack

Your code:

        elif len(li) == 0 or priority[li[-1]] < priority[i]:
            li.append(i)
        else:
            result += i

is missing the entire while part, abd the else part in it comes from nowhere. You are not supposed to copy any operator directly to the output.

Also bear in mind that ^ is usually considered right-associative while all other normal operators are left-associative. Your code does not take associativity into account (which may or may not be within your design parameters).