Hard
Subtopics
math·recursion·stack·string
Companies
amazon·apple·bytedance·doordash·facebook·google·houzz·hulu·jingchi·microsoft·pinterest·pocket-gems·snapchat·uberLast updated: Aug 2, 2025
Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, +, -, *, / operators , open ( and closing parentheses ) and empty spaces . The integer division should truncate toward zero.
You may assume that the given expression is always valid. All intermediate results will be in the range of [-2^31, 2^31 - 1].
Method 1 - Using Operand and Operator Stack - Calculating Answer as Soon as Possible#
We can proceed similar to Basic Calculator 2. But this time along with numStack, we take operator stack as well.
Each time we see digit, we make a number out of it , we push it numStack
If we see operator, we push it to opStack.
But before pushing it, we check if there are any higher precedence operator already in stack. If so, we should first process them, by poping them out and corresponding numbers from numStack
If we see ) , we just push it to opStack
If we see (, we should pop everything out from opStack until we see ) in stack. Finally we pop out ) as well, marking one set of parenthesis as done.
Also, note that I have used lambda expressions in java for isOperator() function and hasPrecedence(). They can be simple functions, I just wanted to learn about them.