Leetcode solution 227: Basic Calculator II

Problem Statement 

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

Example 1:

Input: "3+2*2"
Output: 7

Example 2:

Input: " 3/2 "
Output: 1

Example 3:

Input: " 3+5 / 2 "
Output: 5

Note:

• You may assume that the given expression is always valid.
• Do not use the eval built-in library function.

Problem link

 

Video Tutorial

You can find the detailed video tutorial here

• Youtube 
• B站

Thought Process

This problem is very similar to Basic Calculator. The difference is there is no parenthesis in this one, but there is * and / . We can use similar thought process by having two stacks,  one stack for the operator and the other for the operands. We just need to pay attention the differentiate the operator's priority. For example, when you currently see a "+" or "-"  and previous operator is "*" or "/", you need to pop up the operator stack and calculate. When you currently see a "*" or "/" and previous operator is "+" or "-", you should just keep pushing operator to stack. Else, they are at the same priority, we just do the normal calculation.


A few caveats

• Notice number overflow. "0- 2147483648". I don't think leetcode has this test case but it is a valid one. We should use Long.
• Pay attention to the order when popping out operands and calculate, the order matters. 
• The number might not be just single digit, so need to read the char and convert the numbers

Solutions

Standard generic way

Keep two stacks, operator and operands as explained in the above "Thought Process"


Time Complexity: O(N), N is the length of the string
Space Complexity: O(N), extra stack is needed

Use one stack with two passes

Another neat and clean way to solve this problem is also similar to the "Use the sign method with one stack" in Basic Calculator. The idea is in the first pass, only calculate "*" and "/" and push the values into the stack, then have a 2nd pass to do the "+" and "-" calculations.

Time Complexity: O(N), N is the length of the string
Space Complexity: O(N), extra stack is needed

References

• Leetcode discussion on the clean solution