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+'