How to Evaluate Postfix Expression

Board Infinity

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
23 + 45	Nothing in stack
3+45	Nothing in stack	2
3+4*5	*	2
+4*5	*	23
4*5	+	23*
*5	+	23*4
5	*+	23*4
	*+	23*45
	+	2345
	Nothing in stack	2345+

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+67)	Nothing in stack
2-3+4)(5+67)	(
-3+4)(5+67)	(	2
3+4)(5+67)	(-	2
+4)(5+67)	(-	23
4)(5+67)	(+	23-
)(5+67)	(+	23-4
(5+67)	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.

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

How to Evaluate Postfix Expression

Board Infinity

Advanced Algorithms and Problem Solving Techniques

How To Start Competitive Programming - A Complete Guide

A Quick Guide to Breadth-First Search

Depth First Search (DFS) with Explanation and Code

Difference Between BFS and DFS (with code and diagrams)

How to Perform Level Order Traversal?

A Quick Guide to Backtracking Algorithm

Solving N Queens Problem using Backtracking

Quick Guide to Divide and Conquer Algorithm

Longest Increasing Subsequence Problem

Quick Note - Greedy Programming v/s Dynamic Programming

Coin Change Problem: DP and Recursion Approach

A Definitive Guide to Knapsack Problem

How to Solve Subset Sum Problem?

Understanding Huffman Coding in detail

Understand the working of KMP Algorithm

Longest Common Substring Problem

Longest Common Subsequence problem: solved

A Quick Guide to Manacher's Algorithm

Learning About Bipartite Graphs

Graph Coloring Problem: Explained

Detect Cycle in Direct Graph

Directed Acyclic Graph: Representation

Prim's Algorithm: Explanation, Code, and Applications

Working of Kruskal's Algorithm

Prims and Kruskal algorithm for Maximum Spanning Tree

Bellman Ford Algorithm in detail with code

Floyd-Warshall Algorithm and its Implementation

Understand Travelling Salesman Problem

Branch And Bound Algorithm: Explained

How to Evaluate Postfix Expression

Introduction to Round-Robin Scheduling

Disjoint set (Union find Algorithm)

State Space Reduction in Algorithms

Apriori Algorithm

What is A* Search Algorithm?

Introduction to Postfix Expression

Evaluation of Postfix Expressions

How to convert Infix to postfix :

CODE IN PYTHON