Leetcode-241 —— different ways to add parentheses

Posted on Edited on In ,

题目描述

给定一个有数字和运算符组成的字符串，计算不同优先级的情况下的返回结果。

Example 1:

1
2
3
4
5
6
7
8
Input: "2*3-4*5"
Output: [-34, -14, -10, -10, 10]
Explanation: 
(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

分析

对于每个运算表达式，我们可以分解为 A op B 的形式。当 A 和 B 都是数字时，直接返回计算结果，否则拆分表达式。

1
2
2*3-4*5 split to =>
(2) * (B) or (2*3)-(B)

所以如下递归求解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def calc(x, op, y):
    if op == "+":
        return x + y
    if op == "-":
        return x - y
    else:
        return x * y

def solve(input):
    if input.isdigit():
        return [int(input)]
    ans = []
    for i, c in enumerate(input):
        if c in "+-*":
            left = solve(input[:i])
            right = solve(input[i+1:])

            for l in left:
                for r in right:
                    ans.append(calc(l, c, r))
    return ans