algorithmpython-3.xpostfix-notationinfix-notation

Infix to postfix algorithm in python


For my data structures class I have to create a basic graphing calculator using Python 3. The requirement is that we have to use a basic Stack class. The user enters the equation in "infix" form which I'm then supposed to convert to "postfix" for evaluation and graphing. I'm having trouble with the infix to postfix algorithm. I've seen other algorithms that can work but my professor wants it done a certain way. Here's what I have so far:

def inFixToPostFix():
inFix = '3*(x+1)-2/2'
postFix = ''
s = Stack()
for c in inFix:
    # if elif chain for anything that c can be
    if c in "0123456789x":
        postFix += c
    elif c in "+-":
        if s.isEmpty():
            s.push(c)
        elif s.top() =='(':
            s.push(c)
    elif c in "*/":
        if s.isEmpty():
            s.push(c)
        elif s.top() in "+-(":
            s.push(c)
    elif c == "(":
        s.push(c)
    elif c == ")":
        while s.top() is not '(':
            postFix += s.pop()
        s.pop()
    else:
        print("Error")
print(postFix)
return postFix

When I print this i get '3x1+22' when the expected result is '3x1+*22/-' Any help would be appreciated. Thanks.


Solution

  • you should pop the leftover operands on the stack after exiting your loop. The algorithm is pretty straightforward but if you need information here is explained:

    http://interactivepython.org/runestone/static/pythonds/BasicDS/InfixPrefixandPostfixExpressions.html

    Here is my version of the solution if you need it :)

    def toPostfix(infix):
        stack = []
        postfix = ''
    
        for c in infix:
            if isOperand(c):
                postfix += c
            else:
                if isLeftParenthesis(c):
                    stack.append(c)
                elif isRightParenthesis(c):
                    operator = stack.pop()
                    while not isLeftParenthesis(operator):
                        postfix += operator
                        operator = stack.pop()              
                else:
                    while (not isEmpty(stack)) and hasLessOrEqualPriority(c,peek(stack)):
                        postfix += stack.pop()
                    stack.append(c)
    
        while (not isEmpty(stack)):
            postfix += stack.pop()
        return postfix