3.9. Infix, Prefix and Postfix Expressions

In [1]:

    

from stack import Stack


def infixToPostfix(infixexpr):
    prec = {}
    prec["**"] = 4
    prec["*"] = 3
    prec["/"] = 3
    prec["+"] = 2
    prec["-"] = 2
    prec["("] = 1
    opStack = Stack()
    postfixList = []
    tokenList = infixexpr.split()

    for token in tokenList:
        if token[0] in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token in "0123456789":
            postfixList.append(token)
            
        elif token == '(':
            opStack.push(token)
            
        elif token == ')':
            topToken = opStack.pop()
            while topToken != '(':
                postfixList.append(topToken)
                topToken = opStack.pop()
        
        else:
            while (not opStack.is_empty()) and \
                    (prec[opStack.peek()] >= prec[token]):
                postfixList.append(opStack.pop())
            
            opStack.push(token)

    while opStack.size() > 0:
        postfixList.append(opStack.pop())

    return " ".join(postfixList)




def postfixEval(postfixExpr):
    operandStack = Stack()
    tokenList = postfixExpr.split()

    for token in tokenList:
        if token[0] in "0123456789":
            operandStack.push(int(token))
        else:
            operand2 = operandStack.pop()
            operand1 = operandStack.pop()
            result = doMath(token, operand1, operand2)
            operandStack.push(result)
    return operandStack.pop()



def doMath(op, op1, op2):
    if op == "**":
        return op1 ** op2
    elif op == "*":
        return op1 * op2
    elif op == "/":
        return op1 / op2
    elif op == "+":
        return op1 + op2
    else:
        return op1 - op2



print(infixToPostfix("A * B + C * D"))
print(infixToPostfix("( A + B ) * C - ( D - E ) * ( F + G )"))

    
    
    
    
print(postfixEval('7 8 + 3 2 + /'))
print(postfixEval('17 10 + 3 * 9 /'))
e = infixToPostfix("5 * 3 ** ( 4 - 2 )")
print(e)
print(postfixEval(e))


    

    




A B * C D * +
A B + C * D E - F G + * -
3.0
9.0
5 3 4 2 - ** *
45