# \[241]\[中等]\[递归] 为运算表达式设计优先级

## 题目描述

[241. 为运算表达式设计优先级](https://leetcode-cn.com/problems/different-ways-to-add-parentheses/)

给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 \* 。

示例 1:

```
输入: "2-1-1"
输出: [0, 2]
解释:
((2-1)-1) = 0
(2-(1-1)) = 2
```

示例 2:

```
输入: "2*3-4*5"
输出: [-34, -14, -10, -10, 10]
解释:
(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10
```

## 解题思路

类似于二叉树的操作, 将运算符视作结点, 依次遍历所有运算符, 将其作为根节点, 即**最外层**, **优先级最低**的运算符, 优先计算两侧的结果, 最后将两侧所有可能的结果组合运算得到可能的结果列表. 对于两侧的表达式, 递归使用相同的方法计算所有可能的结果列表.

由于题目通过字符串给出表达式, 需要先遍历字符串, 找出所有的数字和运算符.

注意边际条件.

```python
class Solution:
    def diffWaysToCompute(self, input: str) -> List[int]:
        string_len = len(input)
        n, a, b = 0, 0, 0
        nums, symbols = [], []
        while b < string_len:
            if input[b] in ('+', '-', '*'):
                if b > a:
                    nums.append(int(input[a: b]))
                symbols.append(input[b])
                a = b = b + 1
            else:
                b += 1
        if b > a:
            nums.append(int(input[a: b]))

        n, m = len(symbols), len(nums)
        if n == 0:
            return nums
        if n != m - 1:
            return [0]

        @functools.lru_cache()  # 缓存加速
        def get_res(start, end):
            if start == end:
                return [eval('{}{}{}'.format(nums[start - 1], symbols[start - 1], nums[start]))]

            res = []
            for i in range(start, end + 1):
                left_res = get_res(start, i - 1) if i > start else [nums[start - 1]]
                right_res = get_res(i + 1, end) if i < end else [nums[end]]
                for l in left_res:
                    for r in right_res:
                        res.append(eval('{}{}{}'.format(l, symbols[i - 1], r)))
            return res

        return get_res(1, n) if n else [0]
```

## 相关题目

* [\[95\]\[中等\]\[递归\] 不同的二叉搜索树 II](broken://pages/-MI7Nbfj9Sh3LNe7g3KO)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kerasnoone.gitbook.io/garnet/suan-fa/di-gui/241-wei-yun-suan-biao-da-shi-she-ji-you-xian-ji.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.