Sunday, August 18, 2019

Leetcode solution 772: Basic Calculator III

Problem Statement 


Implement a basic calculator to evaluate a simple expression string.
The expression string may contain open ( and closing parentheses ), the plus + or minus sign -non-negative integers and empty spaces .
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 [-2147483648, 2147483647].
Some examples:
"1 + 1" = 2
" 6-4 / 2 " = 4
"2*(5+5*2)/3+(6/2+8)" = 21
"(2+6* 3+5- (3*14/7+2)*5)+3"=-12

Note: Do not use the eval built-in library function.
Problem link

 

Video Tutorial

You can find the detailed video tutorial here

Thought Process

This is an extension problem to Basic Calculator and Basic Calculator II. The differences are this time it really looks like a real calculator where it can do "+-*/" and with brackets.

It's still the same thought process with exactly the same idea before: having two stacks,  one stack for the operator and the other for the operands, and with exactly the same calculating preferences before: calculate * and / before + and -. When seeing right bracket, continue popping till you see the left bracket.

This works fine assuming all the integers are non-negative, which they are supposed to be based on the problem description, and that's what most of the existing online leetcode solutions did as well.

As of 08/18/2019, this doesn't seem to be the case because leetcode decides to include "non-negative" integer test cases. See below case "-1+4*3/3/3"

An "non-negative" integer case


Since we are practicing interviews, so let's also address the non-negative integer case as well

A few caveats
  • (New) Handle negative integer starting case:
    "-1 + 2" or "-(2+3)*4"
  • (New) Handle negative integer in between expression case:
    "1 - (-7)"
  • (New) Calculate whenever you can calculate since division order matters
    15 / 3 / 5 should be 1, but it won't work 3 / 5 = 0,  then 15/0 invalid
  • 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

Two stacks for non-negative integer solution

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

Two stacks for negative integer solution

Essentially how do address the below two situations given the current code structure
  • (New) Handle negative integer starting case. I simply just check if the first char in trimmed string is "-", and push a -1 into operands and "*" into operator. (e.g.,  -(a+b) = -1 * (a+b) and -a = -1 * a)
    "-1 + 2" or "-(2+3)*4"
  • (New) Handle negative integer in between expression case. This is a bit hacky because a  "-" in the middle of the expression could mean two things: a normal minus sign or a negative sigh denoting negative integer. Luckily "1 - - 2" would not be a valid case which means there should always be a left bracket before the negative sign for negative integer. What I did was using isNegativeNumberFollowingLeftBracket to find those cases and put a -1 and * into the operator and operands respectively
    "1 - (-7)"


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

References

No comments:

Post a Comment