150. Evaluate Reverse Polish Notation

📝 Problem Details

• Title: 150. Evaluate Reverse Polish Notation
• Link: https://leetcode.com/problems/evaluate-reverse-polish-notation/
• Difficulty: Medium
• Tags/Categories: Stack Math
• Neetcode Reference: Video Link

---

🔍 Problem Understanding

Given a string of tokens, containing integers and valid operators (+ , - , * , /), return the integer that represents the value of the expression in tokens

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

---

🎯 Key Insights

- the values are strings, so we will need to convert numbers to integers before performing any operations
- to perform any given operation, we require 2 integers
- we can use a stack to store elements until we encounter an operand, upon which we conduct the operations of the integers and push it back into the stack and continue
- we should end up with a single value by the end of this process

---

🔑 Approach

1. Use a stack to store the intermediate results as you process the tokens.
2. Iterate through the list of tokens:
   - If the token is an operator (`+`, `-`, `*`, `/`):
     - Pop the top two elements from the stack as `operand2` and `operand1`.
     - Perform the operation `operand1 <operator> operand2`.
     - Push the result back onto the stack.
   - If the token is a number:
     - Convert it to an integer and push it onto the stack.
3. At the end of the iteration, the stack should contain exactly one element, which is the result of the expression.

---

💡 Explanation of Solution

- The stack helps keep track of the intermediate results of the operations.
- Each time an operator is encountered, it combines the top two numbers from the stack, which represent the most recently seen operands, ensuring the correct order of operations.
- After processing all tokens, the stack contains only the final result of the Reverse Polish Notation expression.

---

⌛ Complexity Analysis

Time Complexity: O(n)
- we are iterating across n tokens

Space Complexity: O(n)
- for the auxillary space used to store elements in the stack

---

💻 Implementation of Solution

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> stk;
 
        for(const auto& token : tokens) {
            if(token == "+"
            || token == "-"
            || token == "*"
            || token == "/") {
                
                int operand2 = stk.top();
                stk.pop();
                int operand1 = stk.top();
                stk.pop();
 
                if(token == "+") stk.push(operand1 + operand2);
                else if (token == "-") stk.push(operand1 - operand2);
                else if (token == "*") stk.push(operand1 * operand2);
                else if (token == "/") stk.push(operand1 / operand2);
            }
            else {
                stk.push(stoi(token));
            }
        }
        return stk.top();
    }
};