Problem statement

https://leetcode.com/problems/basic-calculator-iv/

Solution

Very difficult and painful problem, there no chance that you solve it under 2 hours. Let us use the idea of 0772 Basic Calculator III combined with polynomial multiplication and addition. First of all, let us discuss how our polynomials will look like: list of tuples: [(('a', 'a'), -1), (('a', 'b'), 0), (('b', 'b'), 1)] in each tuple we have two elements: first one is tuple of variables and second is number - coefficient. For example we have -a*a + b*b polynomial here.

Now, we need to modify our update function from Basic Calculator III:

  1. First, we check if we have list as our variable: if we have not list, it means that we just start to build our polynomial: so, we first check if this variable has value, using v = values.get(v, v) function. Then we check if we have number (it can start with -) and create polynomial v = [((), int(v))]. If it is variable, then we create variable v = [((v,), 1)]
  2. If we have +, then we just append polynomial to stack
  3. If we have -, we need to add to stack polynomial multiplied by -1 (we write -1 as [((), -1)])
  4. If we have *, then we need to pop last element of stack, multiply it by v and put it back.
  5. The rest logic of calculate is very similar to Basic Calculator III, the only difference is instead of summating our stack, we apply AddPol function to all stack.
  6. Finally we calculate our string, remove all terms with value 0, sort items by length and order and finally join all string.

Complexity

Complexity: it is difficult to estimate, but we can say it is O(m + 2^n) both for time and space, where m is length of our values and n is length of s, because we can have example like (a+b)*(c+d)*....

Code

class Solution:
    def basicCalculatorIV(self, s, evalvars, evalints):
        def AddPol(a, b):
            d = defaultdict(int)
            for x, y in a: d[x] += y
            for x, y in b: d[x] += y
            return list(d.items())

        def MultPol(a, b):
            d = defaultdict(int)
            for x1, y1 in a:
                for x2, y2 in b:
                    d[tuple(sorted(x1+x2))] += y1*y2
            return list(d.items())

        def calculate(s):
            def update(op, v):
                if type(v) != list:
                    v = values.get(v, v)
                    if v.isdigit() or v and v[0] == "-": v = [((), int(v))]
                    elif v.isalpha(): v = [((v,), 1)]
                if op == "+": stack.append(v)
                if op == "-": stack.append(MultPol(v, [((), -1)]))
                if op == "*": stack.append(MultPol(stack.pop(), v))

            it, num, stack, sign = 0, "", [], "+"
            
            while it < len(s):
                if s[it].isalnum():
                    num += s[it]
                elif s[it] in "+-*":
                    update(sign, num)
                    num, sign = "", s[it]
                elif s[it] == "(":                                  
                    num, j = calculate(s[it + 1:])
                    it = it + j
                elif s[it] == ")": 
                    update(sign, num)
                    return reduce(lambda a,b:AddPol(a,b), stack, {}), it + 1
                it += 1

            update(sign, num)
            return reduce(lambda a,b:AddPol(a,b), stack, {})

        values = {x: str(y) for x, y in zip(evalvars, evalints)}
        
        calculated = calculate(s)
        calculated = {x:y for x,y in calculated if y!=0}   
        calculated = sorted(list(calculated.items()), key = lambda x: (-len(x[0]), x[0]) )
        return ["*".join((str(y),) + x) for x, y in calculated]