Question

You are given an array of strings tokens that represents a valid arithmetic expression in Reverse Polish Notation.

Return the integer that represents the evaluation of the expression.

• The operands may be integers or the results of other operations.

• The operators include '+', '-', '*', and '/'.

• Assume that division between integers always truncates toward zero.

Example

Input: tokens = ["1","2","+","3","*","4","-"]

Output: 5

Explanation: ((1 + 2) * 3) - 4 = 5

Approach

In this problem, we have to find the result after doing mathematical operations on the integer string. Whenever there is an operators, we have to take previous two / top two elements and perform the operation and push the result back. To do this, we have to store these string in such a way that we can easily find the previous two elements for operations and easily push the result in the same data structure. To do this we can use stack. Just store the integers in the stack and if there is operator then perform the operation and push the result back. We only have to store the integer results.

Algorithm

1. Create a stack (empty array).

2. For index i from 0 to length of tokens:

   1. If the token is operator:

      1. Then pop the top two elements from stack and perform the operation and push the result in stack.

   2. Else

      1. Push the token in stack after converting it in number integer

3. After the loop, return the first element of stack.

Dry Run:

Solution (JS code)

class Solution {
    /**
     * @param {string[]} tokens
     * @return {number}
     */
    evalRPN(tokens) {
        const stack = [];
        for (const c of tokens) {
            if (c === '+') {
                stack.push(stack.pop() + stack.pop());
            } else if (c === '-') {
                const a = stack.pop();
                const b = stack.pop();
                stack.push(b - a);
            } else if (c === '*') {
                stack.push(stack.pop() * stack.pop());
            } else if (c === '/') {
                const a = stack.pop();
                const b = stack.pop();
                stack.push(Math.trunc(b / a));
            } else {
                stack.push(parseInt(c));
            }
        }
        return stack.pop();
    }
}

Time Complexity

O(n)

Space Complexity

O(n)