Postfix notation (also known as Reverse Polish Notation) is a way to represent an expression, where operators follow their corresponding operands. Evaluating an expression represented as postfix notation can easily be done using the stack data structure.
Scope
 In this article, the concept of the Polish postfix notation (or simply postfix notation) has been discussed briefly along with some examples.
 An algorithm that mainly uses the stack data structure has been shown to evaluate postfix expression.
Takeaways
 Stack data structure is used to efficiently evaluate Postfix Expression.
 Time and Space complexity for evaluating postfix expression using stack are
 Time complexity – $O(N)$
 Space complexity – $O(N)$
Introduction
Postfix notation is one of the few ways to represent algebraic expressions. It is used in computers because it is faster than other types of notations (such as infix notation) as parentheses are not required to represent them.
As the name suggests, in the postfix expression operators follow their operands. Therefore, the process of postfix evaluation is quite different than solving the infix notation (normal notation used in daily use).
InputOutput
Input – A string consisting of numeric values along with operator symbols (*, /, +, 
, etc) is given as the input.
Output – The result obtained by solving the given input is required to be printed.
Examples of Postfix Expression Evaluation
Example 1 –
Input – $ 2 3 * 4 5 + * $
Output – $ 54 $
Example 2 –
Input – $ 5 2 3 * * $
Output – $ 30 $
Algorithm of Postfix Expression Evaluation
As we have discussed earlier, the operators follow their operands in the postfix expression. Hence, for the postfix evaluation we will use the Stack
data structure.
We know that the stack data structure works on the last in first out (LIFO) principle. Therefore, previously encountered operands can easily be accessed using the stack.
The algorithm for evaluation of postfix expression is as follows –
 Create a stack that holds integer type data to store the operands of the given postfix expression. Let it be
st
.  Iterate over the string from left to right and do the following –
 If the current element is an operand, push it into the stack.
 Otherwise, if the current element is an operator (say
/
)do the following – Pop an element from
st
, let it beop1
.  Pop another element from
st
, let it beop2
.  Computer the result of
op2 / op1
, and push it into the stack.
Note the order $i.e.$op2 / op1
should not be changed otherwise it will affect the final result in some cases.
 Pop an element from
 At last,
st
will consist of a single element $i.e.$ the result after evaluating the postfix expression.
How to Evaluate a Postfix Expression Using Stack?
We have discussed the algorithm that uses the stack for postfix evaluation. Now we dry run the above algorithm to make the concept crystal clear.
Let the the postfix expression be "10 22 + 8 / 6 * 5 +"
. Now, proceeding as per the algorithm –
 Create a stack (say
st
).  Now since the first element is an operand, so we will push it in the stack $i.e.$
st.push(10)
. After which stack looks like –
st

:–:
10   Now we traverse further in the postfix expression and found that the next element is again an operand. So, we will push it into the stack, after which the stack will look like –
st

