LC 0224 0227 0772 [H] [M] [H] Basic Calculator I II III - ALawliet/algorithms GitHub Wiki

I: +- and ()
II: +-*/
III: +-*/ and () 

so best to study III because it works for I + II + III

• num = num*10 + int(s[i]) to handle tenths place
• for addition/subtraction, just loop and add/subtract
• for multiplication and division, use a stack to get the previous value
• for parens () grouped expressions, use recursion while tracking the end pointer

---

int division should truncate (NOT floor) towards 0: use int() or math.trunc() (// breaks with negative numbers)

>>> -3/2
-1.5
>>> int(-3/2)
-1
>>> -3//2
-2
>>> math.trunc(-3/2)
-1

vocab:

• operator: +, -, *, /
• operand: number value being operated on

II

'''
the correct answer of -3/2 is -1 because we want to truncate the negative answer towards 0 (round up) with int(x/y) or math.trunc(x/y)
if it were 3/2 it would be 1 because we want to truncate the postive answer towards 0 (round down)
>>> -3/2
-1.5
>>> -3//2
-2
>>> int(-3/2)
-1
>>> int(3//2)
1
>>> int(-3//2)
-2
>>> math.trunc(-3/2)
-1
'''

ops = {
    '+': lambda x: stack.append( x ),
    '-': lambda x: stack.append( -x ),
    '*': lambda x: stack.append( stack.pop()*x ),
    '/': lambda x: stack.append( int( stack.pop()/x ) ) # math.trunc() also works
}

class Solution:
    def calculate(self, s):
        stack = []
        num = 0
        prev_op = '+'

        for i, x in enumerate(s):
            # print(i, x) # debug

            if x.isdigit():
                num *= 10 # handle tens places as we build out the current number with x
                num += int(x) # add the actual number
                # print(i, x, num) # debug

            elif x in ops: # else doesn't work because there can be ' '
                ops[prev_op](num) # op is actually the previous op and num is already calculated, we just push it on the stack
                # print(stack) # debug
                # reset
                num = 0
                prev_op = x

        # if i == len(s) - 1: # if we're at the end, we still need to add the last op we calculated
        ops[prev_op](num)
                
        return sum(stack)

III - works for all 3

introduce j as the end pointer for a grouped expression

the recursion of the overall function can return either just the answer sum(stack) or the group too sum(stack), j

class Solution:
    def calculate(self, s: str) -> int:
        stack = []
        num, prev_op = 0, '+'
        
        i = 0 # we need to use a while loop here to track and manage i
        while i < len(s):
            # handle the usual
            if s[i].isdigit():
                num = num*10 + int(s[i])

            elif s[i] in ops:
                ops[prev_op](num)
                num, prev_op = 0, s[i]

            # handle groups
            elif s[i] == '(':                                   # for BC I and BC III
                num, j = self.calculate(s[i+1:])
                i += j # the recursive call returns and we move i past the grouped expression: (i+j)
            elif s[i] == ')':                                   # for BC I and BC III
                ops[prev_op](num)
                j = i+1 # j represents the end of the grouped expression after it is parsed because we moved i then add the +1 for ): )
                return sum(stack), j

            i += 1

        ops[prev_op](num) # still need to do last operation
        return sum(stack)

wrap it all in a helper method for recursion (better to stick to iterative, it is easier than this)

class Solution:
    def calculate(self, s):
        s += '$' # extra char to remove n-1 check
        def helper(stack, i):
            num, op = 0, '+'
            while i < len(s): # while loop to control i
                c = s[i]
                if c.isspace():
                    i += 1
                elif c.isdigit():
                    num = 10*num + int(c)
                    i += 1
                elif c == '(':
                    num, i = helper([], i+1) # move past (
                else: # '+-*/' or ')' or i == n-1 
                    ops[op](num)
                    num, op = 0, c
                    i += 1
                    if c == ')':
                        return sum(stack), i # return ans to parent who invoked recursion
            return sum(stack)
        return helper([], 0)