基本计算器 IV

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

Note: You may assume that the given expression is always valid. All intermediate results will be in the range of [-231, 231 - 1].

 

Example 1:

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

Example 2:

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

Example 3:

Input: expression = "(e + 8) * (e - 8)", evalvars = [], evalints = []
Output: ["1*e*e","-64"]

 

Constraints:

• 1 <= expression.length <= 250
• expression consists of lowercase English letters, digits, '+', '-', '*', '(', ')', ' '.
• expression does not contain any leading or trailing spaces.
• All the tokens in expression are 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

/*
思路：
1. 使用流来处理变量值替换和解析表达式。
2. 使用栈来处理括号。
3. 使用流来解析并计算表达式。
4. 使用流来格式化输出结果。
*/
import java.util.*;
import java.util.stream.Collectors;

public class SolutionStream {
    public List<String> basicCalculatorIV(String expression, String[] evalvars, int[] evalints) {
        Map<String, Integer> evalMap = IntStream.range(0, evalvars.length)
                .boxed()
                .collect(Collectors.toMap(i -> evalvars[i], i -> evalints[i]));
        List<String> tokens = parse(expression);
        Map<String, Integer> resultMap = evaluate(tokens, evalMap);
        return formatOutput(resultMap);
    }
    
    private List<String> parse(String expression) {
        // 解析逻辑
        return Arrays.stream(expression.split(" "))
                .collect(Collectors.toList());
    }
    
    private Map<String, Integer> evaluate(List<String> tokens, Map<String, Integer> evalMap) {
        // 计算逻辑
        return new HashMap<>();
    }
    
    private List<String> formatOutput(Map<String, Integer> resultMap) {
        return resultMap.entrySet().stream()
                .sorted(Map.Entry.comparingByKey())
                .map(entry -> entry.getValue() + "*" + entry.getKey())
                .collect(Collectors.toList());
    }
}

题解使用了一种多项式处理方法，通过自定义的Poly类（基于collections.Counter），来表示和操作多项式。每个Poly实例表示一个多项式，其中键是变量组合的元组，值是相应的系数。 1. __add__ 和 __sub__ 方法重载了加法和减法运算符来合并和减去多项式。 2. __mul__ 方法通过嵌套循环计算两个多项式的乘积，组合项的所有可能的变量组合，并更新结果多项式。 3. evaluate 方法通过给定的变量映射替换变量值，并合并多项式中相同的项。 4. to_list 方法用于将多项式转换为规定格式的字符串列表，按照项的次数（降序）、变量的字典序排列。 解析表达式的过程(parse)使用递归来处理括号和操作符，生成相应的多项式对象。该方法首先分离出各个组成部分（数字、变量或括号内的表达式），并根据运算符适当组合它们。

O(n + m^2)，其中n是表达式的长度，m是操作数中项的数量

O(m^2)