Given a postfix expression Containing only operators [+, – , *, / ]  and numbers. Postfix expression is given the form of a vector of strings. Each element is either operator or operand in postfix expression. Concatenating these strings gives the postfix expression. Evaluate the postfix expression and return the corresponding value of the expression.

NOTE:  Division between two integers should truncate toward zero.

Example:

Example 1: 
Input: [“ 1 ”, ” 3 ”,” - ”,” 4 ”, “ * ” ] 
Output: -8
Explanation: The Arthematic Expression Corresponding to postfix is (1-3)*4 which is equal to -8.

Example 2: 
Input: [“ 4 ”, ” 3 ”,” 15 ”,” / ”, “ - ” ] 
Output: 4 
Explanation: The Arthematic Expression Corresponding to postfix is( 4 + (3/15)) which is equal to 4.

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Algorithm:

1. We know that in postfix expression operator comes after the operand.
2. The Intuition is to iterate the postfix expression, When we find the number/operand push it into the stack
3. Whenever we encounter the operator, pop the last two numbers in the stack.
4. Apply the operation corresponding to the operator on the two numbers and push back the result obtained after performing operations on the numbers into the stack.
5. While applying the operation care should be taken. For operations like addition, and multiplication the order of the numbers doesn’t matter. But the order of numbers is important for subtraction and division.
6. The number popped second is the first number that encounters first in infix expression. So In subtraction first popped number is subtracted from the second popped number. Similarly, In division, the second popped number is divided by the first popped number.
7. After the iteration, there will be only one element left in the stack. Which is the value of the postfix expression.

Code:

#include <bits/stdc++.h>

using namespace std;

int EvalutePostfix(vector < string > & postfix) {
  stack < int > st;
  for (auto & token: postfix) {
    if (token == "+" || token == "-" || token == "*" || token == "/") {
      int first = st.top();
      st.pop();
      int second = st.top();
      st.pop();
      if (token == "+")
        st.push(first + second);
      else if (token == "-")
        st.push(second - first);
      else if (token == "*")
        st.push(first * second);
      else
        st.push(second / first);
    } else
      st.push(stoi(token));
  }
  return st.top();
}

int main() {
  vector < string > postfix = {"1","3","-","4","*"};
  int value = EvalutePostfix(postfix);
  cout << value << endl;
}

import java.util.*;

class TUF {
  static int EvalutePostfix(String[] postfix) {
    Stack < Integer > st = new Stack < > ();
    for (String token: postfix) {
      if (token == "+" || token == "-" || token == "*" || token == "/") {
        int first = st.peek();
        st.pop();
        int second = st.peek();
        st.pop();
        if (token == "+")
          st.push(first + second);
        else if (token == "-")
          st.push(second - first);
        else if (token == "*")
          st.push(first * second);
        else
          st.push(second / first);
      } else
        st.push(Integer.parseInt(token));
    }
    return st.peek();
  }

  public static void main(String args[]) {
    String postfix[] = {"1","3","-","4","*"};
    int value = EvalutePostfix(postfix);
    System.out.println(value);
  }
}

Special thanks to SaiSri Angajala for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article