BASIC CALCULATOR | LEETCODE # 224 | PYTHON SOLUTION

[@dj1984x]

great solution, thank you. Much better explanation than the LC editorials, and much cleaner & more intuitive code to follow

[@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

[@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

[@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.)

[@Wei-KuoLi]

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

[@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

[@LonglongFeng]

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.

[@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?

[@pixelchai]

Yes you can solve this recursively, this was my first approach. Look up 'recursive descent parser'. It ended up having more overhead than the stack solution though in my case.

[@jimmyahmed5619]

Thanks for explaining, Looking forward for version |||

[@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]

[@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

[@MrYyope15555]

Yesssssssss Thank you

[@subee128]

Thanks