28. Evaluation of Postfix Expression
The problem can be found at the following link: Question Link
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.
Examples
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:
Initialize an empty stack.
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.
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.
Code (C++)
class Solution {
public:
int evaluate(vector<string>& arr) {
stack<int> 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();
}
};
Code (Java)
class Solution {
public int evaluate(String[] arr) {
Stack<Integer> 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)
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. Letβs make this learning journey more collaborative!
β If you find this helpful, please give this repository a star! β
πVisitor Count
Last updated