Evaluate Reverse Polish Notation medium

Problem Statement

Evaluate the value of an arithmetic expression in Reverse Polish Notation (RPN).

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

Note:

• Division between two integers should truncate toward zero.
• The given RPN expression is always valid. That means the expression would always evaluate to a result and there won't be any divide by zero operation.

Example 1

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

Example 2

Input: tokens = ["4","13","5","/","+"] Output: 6 Explanation: (4 + (13 / 5)) = 4 + 2 = 6

Steps

1. Use a Stack: We'll utilize a stack to store operands.
2. Iterate through Tokens: Process each token in the input array.
3. Operand: If the token is a number (integer), push it onto the stack.
4. Operator: If the token is an operator (+, -, *, /), pop the top two operands from the stack. Perform the corresponding operation, and push the result back onto the stack.
5. Final Result: After processing all tokens, the only element remaining on the stack will be the final result.

Explanation

The algorithm follows the order of operations implicitly because of the nature of RPN. Operators are applied only after their operands are available on the stack. The stack's LIFO (Last-In, First-Out) property ensures the correct order.

Code (C#)

using System;
using System.Collections.Generic;

public class Solution {
    public int EvalRPN(string[] tokens) {
        Stack<int> stack = new Stack<int>();

        foreach (string token in tokens) {
            if (int.TryParse(token, out int num)) {
                stack.Push(num);
            } else {
                int operand2 = stack.Pop();
                int operand1 = stack.Pop();
                int result = 0;

                switch (token) {
                    case "+":
                        result = operand1 + operand2;
                        break;
                    case "-":
                        result = operand1 - operand2;
                        break;
                    case "*":
                        result = operand1 * operand2;
                        break;
                    case "/":
                        result = operand1 / operand2; // Integer division
                        break;
                }
                stack.Push(result);
            }
        }
        return stack.Pop();
    }
}

Complexity

• Time Complexity: O(n), where n is the number of tokens. We iterate through the tokens once.
• Space Complexity: O(n) in the worst case, where n is the number of tokens. This is because the stack can hold up to n/2 elements (in the case of an expression with many operands and few operators). In practice, the space used might be less than O(n), depending on the expression.