leetcode241

public class Solution {
    public IList<int> DiffWaysToCompute(string input) {
        List<int> ret = new List<int>();
            for (int i = 0; i < input.Length; i++)
            {
                if (input[i] == '-' ||
                    input[i] == '*' ||
                    input[i] == '+')
                {
                    string part1 = input.Substring(0, i);
                    string part2 = input.Substring(i + 1);
                    var part1Ret = DiffWaysToCompute(part1);
                    var part2Ret = DiffWaysToCompute(part2);
                    foreach (var p1 in part1Ret)
                    {
                        foreach (var p2 in part2Ret)
                        {
                            int c = 0;
                            switch (input[i])
                            {
                                case '+': c = p1 + p2;
                                    break;
                                case '-': c = p1 - p2;
                                    break;
                                case '*': c = p1 * p2;
                                    break;
                            }
                            ret.Add(c);
                        }
                    }
                }
            }
            if (ret.Count == 0)
            {
                ret.Add(int.Parse(input));
            }
            return ret;
    }
}

https://leetcode.com/problems/different-ways-to-add-parentheses/#/description

补充一个python的

 1 class Solution:
 2     def diffWaysToCompute(self, input: str) -> 'List[int]':
 3         re = list()
 4         n = len(input)
 5         for i in range(n):
 6             c = input[i]
 7             if c =='+' or c == '-' or c == '*':
 8                 left = input[:i]
 9                 right = input[i+1:]
10                 for l in self.diffWaysToCompute(left):
11                     for r in self.diffWaysToCompute(right):
12                         if c == '+':
13                             re.append(l + r)
14                         elif c == '-':
15                             re.append(l -  r)
16                         elif c == '*':
17                             re.append(l * r)
18         if len(re) == 0:
19             re.append(int(input))
20         return re

实现：