为运算表达式设计优先级

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/different-ways-to-add-parentheses

题目

给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。生成的测试用例满足其对应输出值符合 32 位整数范围，不同结果的数量不超过 10^4^ 。

思路

先处理输入，通过符号来截取字符串（substring），将字符串的数值部分转换为整型存入一个数组，再把符号存入另一个数组。

这里官方题解是存入同一个数组，因为输入表达式中的所有整数值在范围 [0, 99]，可以用负数代表符号

之后进行递归求解，一开始错误的思路是：

对于一个符号位，取先运算和后运算两种方式。即 a + b + c ，分为 a + fun（"b+c"）和 （a+b）+ fun（"c"）

这样得出来的结果会少一些情况，对于表达式 a + b + c + d来说，不会出现 （a + （b + c）） + d 这种情况，因为第一次递归/分治只会有 a + （ b + c + d）和 （a + b）+ c + d

或者这样理解，对于第一种方式，是前面的数 + 后面表达式的可能结果。第二种方式是 前面的数的和（差、积）+ 后面表达式的结果，这样对于前面的组合，永远只有一种：（（a + b）+ c） 而不会出现（a + b + c）的所有可能

看了题解改进后的思路：

递归的以符号为分界，对左边的表达式的可能结果和右边的表达式的可能结果进行组合。

总结

隔了二十多天重新开始刷题，写了较长时间，还是得多练啊。