mediumStackPattern: LIFO
Evaluating Postfix Expressions Using a Stack Solution
Problem Statement
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.
Examples
Example 1:
Input:2 3 +
Output:5
Explanation: First, push 2 and 3 into the stack. Then, pop two elements, add them, and push the result back into the stack, resulting in a final value of 5.
Example 2:
Input:5 2 * 4 /
Output:2.5
Explanation: Push 5 and 2 into the stack, then pop them, multiply, and push the result. Next, push 4 into the stack, pop both the result and 4, divide, and push the final result back into the stack.
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.
Time: O(n) Space: O(n)
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.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
No solution code is currently loaded.
Complete this code in the workspace editor.