Evaluate Reverse Polish Notation medium

Problem Statement

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

Valid operators are +, -, *, /. 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. Initialize a stack: This stack will store operands (numbers).
2. Iterate through the tokens: For each token:
   • If it's a number: Push it onto the stack.
   • *If it's an operator (+, -, , /): Pop the top two operands from the stack (let's call them operand2 and operand1, where operand1 is the topmost element). Perform the operation (operand1 operator operand2). Push the result back onto the stack.
3. After iterating through all tokens: The final result will be the only element remaining in the stack.

Explanation

The algorithm uses a stack to efficiently handle the evaluation of the RPN expression. RPN (Reverse Polish Notation) is also known as postfix notation. The operators appear after their operands. This eliminates the need for parentheses and operator precedence rules. The stack naturally handles the order of operations as we process the tokens from left to right. When an operator is encountered, the stack provides the necessary operands in the correct order.

Code (C++)

#include <iostream>
#include <stack>
#include <string>
#include <vector>

using namespace std;

int evalRPN(vector<string>& tokens) {
    stack<long long> s; // Use long long to handle potential integer overflow

    for (const string& token : tokens) {
        if (isdigit(token[0]) || (token.length() > 1 && token[0] == '-' && isdigit(token[1]))) { //Check for negative numbers as well
            s.push(stoll(token)); // Convert string to long long and push onto stack
        } else {
            long long operand2 = s.top(); s.pop();
            long long operand1 = s.top(); s.pop();

            if (token == "+") {
                s.push(operand1 + operand2);
            } else if (token == "-") {
                s.push(operand1 - operand2);
            } else if (token == "*") {
                s.push(operand1 * operand2);
            } else if (token == "/") {
                s.push(operand1 / operand2); // Integer division
            }
        }
    }
    return s.top();
}

int main() {
    vector<string> tokens1 = {"2", "1", "+", "3", "*"};
    cout << "Example 1: " << evalRPN(tokens1) << endl; // Output: 9

    vector<string> tokens2 = {"4", "13", "5", "/", "+"};
    cout << "Example 2: " << evalRPN(tokens2) << endl; // Output: 6

    vector<string> tokens3 = {"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"};
    cout << "Example 3: " << evalRPN(tokens3) << endl; //Output: 22

    return 0;
}

Complexity

• Time Complexity: O(n), where n is the number of tokens. We iterate through the tokens once. Stack operations (push and pop) take constant time on average.
• Space Complexity: O(n) in the worst case, where n is the number of tokens. The stack could potentially hold all the operands if the expression consists only of numbers and no operators until the end. In the best case (all operators at the end), space complexity will be O(1) because we only need to store the operands for the final operation.