:–:
22 
10   The next element of the expression is an operator (
+
operator) so we will do the following – Pop an element (say
op1
) from the stack. Hereop1 = 22
.  Pop another element (say
op2
) from the stack. Hereop2 = 10
.  Now, we will compute
op2 + op1
which is32
, and push it into the stack.
After this step stack will look like –
 Pop an element (say
 On traversing further in the expression string, we found next element is an operand. So we will push it into the stack.
Upon doing this, the stack will look like –
st
:–:
8
32   The next element is the
/
operator, so we will do the following – Pop an element (say
op1
) from the stack. Hereop1 = 8
.  Pop another element (say
op2
) from the stack. Hereop2 = 32
.  Now, we will compute
op2 / op1
which is4
, and push it into the stack.
After this step stack will look like –
 Pop an element (say
 The next element is an operand, hence pushing it in the stack.
After this step stack will look like –
st
:–:
6
4   The next element is the
*
operator, hence we need to perform the following steps – Pop an element (say
op1
) from the stack. Hereop1 = 6
.  Pop another element (say
op2
) from the stack. Hereop2 = 4
.  Now, we will compute
op2 * op1
which is24
, and push it into the stack.
After this step stack will look like –
st
24  Pop an element (say
 The next operator is an operand, hence pushing it into the stack. Upon doing which stack will look like –
st
:–:
5
24   The last element is the
+
operator. Hence it is required to do the following steps – Pop an element (say
op1
) from the stack. Hereop1 = 5
.  Pop another element (say
op2
) from the stack. Hereop2 = 24
.  Now, we will compute
op2 + op1
which is29
, and push it into the stack.
After this step stack will look like –
 Pop an element (say
 Now, we have traversed the given postfix expression, and hence as per the algorithm the only element remaining in the stack i.e.
29
is the result we get on evaluating the postfix expression.
Implementation of the Algorithm
Java Implementation
import java.util.*;
public class Main{
// Function to evaluate the postfix expression
static int evaluatePostfixExpression(char[] expression) {
// Defining an stack of integer type.
Stack<Integer> st=new Stack<>();
// Traversing in the expression from left
// to right.
for (int i = 0; i < expression.length; i++){
char c = expression[i];
// If 'c' is a digit (operand)
if (c >= '0' && c <= '9'){
// Convert 'c' in integer and
// push it into the stack.
int temp = (int)(c  '0');
st.push(temp);
}
// Otherwise it is an operator.
else{
// Pop element from the stack.
int op1 = st.pop();
// Pop another element from the stack.
int op2 = st.pop();
// Use the switch case to deal with
// the operand accordingly.
switch(c){
case '+':
st.push(op2 + op1);
break;
case '':
st.push(op2  op1);
break;
case '*':
st.push(op2 * op1);
break;
case '/':
st.push(op2 / op1);
break;
}
}
}
// Return the element at the top
// of the stack.
return st.peek();
}
// Main function
public static void main(String[] args) {
// Postfix expression.
String expression = "23*45+*";
// Calling function to find the result
// of the postfix expression.
System.out.println(
evaluatePostfixExpression(expression.toCharArray()));
}
}
Output –
54
C++ Implementation
#include<bits/stdc++.h>
using namespace std;
// Function to evaluate the postfix expression
int evaluatePostfixExpression(string expression) {
// Defining an stack of integer type.
stack<int> st;
// Traversing in the expression from left
// to right.
for (int i = 0; i < expression.length(); i++){
char c = expression[i];
// If 'c' is a digit (operand)
if (c >= '0' && c <= '9'){
// Convert 'c' in integer and
// push it into the stack.
int temp = (int)(c  '0');
st.push(temp);
}
// Otherwise it is an operator.
else{
// Pop element from the stack.
int op1 = st.top();
st.pop();
// Pop another element from the stack.
int op2 = st.top();
st.pop();
// Use the switch case to deal with
// the operand accordingly.
switch(c){
case '+':
st.push(op2 + op1);
break;
case '':
st.push(op2  op1);
break;
case '*':
st.push(op2 * op1);
break;
case '/':
st.push(op2 / op1);
break;
}
}
}
// Return the element at the top
// of the stack.
return st.top();
}
// Main function
int main() {
// Postfix expression.
string expression = "23*45+*";
// Calling function to find the result
// of the postfix expression.
cout <<
evaluatePostfixExpression(expression) << endl;
}
Output –
54
Python Implementation
# Function to evaluate the postfix expression
def evaluatePostfixExpression(expression):
# Defining an stack of integer type.
st = []
# Traversing in the expression from left
# to right.
for i in range(len(expression)):
c = expression[i]
# If 'c' is a digit (operand)
if (c >= '0' and c <= '9'):
# Convert 'c' in integer and
# push it into the stack.
temp = int(c)
st.append(temp)
# Otherwise it is an operator.
else:
# Pop element from the stack.
op1 = st.pop()
# Pop another element from the stack.
op2 = st.pop()
# Use the if else ladder to deal with
# the operand accordingly.
if (c == '+'):
st.append(op2 + op1)
elif (c == ''):
st.append(op2  op1)
elif (c == '*'):
st.append(op2 * op1)
elif (c == '/'):
st.append(op2 / op1)
# Return the element at the top
# of the stack.
return st.pop()
# Driver code
# Postfix expression.
expression = "23*45+*"
# Calling function to find the result
# of the postfix expression.
print(evaluatePostfixExpression(expression))
Output –
54
Complexity Analysis
Time Complexity – Since, we are traversing the expression once, which costs $O(n)$ time. Therefore the overall time complexity of postfix evaluation is $O(n)$.
Space Complexity – The maximum number of elements in our stack can reach up to $O(n)$ in the worst case. The space complexity is $O(n)$.
A Limitation of the Previous Approach
While implementing the previous approach, we are not taking care of the following two cases –
 If the given postfix expression itself is invalid.
 If the operands in expression are of two or more digits.
To handle these cases, we need to make some minor changes in the code which are as follows –
 If while popping out any element we found that the stack is already empty. It indicates that the given postfix expression is invalid.
 If the expression contains operands with two or more digits, all of them must be separated by blank space. Therefore, for each element, we need to calculate its value.
Java Implementation
import java.util.*;
public class Main{
// Function to evaluate the postfix expression
static int evaluatePostfixExpression(char[] expression) {
// Defining an stack of integer type.
Stack<Integer> st=new Stack<>();
// Traversing in the expression from left
// to right.
int i = 0;
while (i < expression.length){
char c = expression[i];
// If the current character is space
// increase the index and continue.
if (c == ' '){
i++;
continue;
}
// Else if 'c' is a digit (operand)
else if (c >= '0' && c <= '9'){
// Find the value of current operand.
int val = 0;
while (expression[i]!=' '){
// Obtain the value of current character
int temp = (int)(expression[i]  '0');
// Increase the val
val = 10 * val + temp;
// Increase the index;
i++;
}
// Push val into the stack.
st.push(val);
}
// Otherwise it is an operator.
else{
// Checking if the stack contain less than
// two elements, which means the expression
// is invalid.
if (st.size() < 2){
System.out.println("Given expression is invalid");
return Integer.MIN_VALUE;
}
// Pop element from the stack.
int op1 = st.pop();
// Pop another element from the stack.
int op2 = st.pop();
// Use the switch case to deal with
// the operand accordingly.
switch(c){
case '+':
st.push(op2 + op1);
break;
case '':
st.push(op2  op1);
break;
case '*':
st.push(op2 * op1);
break;
case '/':
st.push(op2 / op1);
break;
}
}
// Incrasing the index
i++;
}
// Return the element at the top
// of the stack.
return st.peek();
}
// Main function
public static void main(String[] args) {
// Postfix expression.
String expression = "10 22 + 8 / 6 * 5 +";
// Calling function to find the result
// of the postfix expression.
System.out.println(
evaluatePostfixExpression(expression.toCharArray()));
}
}
Output –
29
C++ Implementation
#include<bits/stdc++.h>
using namespace std;
// Function to evaluate the postfix expression
int evaluatePostfixExpression(string expression) {
// Defining an stack of integer type.
stack<int> st;
// Traversing in the expression from left
// to right.
int i = 0;
while (i < expression.length()){
char c = expression[i];
// If the current character is space
// increase the index and continue.
if (c == ' '){
i++;
continue;
}
// If 'c' is a digit (operand)
else if (c >= '0' && c <= '9'){
// Find the value of current operand.
int val = 0;
while (expression[i]!=' '){
// Obtain the value of current character
int temp = (int)(expression[i]  '0');
// Increase the val
val = 10 * val + temp;
// Increase the index;
i++;
}
// Push val into the stack.
st.push(val);
}
// Otherwise it is an operator.
else{
// Checking if the stack contain less than
// two elements, which means the expression
// is invalid.
if (st.size() < 2){
cout << "Given expression is invalid" << endl;
return INT_MIN;
}
// Pop element from the stack.
int op1 = st.top();
st.pop();
// Pop another element from the stack.
int op2 = st.top();
st.pop();
// Use the switch case to deal with
// the operand accordingly.
switch(c){
case '+':
st.push(op2 + op1);
break;
case '':
st.push(op2  op1);
break;
case '*':
st.push(op2 * op1);
break;
case '/':
st.push(op2 / op1);
break;
}
// Increasing the index
i++;
}
}
// Return the element at the top
// of the stack.
return st.top();
}
// Main function
int main() {
// Postfix expression.
string expression = "10 22 + 8 / 6 * 5 +";
// Calling function to find the result
// of the postfix expression.
cout <<
evaluatePostfixExpression(expression) << endl;
}
Output –
29
Python Implementation
# Function to evaluate the postfix expression
def evaluatePostfixExpression(expression):
# Defining an stack of integer type.
st = []
# Traversing in the expression from left
# to right.
i = 0
while (i < len(expression)):
c = expression[i]
# If the current character is space
# increase the index and continue.
if (c == ' '):
i+=1
continue
# If 'c' is a digit (operand)
elif (c >= '0' and c <= '9'):
# Find the value of current operand.
val = 0
while (expression[i]!=' '):
# Obtain the value of current character
temp = int(expression[i])
# Increase the val
val = 10 * val + temp
# Increase the index
i+=1
# Push val into the stack.
st.append(val)
# Otherwise it is an operator.
else:
# Checking if the stack contains less than
# two elements, which means the expression
# is invalid.
if (len(st) < 2):
print("Given expression is invalid")
return 9999999
# Pop element from the stack.
op1 = st.pop()
# Pop another element from the stack.
op2 = st.pop()
# Use the if else ladder to deal with
# the operand accordingly.
if (c == '+'):
st.append(op2 + op1)
elif (c == ''):
st.append(op2  op1)
elif (c == '*'):
st.append(op2 * op1)
elif (c == '/'):
st.append(op2 / op1)
# Increasing the index
i+=1
# Return the element at the top
# of the stack.
return st.pop()
# Driver code
# Postfix expression.
expression = "10 22 + 8 / 6 * 5 +"
# Calling function to find the result
# of the postfix expression.
print(evaluatePostfixExpression(expression))
Output –
29
Conclusion
 In postfix notation, the operator appears after the operands.
 It does not require the use of parentheses and therefore it is faster when compared to other notations.
 Stack data structure is used for evaluation of postfix expression efficiently.