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

Evaluation of Postfix Expression


Difficulty Level Medium
Frequently asked in Amazon Oracle
Stack

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  Reverse a stack without using extra space in O(n)

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  Check if Two Expressions With Brackets are Same

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
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!! You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Anisha was able to crack Amazon after practicing questions from TutorialCup