How to Evaluate Postfix Expression

Introduction to Postfix Expression

  • An operator is printed after its operands in a postfix expression.
  • In postfix notation, the infix expression 2+3 equals 23+.
  • Operations on postfix expressions are conducted in the sequence in which they are printed (left to right).
  • There is no need for brackets. In postfix notation, the infix expression 2+3*4 equals 234*+.
  • In postfix notation, the infix expression 3*4+2*5 converts to 34*25*+.

342+*5* is the infix expression for 3*(4+2)*5.

Evaluation of Postfix Expressions

2+3*4 (infix)   ----- >   234*+ (postfix) expression.

Notice:

  • In both expressions, the operands (2,3, and 4) appear in the same order.
  • The operators (* and +) appear in the order that they are performed in the postfix version — the multiplication comes before the addition. Writing the operators in the order that they are conducted makes postfix expressions convenient to analyze using the algorithm method:
  • Scan the expression from left to right until you come across an operator, @ (@ stands for + - * or /).
  • Carry out the operation @. The operands come before the operator, which is 3 4 + = 3+4= 7.
  • Substitute @ and its operands with the computed value in the expression.
  • Repeat steps 1-3 until no more operators are accessible.

Parentheses are not required in postfix notation.

  • "Stack-based postfix evaluation" Scan the string from left to right.
  • When you come across an operand, place it on the stack; when you come across an operator, remove the corresponding operands from the stack, perform the operation, and place the result back on the stack.
  • When you finish searching the expression, the value obtained is still on the stack.

Contemplate the postfix expression 234*+ as an example.

Input

Stack

Postfix evaluation

2 3 4 * +

empty

Push 2 into stack

3 4 * +

2

Push 3 into stack

4 * +

3 2

Push 4 into stack

* +

4 3 2

Pop 4 &  pop 3 from stack and  do 3 *4 , push 12 into stack

+

12 2

Pop 12 &  Pop 2 from stack do 2 + 12, push 14 into stack 


14


Input

Stack

Postfix evaluation

3 4 * 2 5 * +

empty

Push 3 into stack 

4 * 2 5 * +

3

Push 4 into stack

* 2 5 * +

4 3

Pop 4 & pop 3 from stack  do 3*4, Push 12

2 5 * +

12

Push 2  into stack

5 * +

2 12

Push 5  into stack

* +

5 2 12

Pop 5, Pop 2 from stack  do 2*5, Push 10  into stack

+

10 12

Pop 10 & Pop 12 from stack  do 12 + 10, push 22 into stack


22


An algorithm for evaluating postfix expressions is provided below :-

  • Make a few simplifying assumptions to eliminate some unnecessary and non-instructive details:
  • All of the numbers entered are single digits (0..9).
  • The input string contains no whitespace. Thus, 345+* is correct, but 345+* is not.
  • The only allowed operators are +,-,*, and /, where / represents integer division.

All of the input data is correct.

Thus, a typical input string is 23*73/+, which is 2*3 + 7/3 in infix notation (value is 8).

Making these assumptions, the algorithm for postfix evaluation is :

  • Read a character
  • Convert to int and push
  • If the character is an operator pop the stack twice to obtain two operands
  • Push the outcome of operation
  • Remove the final value from the stack

How to convert Infix to postfix :

While characters are still present in the infix string:

Read the given character from the infix string

>> If the character is an operand, append the character to the postfix expression.

>> If the character is an operator @, pop the stack and append the operator to the postfix expression if the stack is not empty and an operator of greater or equal priority is on the stack.

>> If the character is a left parenthesis (push the parenthesis onto the stack if the character is a right parenthesis) and the top of the stack does not contain a matching left parenthesis (pop the stack and append the operator to postfix pop the stack and discard the returned left parenthesis)>> Append to postfix any remaining items on the stack.

Examples

Input

Stack

Postfix evaluation

2*3 + 4*5

Nothing in stack


*3+4*5

Nothing in stack

2

3+4*5

*

2

+4*5

*

23

4*5

+

23*

*5

+

23*4

5

*+

23*4


*+

23*45


+

23*45*


Nothing in stack

23*45*+

Input

Stack

Postfix evaluation

2-3+4-5*6

Nothing in stack


-3+4-5*6

Nothing in stack

2

3+4-5*6

-

2

+4-5*6

-

23

4-5*6

+

23-

-5*6

+

23-4

5*6

-

23-4+

*6

-

23-4+5

6

*-

23-4+5


*-

23-4+56


-

23-4+56*


Nothing in stack

23-4+56*-

Input

Stack

Postfix evaluation

(2-3+4)*(5+6*7)

Nothing in stack


2-3+4)*(5+6*7)

(


-3+4)*(5+6*7)

(

2

3+4)*(5+6*7)

(-

2

+4)*(5+6*7)

(-

23

4)*(5+6*7)

(+

23-

)*(5+6*7)

(+

23-4

*(5+6*7)

Nothing in stack

23-4+

(5+6*7)

*

23-4+

5+6*7)

(*

23-4+

+6*7)

(*

23-4+5

6*7)

+(*

23-4+5

*7)

+(*

23-4+56

7)

*+(*

23-4+56

)

*+(*

23-4+567


*

23-4+567*+


  Nothing in stack

23-4+567*+*

Steps for evaluating postfix expression :

1. In the post variable, acknowledge postfix expression string.

2.  

For i in post:
    If i is an operand:
        Push i in stack.
    Else:
        Pop two elements from stack e.g. X and Y
        Perform operation with current operator on both the parents i.e X i Y
        Push the result back into the stack.
End for loop.

3. Finally, remove the result from the stack and store it.

CODE IN PYTHON

class evaluate_postfix:
    def __init__(self):
        self.items=[]
        self.size=-1
    def isEmpty(self):
        return self.items==[]
    def push(self,item):
        self.items.append(item)
        self.size+=1
    def pop(self):
        if self.isEmpty():
            return 0
        else:
            self.size-=1
            return self.items.pop()
    def seek(self):
        if self.isEmpty():
            return False
        else:
            return self.items[self.size]
    def evalute(self,expr):
        for i in expr:
            if i in '0123456789':
                self.push(i)
            else:
                op1=self.pop()
                op2=self.pop()
                result=self.cal(op2,op1,i)
                self.push(result)
        return self.pop()
    def cal(self,op2,op1,i):
        if i is '*':
            return int(op2)*int(op1)
        elif i is '/':
            return int(op2)/int(op1)
        elif i is '+':
            return int(op2)+int(op1)
        elif i is '-':
            return int(op2)-int(op1)
s=evaluate_postfix()
expr=input('enter the postfix expression')
value=s.evalute(expr)
print('the result of postfix expression',expr,'is',value)

write your code here: Coding Playground