# 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 :

• 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