7. Evaluation of Postfix expression

Evaluation of postfix expression using stack.¶

1. Scan the expression from left to right.
2. If we encounter any operand in the expression, then we push the operand in the stack.
3. When we encounter any operator in the expression, then we pop the corresponding operands from the stack.
4. When we finish with the scanning of the expression, the final value remains in the stack.

Ref

1. https://www.javatpoint.com/convert-infix-to-postfix-notation

In [1]:

postfix_expression1 = '2 3 4 * +'
postfix_expression2 = '3 4 * 2 5 * +'
postfix_expression3 = '2 3 1 * + 9 -'
postfix_expression4 = '5 3 + 6 2 / * 3 5 * +'
postfix_expression5 = '2 3 4 * + 16 2 3 ^ / -'


postfix_expression1 = postfix_expression1.split()
postfix_expression2 = postfix_expression2.split()
postfix_expression3 = postfix_expression3.split()
postfix_expression4 = postfix_expression4.split()
postfix_expression5 = postfix_expression5.split()

postfix_expression1 = '2 3 4 * +' postfix_expression2 = '3 4 * 2 5 * +' postfix_expression3 = '2 3 1 * + 9 -' postfix_expression4 = '5 3 + 6 2 / * 3 5 * +' postfix_expression5 = '2 3 4 * + 16 2 3 ^ / -' postfix_expression1 = postfix_expression1.split() postfix_expression2 = postfix_expression2.split() postfix_expression3 = postfix_expression3.split() postfix_expression4 = postfix_expression4.split() postfix_expression5 = postfix_expression5.split()

In [2]:

def postfix_expression_evaluation(expression):
    operators = ["+", "-", "*", "/", "^"]
    stack = [] 
    for i in expression:
        if i in operators:
            a = stack.pop()
            b = stack.pop()
            s = b + i + a
            print(s)
            if i == "^":
                i = "**"
            ans = eval(b + i + a)
            print("pushing {} onto stack".format(ans))
            stack.append(str(ans))
        else:
            print("pushing {} onto stack".format(i))
            stack.append(i)
    
    return float(stack[-1])

def postfix_expression_evaluation(expression): operators = ["+", "-", "*", "/", "^"] stack = [] for i in expression: if i in operators: a = stack.pop() b = stack.pop() s = b + i + a print(s) if i == "^": i = "**" ans = eval(b + i + a) print("pushing {} onto stack".format(ans)) stack.append(str(ans)) else: print("pushing {} onto stack".format(i)) stack.append(i) return float(stack[-1])

In [3]:

postfix_expression_evaluation(postfix_expression1)

postfix_expression_evaluation(postfix_expression1)

pushing 2 onto stack
pushing 3 onto stack
pushing 4 onto stack
3*4
pushing 12 onto stack
2+12
pushing 14 onto stack

Out[3]:

14.0

In [4]:

postfix_expression_evaluation(postfix_expression2)

postfix_expression_evaluation(postfix_expression2)

pushing 3 onto stack
pushing 4 onto stack
3*4
pushing 12 onto stack
pushing 2 onto stack
pushing 5 onto stack
2*5
pushing 10 onto stack
12+10
pushing 22 onto stack

Out[4]:

22.0

In [5]:

postfix_expression_evaluation(postfix_expression3)

postfix_expression_evaluation(postfix_expression3)

pushing 2 onto stack
pushing 3 onto stack
pushing 1 onto stack
3*1
pushing 3 onto stack
2+3
pushing 5 onto stack
pushing 9 onto stack
5-9
pushing -4 onto stack

Out[5]:

-4.0

In [6]:

postfix_expression_evaluation(postfix_expression4)

postfix_expression_evaluation(postfix_expression4)

pushing 5 onto stack
pushing 3 onto stack
5+3
pushing 8 onto stack
pushing 6 onto stack
pushing 2 onto stack
6/2
pushing 3.0 onto stack
8*3.0
pushing 24.0 onto stack
pushing 3 onto stack
pushing 5 onto stack
3*5
pushing 15 onto stack
24.0+15
pushing 39.0 onto stack

Out[6]:

39.0

In [7]:

postfix_expression5

postfix_expression5

Out[7]:

['2', '3', '4', '*', '+', '16', '2', '3', '^', '/', '-']

In [8]:

postfix_expression_evaluation(postfix_expression5)

postfix_expression_evaluation(postfix_expression5)

pushing 2 onto stack
pushing 3 onto stack
pushing 4 onto stack
3*4
pushing 12 onto stack
2+12
pushing 14 onto stack
pushing 16 onto stack
pushing 2 onto stack
pushing 3 onto stack
2^3
pushing 8 onto stack
16/8
pushing 2.0 onto stack
14-2.0
pushing 12.0 onto stack

Out[8]:

12.0

In [ ]: