Monday, 9 August 2021

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

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.

enter image description here

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.



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

No comments:

Post a Comment