Home » Technical Interview Questions » Stack Interview Questions » Evaluation of Postfix Expression

Evaluation of Postfix Expression


Reading Time - 5 mins

In the Evaluation of the postfix expression problem, we have given a string s containing a postfix expression. Evaluate the given expression.

Evaluation of Postfix Expression

Example

Input : s = “231*+9-”

Output : -4

Input : s = “100 200 + 2 / 5 * 7 +”

Output : 757

For Operands Having Single Digits

Algorithm

  1. Initialize a string s containing postfix expression.
  2. Create a stack of the same size as that of the string.
  3. If there is no stack return -1. Else traverse through the string and check if the current character is a digit, push the digit in the stack.
  4. Else pop the top two elements in the stack. Apply the current character/operator on them and push their result in the stack.
  5. Return the top of the stack.

C++ Program for Evaluation of Postfix Expression

#include <iostream>  
#include <string.h>  
  
using namespace std; 
  
struct Stack{  
    int top;  
    unsigned capacity;  
    int* array;  
};  
  
struct Stack* createStack( unsigned capacity ){  
    struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));  
  
    if(!stack){ 
        return NULL;  
    }    
  
    stack->top = -1;  
    stack->capacity = capacity;  
    stack->array = (int*) malloc(stack->capacity * sizeof(int));  
  
    if(!stack->array){ 
        return NULL;
    }    
  
    return stack;  
}  
  
int isEmpty(struct Stack* stack){  
    return stack->top == -1 ;  
}  
  
char peek(struct Stack* stack){  
    return stack->array[stack->top];  
}  
  
char pop(struct Stack* stack){  
    if(!isEmpty(stack)){  
        return stack->array[stack->top--];
    }    
    return '$';  
}  
  
void push(struct Stack* stack, char op){  
    stack->array[++stack->top] = op;  
}  
  
  
int evaluatePostfix(char* exp){  
    
    struct Stack* stack = createStack(strlen(exp));  
    int i;  
  
    if(!stack){ 
        return -1;
    }    
  
    for(i = 0; exp[i]; ++i){  
        if(isdigit(exp[i])){  
            push(stack, exp[i] - '0');  
        } 
        else{  
            int val1 = pop(stack);  
            int val2 = pop(stack);  
            switch (exp[i]){  
                case '+': push(stack, val2 + val1); break;  
                case '-': push(stack, val2 - val1); break;  
                case '*': push(stack, val2 * val1); break;  
                case '/': push(stack, val2/val1); break;  
            }  
        }  
    }  
    return pop(stack);  
}  
  
int main(){
    
    char s[] = "231*+9-";  
    cout<<evaluatePostfix(s); 
    
    return 0;  
}
-4

Java Program for Evaluation of Postfix Expression

import java.util.Stack; 
  
class Postfix{ 
    
    static int evaluatePostfix(String exp){ 
        
        Stack<Integer> stack=new Stack<>(); 
          
        for(int i=0;i<exp.length();i++){ 
            char c=exp.charAt(i); 
              
            if(Character.isDigit(c)){ 
                stack.push(c - '0'); 
            }    
              
            else{ 
                int val1 = stack.pop(); 
                int val2 = stack.pop(); 
                  
                switch(c){ 
                    case '+': 
                        stack.push(val2+val1); 
                        break; 
                      
                    case '-': 
                        stack.push(val2- val1); 
                        break; 
                      
                    case '/': 
                        stack.push(val2/val1); 
                        break; 
                      
                    case '*': 
                        stack.push(val2*val1); 
                        break; 
                } 
            } 
        } 
        return stack.pop();     
    } 
      
    public static void main(String[] args){
        
        String s = "231*+9-"; 
        System.out.println(evaluatePostfix(s));
        
    } 
}
-4

Complexity Analysis

Time Complexity: O(n) where n is the size of the given string/expression.

READ  How to Implement Stack Using Priority Queue or Heap?

Auxiliary Space: O(n) because we used the stack space for n characters.

For Operands Having Multiple Digits

