LeetCode 770 Basic Calculator IV

LeetCode

Given an expression such as expression = "e + 8 - a + 5" and an evaluation map such as {"e": 1} (given in terms of evalvars = ["e"] and evalints = [1]), return a list of tokens representing the simplified expression, such as ["-1*a","14"]

An expression alternates chunks and symbols, with a space separating each chunk and symbol. A chunk is either an expression in parentheses, a variable, or a non-negative integer.
A variable is a string of lowercase letters (not including digits.) Note that variables can be multiple letters, and note that variables never have a leading coefficient or unary operator like "2x" or "-x".

Expressions are evaluated in the usual order: brackets first, then multiplication, then addition and subtraction. For example, expression = "1 + 2 * 3" has an answer of ["7"].

The format of the output is as follows:

For each term of free variables with a non-zero coefficient, we write the free variables within a term in sorted order lexicographically. For example, we would never write a term like "b*a*c", only "a*b*c".
Terms have degrees equal to the number of free variables being multiplied, counting multiplicity. We write the largest degree terms of our answer first, breaking ties by lexicographic order ignoring the leading coefficient of the term. For example, "a*a*b*c" has degree 4.
The leading coefficient of the term is placed directly to the left with an asterisk separating it from the variables (if they exist.) A leading coefficient of 1 is still printed. An example of a well-formatted answer is ["-2*a*a*a", "3*a*a*b", "3*b*b", "4*a", "5*c", "-6"].
Terms (including constant terms) with coefficient 0 are not included. For example, an expression of "0" has an output of [].

Example 1:

Input: expression = “e + 8 - a + 5”, evalvars = [“e”], evalints = [1]
Output: [“-1a”,”14”]

Example 2:

Input: expression = “e - 8 + temperature - pressure”, evalvars = [“e”, “temperature”], evalints = [1, 12]
Output: [“-1pressure”,”5”]

Example 3:

Input: expression = “(e + 8)  (e - 8)”, evalvars = [], evalints = []
Output: [“1ee”,”-64”]

Constraints: 1 <= expression.length <= 250
expression consists of lowercase English letters, digits, '+', '-', `’‘,‘(‘,‘)’,‘ ‘. *expressiondoes not contain any leading or trailing spaces. * All the tokens inexpressionare separated by a single space. *0 <= evalvars.length <= 100*1 <= evalvars[i].length <= 20*evalvars[i]consists of lowercase English letters. *evalints.length == evalvars.length*-100 <= evalints[i] <= 100`

题目大意：

表达式含有若干变量evalvars及其对应值evalints，且含加减乘和括号，求结果。若变量不在evalvars就简化表达式

解题思路：

此题不需要掌握，若考到就认命好了。之前的LeetCode 224 Basic Calculator含有括号和加法已经是Hard，此题不但有括号和加减乘，还有变量，难度不止提高一个数量级。不过不可以用eval函数的条件去掉了。所以就是考察eval。
如果不含变量，直接调用eval即可求解

Python代码：

def basicCalculatorIV(self, expression: str, evalvars: List[str], evalints: List[int]) -> List[str]:
	return eval(expression)

含变量且变量有值，就调用字典将变量替代掉，这里考到了regex替代函数re.sub

Python代码：

def basicCalculatorIV(self, expression: str, evalvars: List[str], evalints: List[int]) -> List[str]:
	var_to_val = dict(zip(evalvars, evalints))

	def f(s):
		token = s.group()
		s = str(var_to_val[token] if token in var_to_val else token)
		return s

	converted_expr = re.sub(r'\w+', f, expression)
	res = eval(converted_expr)
	return res

由于变量可能没有值，所以核心思路是用dict进行计算，如x + 2，用集合求和{(x,): 1} + {(): 2}得到{(‘x’,): 1, (): -2}，用dict来计算及保存结果

解题步骤：

1. regex替代变量
2. 将表达式用f包装，如(f(“x”) + f(“8”)) * (f(“x”) - f(“8”))
3. 实现dict的加减乘
4. dict的计算结果转成题目所求

注意事项：

1. Python代码：

   def basicCalculatorIV(self, expression: str, evalvars: List[str], evalints: List[int]) -> List[str]:
   	class MyCounter(Counter):
   		def __add__(self, other):
   			self.update(other)
   			return self
   
   		def __sub__(self, other):
   			self.subtract(other)
   			return self
   
   		def __mul__(self, other):
   			product = MyCounter()
   			for x in self:
   				for y in other:
   					xy = tuple(sorted(x + y))
   					product[xy] += self[x] * other[y]
   			return product
   
   	var_to_val = dict(zip(evalvars, evalints))
   
   	def f(s):
   		token = s
   		s = str(var_to_val[token] if token in var_to_val else token)
   		return MyCounter({(s, ): 1}) if s.isalpha() else MyCounter({(): int(s)})
   
   	converted_expr = re.sub(r'(\w+)', r'f("\1")', expression)
   	# (f("x") + f("8")) * (f("x") - f("8"))
   	res = eval(converted_expr) #
   	# C({('x', 'x'): 1, ('x',): 0, (): -64})
   	return ['*'.join((str(res[x]), ) + x)
   			for x in sorted(res, key=lambda x: (-len(x), x))
   			if res[x]]

算法分析：

时间复杂度为O(n)，空间复杂度O(1)