class Polynomial:
# optional initialization with one term
def __init__(self, coeff=0, variables=[]):
self.c = Counter()
self.c[tuple(sorted(variables))] = coeff
def tokenize(self):
# sort by (decreasing length, lexicographically increasing)
def key(term):
variables,coeff = term
return [-len(variables), variables]
ret = []
for variables,coeff in sorted(self.c.items(), key=key):
# nonzero counts only
if coeff:
ret.append("*".join([str(coeff), *variables]))
return ret
def __add__(self, o):
ret = deepcopy(self)
ret.c.update(o.c)
return ret
def __sub__(self, o):
ret = deepcopy(self)
ret.c.subtract(o.c)
return ret
def __mul__(self, o):
ret = Polynomial()
for variables,coeff in self.c.items():
for VARIABLES,COEFF in o.c.items():
ret.c[tuple(sorted(variables + VARIABLES))] += coeff*COEFF
return ret
class Solution:
def basicCalculatorIV(self, s: str, names: List[str], values: List[int]) -> List[str]:
bound_vars = dict(zip(names, values))
def AS():
ret = MUL()
while q[0] in "+-":
op = q.popleft()
if op == "+":
ret += MUL()
else:
ret -= MUL()
return ret
def MUL():
ret = UNIT()
while q[0] == "*":
q.popleft()
ret *= UNIT()
return ret
def UNIT():
if q[0] == "(":
q.popleft()
ret = AS()
q.popleft()
return ret
elif q[0].isdigit():
return NUMBER()
else:
return VAR()
def NUMBER():
ret = ""
while q[0].isdigit():
ret += q.popleft()
return Polynomial(int(ret))
# bound or free
def VAR():
ret = ""
while q[0].islower():
ret += q.popleft()
if ret in bound_vars:
return Polynomial(bound_vars[ret])
else:
return Polynomial(1, [ret])
q = deque(s.replace(" ", "") + "$")
return AS().tokenize()