How to handle functions call in RPN

430 views Asked by At

I'm having a lot of trouble converting infix notation to postfix.

For instance, I want to convert this

test(a(b+c), d()) - 3

into this

b c + a , d test 3 -

I tried this solution,

def composition(s):
    i = 0
    rpnstack = []
    stack = []
    ret = []
    count = 0
    while i < len(s) :
        if i + 1 < len(s) and s[i + 1] == "(":
            stack.append([count, rpnstack, s[i]])
            i += 2
            count = 1
            rpnstack = []
        elif s[i] == "(":
            count += 1
            rpnstack.append(s[i])
            i += 1
        elif s[i] == ")":
            count -= 1
            if count == 0:
                for a in rpn(rpnstack):
                    ret.append(a)
                a = stack.pop()
                count = a[0]
                rpnstack = a[1]
                ret.append(a[2])
            else:
                rpnstack.append(s[i])
            i += 1
        else:
            rpnstack.append(s[i])
            i += 1
    for a in rpn(rpnstack):
        ret.append(a)
    return ret

where RPN is the standard algorithm for the reverse polish notation and is is the infix string splitted with this regex

(\+|\-|\*|\/|\>|\<|\(|\)|\,)

But it only works sometimes.

This is the full implementation of the rpn function

operator = -10
operand = -20
leftparentheses = -30
rightparentheses = -40
empty = -50

operands = ["+", "-", "*", "/", ">", "<", "=", ","]


def precedence(s):
    if s is '(':
        return 0
    elif s is '+' or '-':
        return 1
    elif s is '*' or '/' or '%':
        return 2
    else:
        return 99

def typeof(s):
    if s is '(':
        return leftparentheses
    elif s is ')':
        return rightparentheses
    elif s in operands:
        return operator
    elif s is ' ':
        return empty    
    else :
        return operand                          


def rpn(infix):
    postfix = []
    temp = []
    for i in infix :
        type = typeof(i)
        if type is leftparentheses :
            temp.append(i)
        elif type is rightparentheses :
            next = temp.pop()
            while next is not '(' or skip > 0:
                postfix.append(next)
                next = temp.pop()
        elif type is operand:
            postfix.append(i)
        elif type is operator:
            p = precedence(i)
            while len(temp) is not 0 and p <= precedence(temp[-1]) :
                postfix.append(temp.pop())
            temp.append(i)
        elif type is empty:
            continue

    while len(temp) > 0 :
        postfix.append(temp.pop())

    return postfix

if i try to use the code against this infix expression:

i < test.func()

i get:

[' test.func', 'i ', '<']

and against this

i < 10

i get:

['i ', ' 10', '<']

How can I fix this?

0

There are 0 answers