mediumStackPattern: Stack Processing
Evaluating Postfix Expressions Using Stack Solution
Problem Statement
Given a postfix expression, write a function that evaluates the expression using a stack. The expression consists of single digit operands and basic arithmetic operators (+, -, *, /).
Examples
Example 1:
Input:['2', '3', '+']
Output:5
Explanation: First, push 2 and 3 into the stack. Then, pop the last two elements, add them, and push the result back into the stack. The result is 5.
Example 2:
Input:['5', '1', '2', '+', '4', '*', '+']
Output:19
Explanation: First, push 5 and 1 into the stack. Then, push 2, pop the last two elements, add them (1+2=3), and push the result back into the stack. Next, pop the last two elements (5 and 3), multiply them (5*3=15), and push the result back into the stack. Finally, pop the last two elements (15 and 4), add them (15+4=19), and push the result back into the stack.
Constraints
- The expression is guaranteed to be valid.
- The input array size will not exceed 100.
- The operands are single digit numbers.
- The operators are +, -, *, /
Time: O(n) Space: O(n)
Use a stack to store the operands and apply the operators when encountered, resulting in linear time complexity. Iterate through the postfix expression and pop the last two elements from the stack when an operator is found, applying the operation and pushing the result back onto 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.