algoadvance

Leetcode 150. Evaluate Reverse Polish Notation

Problem Statement

You need to 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 that division between two integers should truncate toward zero. The given RPN expression is always valid, i.e., it will always evaluate to a result, and there won’t be any division by zero operation.

Example

  1. Input: ["2","1","+","3","*"] Output: 9
    Explanation: ((2 + 1) * 3) = 9
  2. Input: ["4","13","5","/","+"] Output: 6
    Explanation: (4 + (13 / 5)) = 6
  3. Input: ["10","6","9","3","+","-11","*","/","*","17","+","5","+"] Output: 22
    Explanation:
    1. (10 * (6 / ((9 + 3) * -11))) + 17 + 5
    2. (10 * (6 / (12 * -11))) + 17 + 5
    3. (10 * (6 / -132)) + 17 + 5
    4. (10 * 0) + 17 + 5
    5. 0 + 17 + 5
    6. 22

Clarifying Questions

  1. Can operands be negative?
    • Yes, operands can be negative.
  2. What is the maximum length of the RPN expression?
    • The problem does not specify, assume inputs within typical constraints for LeetCode problems (e.g., up to 10^4 elements).
  3. Do we need to handle invalid RPN expressions?
    • No, you can assume that the input RPN expression is always valid.

Strategy

  1. Stack-Based Evaluation:
    • Use a stack to keep track of operands.
    • Iterate over each token in the RPN expression:
      • If the token is an operand, convert it to an integer and push it onto the stack.
      • If the token is an operator, pop the necessary operands from the stack, perform the operation, and push the result back onto the stack.
    • At the end of the iteration, the stack should contain exactly one element, which is the result of the RPN expression.

Time Complexity

Code

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

class Solution {
public:
    int evalRPN(std::vector<std::string>& tokens) {
        std::stack<int> s;
        
        for (const auto &token : tokens) {
            // if the token is an operator, pop two operands and calculate the result
            if (token == "+" || token == "-" || token == "*" || token == "/") {
                int b = s.top(); s.pop();
                int a = s.top(); s.pop();
                
                if (token == "+") s.push(a + b);
                else if (token == "-") s.push(a - b);
                else if (token == "*") s.push(a * b);
                else if (token == "/") s.push(a / b); // using integer division
            } else {
                // if the token is an operand, push it onto the stack
                s.push(std::stoi(token));
            }
        }
        
        // the result of the RPN expression will be the last remaining element in the stack
        return s.top();
    }
};

// Sample test
int main() {
    Solution sol;
    std::vector<std::string> tokens1 = {"2", "1", "+", "3", "*"};
    std::vector<std::string> tokens2 = {"4", "13", "5", "/", "+"};
    std::vector<std::string> tokens3 = {"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"};
    
    std::cout << sol.evalRPN(tokens1) << std::endl;  // Output: 9
    std::cout << sol.evalRPN(tokens2) << std::endl;  // Output: 6
    std::cout << sol.evalRPN(tokens3) << std::endl;  // Output: 22
    
    return 0;
}

This code correctly evaluates an expression given in Reverse Polish Notation using a stack to perform the necessary arithmetic operations. Each token is processed, and the resulting value is obtained by appropriately managing the stack throughout the evaluation process.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI