Evaluate Reverse Polish Notation LeetCode Solution

Table of Contents

Problem Statement

Evaluate Reverse Polish Notation LeetCode Solution – Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, and /. Each operand may be an integer or another expression.

Note that the division between two integers should truncate toward zero.

It is guaranteed that the given RPN expression is always valid. That means the expression would always evaluate a result, and there will not be any division by zero operation.

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Explanation

As we evaluate postfix expression manually we’ll follow the same approach of using a stack and performing an operation based on whether the current token is an operator or an operand.

Evaluating a postfix expression is even easier than evaluating a normal expression because you don’t have to worry about operator precedence.
The structure of postfix expression is as follows:
ab*, where a and b can be operands, or expressions themselves, and * is an operator.

So our task is to first evaluate a, then b, then combine them as (a * b).
This can be done easily using a stack.
We iterate over the whole string while maintaining a stack of operands, following this algorithm:

If the current token is an operation, go to step 2, else go to step 4
Pop the first two elements from the stack. They will be b and a respectively (as the order of the operands is reversed due to the stack).
Perform the requisite operation (a * b), and push the result back to the stack. go to step 5.
Push the integer representation of the current token to the stack.
Repeat steps 1 to 4 until the whole tokens array is traversed.
Return the top element of the stack.

Code

C++ Code for Evaluate Reverse Polish Notation

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        unordered_map<string, function<int (int, int) > > map = {
            { "+" , [] (int a, int b) { return a + b; } },
            { "-" , [] (int a, int b) { return a - b; } },
            { "*" , [] (int a, int b) { return a * b; } },
            { "/" , [] (int a, int b) { return a / b; } }
        };
        std::stack<int> stack;
        for (string& s : tokens) {
            if (!map.count(s)) {
                stack.push(stoi(s));
            } else {
                int op1 = stack.top();
                stack.pop();
                int op2 = stack.top();
                stack.pop();
                stack.push(map[s](op2, op1));
            }
        }
        return stack.top();
    }
};

Java Code for Evaluate Reverse Polish Notation

import java.util.Stack;

public class Solution {
    public int evalRPN(String[] tokens) {
        int a,b;
    Stack<Integer> S = new Stack<Integer>();
    for (String s : tokens) {
      if(s.equals("+")) {
        S.add(S.pop()+S.pop());
      }
      else if(s.equals("/")) {
        b = S.pop();
        a = S.pop();
        S.add(a / b);
      }
      else if(s.equals("*")) {
        S.add(S.pop() * S.pop());
      }
      else if(s.equals("-")) {
        b = S.pop();
        a = S.pop();
        S.add(a - b);
      }
      else {
        S.add(Integer.parseInt(s));
      }
    }	
    return S.pop();
  }
}

Python Code for Evaluate Reverse Polish Notation

class Solution:
    # @param {string[]} tokens
    # @return {integer}
    def __init__(self):
        self.operators = {
            '+': lambda y, x: x + y,
            '-': lambda y, x: x - y,
            '*': lambda y, x: x * y,
            '/': lambda y, x: int(operator.truediv(x, y))
        }

    def evalRPN(self, tokens):
        if not tokens:
            return 0

        stack = []

        for token in tokens:
            if token in self.operators:
                stack.append(self.operators[token](stack.pop(), stack.pop()))
            else:
                stack.append(int(token))

        return stack[0]