Algorithm

  1. Initialize a string s containing postfix expression.
  2. Create a stack of the same size as that of the string.
  3. If there is no stack return -1. Else traverse through the string and check if the current character is white space continues the loop.
  4. If the current character is a digit, check if it’s a number read the full number else read the digit and push the digit in the stack.
  5. Else pop the top two elements in the stack. Apply the current character/operator on them and push their result in the stack.
  6. Return the top of the stack.

C++ Program for Evaluation of Postfix Expression

#include <iostream>  
#include <string.h>  
  
using namespace std; 
  
class Stack{  
    public: 
        int top;  
        unsigned capacity;  
        int* array;  
};  
  
Stack* createStack( unsigned capacity ){  
    Stack* stack = new Stack(); 
  
    if(!stack){
        return NULL;
    }    
  
    stack->top = -1;  
    stack->capacity = capacity;  
    stack->array = new int[(stack->capacity * sizeof(int))];  
  
    if(!stack->array){ 
        return NULL;
    }    
  
    return stack;  
}  
  
int isEmpty(Stack* stack){  
    return stack->top == -1 ;  
}  
  
int peek(Stack* stack){  
    return stack->array[stack->top];  
}  
  
int pop(Stack* stack){  
    if(!isEmpty(stack)){  
        return stack->array[stack->top--];
    }    
    return '$';  
}  
  
void push(Stack* stack,int op){  
    stack->array[++stack->top] = op;  
}  
  
  
int evaluatePostfix(char* exp){  
    
    Stack* stack = createStack(strlen(exp));  
    int i;  
  
    if(!stack){ 
        return -1;
    }    
  
    for(i = 0; exp[i]; ++i){  
        if(exp[i] == ' '){
            continue;
        }    
          
        else if(isdigit(exp[i])){  
            int num=0;  
              
            while(isdigit(exp[i])){  
                num = num * 10 + (int)(exp[i] - '0');  
                i++;  
            }  
            
            i--;  
              
            push(stack,num);  
        }  
          
        else{  
            int val1 = pop(stack);  
            int val2 = pop(stack);  
              
            switch (exp[i]){  
                case '+':
                    push(stack, val2 + val1); 
                    break;  
                case '-': 
                    push(stack, val2 - val1); 
                    break;  
                case '*': 
                    push(stack, val2 * val1); 
                    break;  
                case '/': 
                    push(stack, val2/val1);
                    break;  
            }  
        }  
    }  
    return pop(stack);   
}  
  
int main(){
    
    char s[] = "100 200 + 2 / 5 * 7 +";  
    cout<<evaluatePostfix(s); 
    
    return 0;  
}
757

Java Program for Evaluation of Postfix Expression

import java.util.Stack; 
  
class Postfix{ 
    
    static int evaluatePostfix(String exp){ 
        
        Stack<Integer> stack = new Stack<>(); 
          
        for(int i = 0; i < exp.length(); i++){ 
            char c = exp.charAt(i); 
              
            if(c == ' '){ 
                continue;
            }
              
            else if(Character.isDigit(c)){ 
                int n = 0; 
                  
                while(Character.isDigit(c)){ 
                    n = n*10 + (int)(c-'0'); 
                    i++; 
                    c = exp.charAt(i); 
                } 
                
                i--; 
  
                stack.push(n); 
            } 
              
            else{ 
                int val1 = stack.pop(); 
                int val2 = stack.pop(); 
                  
                switch(c){ 
                    case '+': 
                        stack.push(val2+val1); 
                        break; 
                      
                    case '-': 
                        stack.push(val2- val1); 
                        break; 
                      
                    case '/': 
                        stack.push(val2/val1); 
                        break; 
                      
                    case '*': 
                        stack.push(val2*val1); 
                        break; 
                } 
            } 
        } 
        return stack.pop();  
    } 
      
    public static void main(String[] args){ 
        
        String s = "100 200 + 2 / 5 * 7 +"; 
        System.out.println(evaluatePostfix(s));
        
    } 
}
757

Complexity Analysis

Time Complexity: O(n) where n is the size of the given string/expression.

READ  Implement Stack using Queues

Auxiliary Space: O(n) because we used the stack space for n characters.

Reference1   reference2

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions