In [6]:
from pythonds9.basic.stack import Stack
import string
In [7]:
string.ascii_uppercase
Out[7]:
'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
In [8]:
token_list = "A + B * ( C * D )".split()
token_list
Out[8]:
['A', '+', 'B', '*', '(', 'C', '*', 'D', ')']
In [9]:
def infix_to_postfix(infix_expr):
    opstack = Stack()
    postfix_list = []
    token_list = infix_expr.split()
    
    for token in token_list:
        if token in string.ascii_uppercase:
            postfix_list.append(token)
        elif token == "(":
            opstack.push(token)
        elif token == ")":
            top_token = opstack.pop()
            while top_token != "(":
                postfix_list.append(top_token)
                top_token = opstack.pop()
        else:  # implicity operators
            if not opstack.is_empty() and opstack.peek() != '(':
                postfix_list.append(opstack.pop())
            opstack.push(token)
                
    while not opstack.is_empty():
        postfix_list.append(opstack.pop())
        
    return " ".join(postfix_list)
In [10]:
# opstack = Stack([])
# postfix_list = ["A", "B", "+","C","D","*","*"]
" ".join(["A", "B", "+","C","D","*","*"])
Out[10]:
'A B + C D * *'
In [11]:
# This ignores proper operator precedence!
expr = "A * B + C * D"
infix_to_postfix(expr)
Out[11]:
'A B * C + D *'
In [12]:
expr = "( A + B ) * C - ( D - E ) * ( F + G )"
infix_to_postfix(expr)
Out[12]:
'A B + C * D E - - F G + *'

With precedence

In [31]:
def infix_to_postfix2(infix_expr):
    prec = {
        "*":3,
        "/":3,
        "+":2,
        "-":2,
        "(": 1
    }
    
    opstack = Stack()
    postfix_list = []
    token_list = infix_expr.split()
    
    for token in token_list:
        if token.isalpha() or token.isdigit():
            postfix_list.append(token)
        elif token == "(":
            opstack.push(token)
        elif token == ")":
            top_token = opstack.pop()
            while top_token != "(":
                postfix_list.append(top_token)
                top_token = opstack.pop()
        else:  # implicity operators
            while (not opstack.is_empty() and prec[opstack.peek()] >= prec[token]):
                   postfix_list.append(opstack.pop())
                
            opstack.push(token)
            
    while not opstack.is_empty():
        postfix_list.append(opstack.pop())
        
    return " ".join(postfix_list)
In [32]:
expr = "A * B + C * D"
print("without precedence:", infix_to_postfix(expr))
print("with precedence:", infix_to_postfix2(expr))
without precedence: A B * C + D *
with precedence: A B * C D * +
In [33]:
expr = "A + B * ( C * D )"
print("without precedence:", infix_to_postfix(expr))
print("with precedence:", infix_to_postfix2(expr))
without precedence: A B + C D * *
with precedence: A B C D * * +
In [34]:
 expr = "9 + 42 * ( 33 * 15 )"
print("with precedence:", infix_to_postfix2(expr))
with precedence: 9 42 33 15 * * +
In [22]:
string.digits
Out[22]:
'0123456789'
In [23]:
"9" in string.digits
Out[23]:
True
In [24]:
"42" in string.digits
Out[24]:
False
In [27]:
"42".isdigit()
Out[27]:
True

Postfix Expression Evaluation

In [35]:
def postfix_eval(postfix_expr):
    operand_stack = Stack()
    token_list = postfix_expr.split()
    
    for token in token_list:
        if token.isdigit():  # operand
            operand_stack.push(int(token))
        else:  # operator, and thus we need to evaluate
            operand2 = operand_stack.pop()
            operand1 = operand_stack.pop()
            result = do_math(token, operand1, operand2)
            operand_stack.push(result)
            
    return operand_stack.pop()  # should be only value left, our final result
In [36]:
def do_math(op, op1, op2):
    if op == "*":
        return op1 * op2
    elif op == "/":
        return op1 / op2
    elif op == "+":
        return op1 + op2
    else:
        return op1 - op2
In [38]:
expr = "9 + 42 * ( 33 * 15 )"
infix_expr = infix_to_postfix2(expr)
print("with precedence:", infix_expr)
with precedence: 9 42 33 15 * * +
In [39]:
postfix_eval(infix_expr)
Out[39]:
20799