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.

Answer 1

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

Answer 2

A lot of modifications required in the algorithm to make it correct.

1. Using this type of string representation for postfix strings, later while evaluating them you may end up as- same representation for 2+34 and 23+4 that is 234+
2. if the operand encountered is of lower precedence than that at the top of operand stack,pop from operand stack and push it to postfix stack (you haven't done this)
3. remaining operands in the operand stack, after the completion of traversal of the given infix string, should be popped from it and pushed to the postfix stack.

---

It's one of the initial tasks in data structures course as it really acknowledges you with the use of stacks.Thus i won't share my code, because i think you can get there yourself.Still having difficulty,share the obstacles i will guide you a path to destination.

Answer 3

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