--- Difficulty: Medium Source: 160 Days of Problem Solving Tags: - Stack --- # πŸš€ _Day 8. Evaluation of Postfix Expression_ 🧠 The problem can be found at the following link: [Question Link](https://www.geeksforgeeks.org/batch/gfg-160-problems/track/stack-gfg-160/problem/evaluation-of-postfix-expression1735) ## πŸ’‘ **Problem Description:** You are given an array of strings `arr` that represents a valid arithmetic expression written in **Reverse Polish Notation (Postfix Notation)**. Your task is to evaluate the expression and return an integer representing its value. ### **Operators Supported** - `+` Addition - `-` Subtraction - `*` Multiplication - `/` Integer Division (rounds towards zero) ### **Key Points** - All numbers are valid integers. - No division by zero. - Result and intermediate values fit in **32-bit signed integer**. ## πŸ” **Example Walkthrough:** ### **Example 1** #### **Input:** arr = ["2", "3", "1", "*", "+", "9", "-"] #### **Output:** `-4` #### **Explanation:** Expression equivalent to: $\(2 + (3 \times 1) - 9 = 5 - 9 = -4\)$ ### **Example 2** #### **Input:** arr = ["100", "200", "+", "2", "/", "5", "*", "7", "+"] #### **Output:** `757` #### **Explanation:** Expression equivalent to: $\(\frac{100 + 200}{2} \times 5 + 7 = 150 \times 5 + 7 = 757\)$ ### **Constraints** - $\(1 \leq arr.size() \leq 10^5\)$ - $\(arr[i]\)$ is either an **operator**: "+", "-", "\*", "/" or an **integer** in the range $\([-10^4, 10^4]\)$ ## 🎯 **My Approach:** ### **Stack-Based Evaluation (O(N) Time, O(N) Space)** This approach processes each element in the postfix expression in a **single pass** and uses a **stack** to store operands. Operators pop the top two operands, evaluate them, and push the result back onto the stack. ### **Algorithm Steps:** 1. **Initialize an empty stack.** 2. **Iterate through each token in the array:** - If the token is an **operator**, pop the top two operands, apply the operation, and push the result back. - If the token is a **number**, convert it to integer and push it onto the stack. 3. **At the end, the stack will contain exactly one value β€” the final result.** This method guarantees all operations happen in **O(1)** time, and we iterate over the array exactly once. ## πŸ•’ **Time and Auxiliary Space Complexity** - **Expected Time Complexity:** O(N), where N = length of `arr`, as each token is processed exactly once. - **Expected Auxiliary Space Complexity:** O(N), for storing the operands in the stack. ## πŸ“ **Solution Code** ## **Code (C++)** ```cpp class Solution { public: int evaluate(vector& arr) { stack st; for (auto &s : arr) { if (s == "+" || s == "-" || s == "*" || s == "/") { int b = st.top(); st.pop(); int a = st.top(); st.pop(); if (s == "+") st.push(a + b); else if (s == "-") st.push(a - b); else if (s == "*") st.push(a * b); else st.push(a / b); } else st.push(stoi(s)); } return st.top(); } }; ```

⚑ Alternative Approaches

 ## **2️⃣ Using `vector` as Stack (O(N) Time, O(N) Space)** This approach **simulates a stack using a `vector`**, treating the `back()` element as the top of the stack. ```cpp class Solution { public: int evaluate(vector& arr) { vector st; for (const string& token : arr) { if (token == "+" || token == "-" || token == "*" || token == "/") { int b = st.back(); st.pop_back(); int a = st.back(); st.pop_back(); if (token == "+") st.push_back(a + b); else if (token == "-") st.push_back(a - b); else if (token == "*") st.push_back(a * b); else st.push_back(a / b); } else { st.push_back(stoi(token)); } } return st.back(); } }; ``` πŸ”Ή **Pros:** Avoids `stack`, works similarly. πŸ”Ή **Cons:** Same time and space complexity. ## **3️⃣ Recursive Approach (O(N) Time, O(N) Space)** This approach recursively processes tokens from **right to left**, mimicking evaluation directly from the postfix array itself. It’s more theoretical and educational than practical due to recursion overhead. ```cpp class Solution { int idx; int eval(vector& arr) { string token = arr[idx--]; if (isdigit(token.back()) || (token.size() > 1 && isdigit(token[1]))) { return stoi(token); } int b = eval(arr); int a = eval(arr); if (token == "+") return a + b; if (token == "-") return a - b; if (token == "*") return a * b; return a / b; } public: int evaluate(vector& arr) { idx = arr.size() - 1; return eval(arr); } }; ``` πŸ”Ή **Pros:** Recursive parsing for educational purposes. πŸ”Ή **Cons:** Not suitable for large input due to stack overflow risk. ## **πŸ“Š Comparison of Approaches** | **Approach** | ⏱️ **Time Complexity** | πŸ—‚οΈ **Space Complexity** | βœ… **Pros** | ⚠️ **Cons** | | --------------------- | ---------------------- | ----------------------- | ------------------- | ------------------- | | **Iterative Stack** | 🟒 O(N) | 🟒 O(N) | Simple & optimal | None | | **Vector as Stack** | 🟒 O(N) | 🟒 O(N) | Avoids `stack` | Same complexity | | **Recursive Parsing** | 🟑 O(N) | πŸ”΄ O(N) (call stack) | Educational | Stack overflow risk | ## πŸ’‘ **Best Choice?** - βœ… **For competitive programming:** **Iterative Stack (`O(N)` Time, `O(N)` Space)**. - βœ… **For educational learning:** Recursive parsing is interesting to explore recursion-based parsing.
## **Code (Java)** ```java class Solution { public int evaluate(String[] arr) { Stack st = new Stack<>(); for (String s : arr) { if ("+-*/".contains(s)) { int b = st.pop(), a = st.pop(); if (s.equals("+")) st.push(a + b); else if (s.equals("-")) st.push(a - b); else if (s.equals("*")) st.push(a * b); else st.push(a / b); } else { st.push(Integer.parseInt(s)); } } return st.peek(); } } ``` ## **Code (Python)** ```python class Solution: def evaluate(self, arr): st = [] for s in arr: if s in {"+", "-", "*", "/"}: b, a = st.pop(), st.pop() if s == "+": st.append(a + b) elif s == "-": st.append(a - b) elif s == "*": st.append(a * b) else: st.append(int(a / b)) else: st.append(int(s)) return st[-1] ``` ## 🎯 **Contribution and Support:** For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: [Any Questions](https://www.linkedin.com/in/patel-hetkumar-sandipbhai-8b110525a/). Let’s make this learning journey more collaborative! ⭐ **If you find this helpful, please give this repository a star!** ⭐ ---

πŸ“Visitor Count