Infix to postfix algorithm in python

Question

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 1

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

Solution 2

class stack:
def __init__(self):
    self.item = []

def push(self,it):
    self.item.append(it)
def peek(self):
    if self.isempty() == True:
        return 0
    return self.item[-1]

def pop(self):
    if self.isempty() == True:
        return 0
    return(self.item.pop())

def length(self):
    return (len(self.item))


def isempty(self):
    if self.item == []:
        return True
    else:
        return False

def display(self):
    if self.isempty()== True:
        return
    temps = stack()
    while(self.isempty() != True):
        x = self.peek()
        print("~",x)
        temps.push(x)
        self.pop()
    while(temps.isempty() != True):
        x = temps.peek()
        self.push(x)
        temps.pop()


def isOperand(self, ch): 
    return ch.isalpha()
def notGreater(self, i):
    precedence = {'+':1, '-':1, '*':2, '/':2, '%':2, '^':3}
    if self.peek() == '(':
        return False
    a = precedence[i]
    b = precedence[self.peek()] 
    if a  <= b:
        return True
    else:
        return False
        


def infixToPostfix(self, exp):
    output = ""
    
    for i in exp:
        
        if self.isOperand(i) == True: # check if operand add to output
            print(i,"~ Operand push to stack")
            output = output + i

        # If the character is an '(', push it to stack 
        elif i  == '(':
            self.push(i)
            print(i," ~ Found ( push into stack")

        elif i == ')':  # if ')' pop till '('
            while( self.isempty() != True and self.peek() != '('):
                n = self.pop() 
                output = output + n
                print(n, "~ Operator popped from stack")
            if (self.isempty() != True and self.peek() != '('):
                print("_________")
                return -1
            else:
                x = self.pop()
                print(x, "Popping and deleting (")
        else: 
            while(self.isempty() != True and self.notGreater(i)):
                c = self.pop()
                output = output + c
                print(c,"Operator popped after checking precedence from stack")
            self.push(i)
            print(i,"Operator pushed to stack")

    # pop all the operator from the stack 
    while self.isempty() != True:
        xx = self.pop()
        output = output + xx
        print(xx,"~ pop at last")
    print(output)
    self.display()
st = stack()
st.infixToPostfix("a+(b*c)")

Here's a complete algorithm with step by step working details.

Output:

a ~ Operand push to stack
+ Operator pushed to stack
(  ~ Found ( push into stack
b ~ Operand push to stack
* Operator pushed to stack
c ~ Operand push to stack
* ~ Operator popped from stack
( Popping and deleting (
+ ~ pop at last
abc*+