[LeetCode] Different Ways to Add Parentheses

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.

Example 1

Input: "2-1-1".

分而治之。对于输入字符串，若其中有运算符，则将其分为两部分，分别递归计算其值，然后将左值集合与右值集合进行交叉运算，将运算结果放入结果集中；若没有运算符，则直接将字符串转化为整型数放入结果集中。

Java：

public List Integer diffWaysToCompute(String input) { List Integer res = new ArrayList Integer for (int i = 0; i input.length(); i++) { char ch = input.charAt(i); if (ch == + || ch == - || ch == *) { List Integer left = diffWaysToCompute(input.substring(0, i)); List Integer right = diffWaysToCompute(input.substring(i + 1)); for (int n : left) { for (int m : right) { switch (ch) { case +: res.add(n + m); break; case -: res.add(n - m); break; case *: res.add(n * m); break; if (res.size() == 0) { res.add(Integer.parseInt(input)); return res; }
LeetCode 241. Different Ways to Add Parentheses 给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is: ((())) , (()()) , (())() ,