Evaluating Postfix Expressions Using a Stack — Problem Statement & Solution Guide
Problem Description
Given a string of postfix mathematical expressions containing single-digit numbers and basic arithmetic operators (+, -, *, /), implement a function that evaluates the expression using a stack data structure and returns the result as a string.
Examples
Input
2 3 +
Output
5.0
Explanation: Step-by-step: with input '2 3 +', we first push 2 and 3 onto the stack, then pop them off and add them together, giving output 5.0
Input
4 2 *
Output
8
Explanation: Step-by-step: with input '4 2 *', we first push 4 and 2 onto the stack, then pop them off and multiply them together, giving output 8
Constraints
- The input string will contain at most 100 elements separated by spaces.
- Each number in the input string is a single-digit integer between 0 and 9.
- The input string is guaranteed to be a valid postfix expression.
- Division by zero will not occur.
Optimal Approach & Strategy
A more efficient approach is to use a stack to store the operands and evaluate the expression from left to right, resulting in a linear time complexity of O(n). This approach avoids repeated calculations and takes advantage of the LIFO pattern of the stack.
Brute Force Approach
A naive approach would involve using a recursive function to evaluate each subexpression, resulting in an O(n^2) time complexity. However, this approach is inefficient due to repeated calculations. Another brute-force approach would be to generate all possible orderings of the numbers and operators, then evaluate each one.
Verified Code Solutions
class Solution {
public String evaluatePostfix(String expression) {
String[] tokens = expression.split(" ");
java.util.Stack<String> stack = new java.util.Stack<>();
for (String token : tokens) {
if (token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/")) {
String operand2 = stack.pop();
String operand1 = stack.pop();
int result;
if (token.equals("+")) {
result = Integer.parseInt(operand1) + Integer.parseInt(operand2);
} else if (token.equals("-")) {
result = Integer.parseInt(operand1) - Integer.parseInt(operand2);
} else if (token.equals("*")) {
result = Integer.parseInt(operand1) * Integer.parseInt(operand2);
} else {
result = Integer.parseInt(operand1) / Integer.parseInt(operand2);
}
stack.push(String.valueOf(result));
} else {
stack.push(token);
}
}
return stack.peek();
}
}def evaluate_postfix(expression):
stack = []
for token in expression.split():
if token in '+-*/':
operand2 = stack.pop()
operand1 = stack.pop()
if token == '+':
result = int(operand1) + int(operand2)
elif token == '-':
result = int(operand1) - int(operand2)
elif token == '*':
result = int(operand1) * int(operand2)
else:
result = int(operand1) // int(operand2)
stack.append(str(result))
else:
stack.append(token)
return stack[0]Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.