150. Evaluate Reverse Polish Notation

Intuition

Reverse Polish Notation (RPN) is a mathematical notation in which every operator follows all of its operands. It is also known as postfix notation. To evaluate an expression in RPN, a stack is used to store operands, and operators are applied to the operands in the correct order. This approach naturally fits the stack data structure, as it allows easy management of operands and operators.

Approach

1. Initialization: - Use a stack to keep track of the operands as we iterate through the tokens.
2. Iteration: - For each token in the input tokens: - If the token is an operand (a number), push it onto the stack. - If the token is an operator (+, -, *, /), pop the top two operands from the stack, apply the operator, and push the result back onto the stack.
3. Operations: - When an operator is encountered, pop the top two elements from the stack. Let val2 be the first popped element and val1 be the second. - Apply the operator to val1 and val2: - For +, push val1 + val2. - For -, push val1 - val2. - For *, push val1 * val2. - For /, push int(val1 / val2) to ensure truncation towards zero.
4. Final Result: - After processing all tokens, the stack will contain a single element, which is the result of the RPN expression.

Complexity

Time Complexity:

• The time complexity is O(n), where n is the number of tokens. Each token is processed exactly once.

Space Complexity:

• The space complexity is O(n) in the worst case, where n is the number of tokens. The stack size can grow up to n/2 in the case of alternating operands and operators.

Code

C++

class Solution {
public:
    int evalRPN(vector& tokens) {
        stack stack;
        for (const string& token : tokens) {
            if (isdigit(token.back())) {
                stack.push(stoi(token));
            } else {
                int val2 = stack.top();
                stack.pop();
                int val1 = stack.top();
                stack.pop();
                int result;
                switch (token[0]) {
                    case '*':
                        result = val1 * val2;
                        break;
                    case '+':
                        result = val1 + val2;
                        break;
                    case '-':
                        result = val1 - val2;
                        break;
                    case '/':
                        result = val1 / val2;
                        break;
                }
                stack.push(result);
            }
        }
        return stack.top();
    }
};

Python

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for token in tokens:
            if token.lstrip('-').isdigit():
                stack.append(int(token))
            else:
                val2 = stack.pop()
                val1 = stack.pop()
                if token == '*':
                    stack.append(val1 * val2)
                elif token == '+':
                    stack.append(val1 + val2)
                elif token == '-':
                    stack.append(val1 - val2)
                elif token == '/':
                    stack.append(int(val1 / val2))
        return stack.pop()

Java

class Solution {
    public int evalRPN(String[] tokens) {
        Stack stack = new Stack<>();
        for (String token : tokens) {
            if (isNumeric(token)) {
                stack.push(Integer.parseInt(token));
            } else {
                int val2 = stack.pop();
                int val1 = stack.pop();
                int result;
                switch (token) {
                    case "*":
                        result = val1 * val2;
                        break;
                    case "+":
                        result = val1 + val2;
                        break;
                    case "-":
                        result = val1 - val2;
                        break;
                    case "/":
                        result = val1 / val2;
                        break;
                    default:
                        throw new IllegalArgumentException("Invalid operator: " + token);
                }
                stack.push(result);
            }
        }
        return stack.pop();
    }
    private boolean isNumeric(String str) {
        try {
            Integer.parseInt(str);
            return true;
        } catch (NumberFormatException e) {
            return false;
        }
    }
}

JavaScript

var evalRPN = function (tokens) {
    let stack = [];
    for (let i = 0; i < tokens.length; i++) 
    {
        let val = Number(tokens[i]);
        if (!isNaN(val)) {
            stack.push(val)
        } else {
            let val = stack.pop();
            let val1 = stack.pop();
            switch (tokens[i]) {
                case '*':
                    out = val1 * val
                    break;
                case '+':
                    out = val1 + val
                    break;
                case '-':
                    out = val1 - val
                    break;
                case '/':
                    out = Math.trunc(val1 / val)
                    break;

            }
            stack.push(out)
        }
    }
    return stack.pop()
};