BASIC CALCULATOR | LEETCODE # 224 | PYTHON SOLUTION

In this video we are solving the first problem in the Basic Calculator series of problems on Leetcode. It's a little bit trickier than Basic Calculator II in that we have to deal with parenthesis but at least we do not have to account for multiplication and division operators.

[@adityahpatel]

this is not possible to figure out without memorizing that one has to do this like a stack with 4 elements. Is there no other way? it is not intuitive. Do they ask these kinds of probs? Can we solve this recursively?

[@halahmilksheikh]

Thank you. This was very helpful, although your drawing should have been simpler. You should have had cur, res, sign and stack in a row and have the characters as columns. It's more work to fill it out but much clearer.

[@crackfaang]

Haha yes it’s hard to draw with a mouse. Sometimes I just say okay this is too messy let’s go to the editor instead

[@jimmyahmed5619]

Thanks for explaining, Looking forward for version |||

[@MrTomer157]

Yesssssssss
Thank you

[@firezdog]

I think a recursive solution would be a little more natural / elegant conceptually. The call stack could do for you already what you do by hand in the iteration. I'm also curious whether, when you parse in the number to add, you could just consider the previous sign to be the sign of the number, then flatten out all operations to addition.
(There was an interesting conceptual simplification in this problem. Normally I believe subtraction is not (left?) associative, i.e. "3 - 4 + 1" is ambiguous between -2 and 0, but for the sake of this problem all arithmetic operations were assumed to be (left?) associative.)

[@user-bp9dx1ir7w]

Yes recursive is more intuitive perhaps but usually its also computational expensive

[@subee128]

Thanks

[@harishreddy4866]

FYI, python strings are immutable. It creates a copy of the string when you do `+=` operation and it's o(n) operation.

[@joshstevens2779]

He isn't modifying any strings

[@LonglongGuitar]

for the line: cur = cur * 10 + int(char)
why do we need 'cur * 10'?

[@crackfaang]

It's because we are parsing the number from left to right. Typically you would parse from right to left but since we go the other way we need to account for the fact that each digit we add means the previous one we parsed is 10x greater.
Take '123' for example:
First we parse 1. Cur = 1
Then we parse 2 -> So far we have parsed 12 but if we add 2 to the 1 we had before we get 3 not 12. So to get 12 we multiple the previous number by 10 and add the 2. (1 * 10) + 2 = 12
Then we parse 3. So we have parsed 123. Again we can't just add 3 to 12 because we get 15 but we need 123. So we multiply 12 by 10 again to get 120 and then we add 3.
You continue this process until you no longer have digits to parse and that final value is the entire parsed number.
Hope this helps.

[@HarumaWilson]

hey handsome, thank you for the explanation. This video is very helpful indeed.

[@crackfaang]

thanks for the kind words! make sure to subscribe if you haven’t already

[@joshstevens2779]

Was banging my head against the keyboard with all the edge cases, but I had taken a different approach. Thanks for the video but for the love of God can you increase the zoom/font size during the code editing

[@crackfaang]

Haha yea in newer videos I started zooming into 150% and not showing the side panel

[@parshantjuneja4811]

Here is a solution inspired by this video. Hopefully it helps
class Solution:
def calculate(self, s: str) -> int:
# Time complexity = O(n), Space complexity = O(n) where n = number of characters in s
# res of the current paranthesis, and the sign of the previous operation(+ or -)
# 1 means we are adding, -1 means we are substracting
stack_of_res = [[0, 1]]
num = 0
for i, c in enumerate(s):
# Ignore space
if s[i] == ' ':
continue
# Keep updating the num until we see an operator or a closing paranthesis
# Space will be ignored and we know for sure that the experssion is valid
# So we don't need to worry about 2 2 + 2 which will become 22 using the following logic
# But it wont happen 2 + (2) - After 2, we can only expect a space or operator or )
# (1 + 2 )
if c.isdigit():
num = num * 10 + int(c)
continue
# If c is an opening paranthesis => we have a start of a new expression
if c == '(':
stack_of_res.append([0, 1])
continue
# Evaluate whatever num when we see a + or - or )
if c in '+-)':
# There is a num when you close the paranthesis that we need to first
# add to our result which is the same as seeing a new operator
stack_of_res[-1][0] += stack_of_res[-1][1] * num
stack_of_res[-1][1] = 1 if c == '+' else -1
num = 0 if c in '+-' else stack_of_res.pop()[0]
continue
if num != 0:
stack_of_res[-1][0] += stack_of_res[-1][1] * num
return stack_of_res[0][0]