本文共 1830 字，大约阅读时间需要 6 分钟。
原文地址：
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". ((2-1)-1) = 0(2-(1-1)) = 2
Output: [0, 2]
Example 2
Input:"2*3-4*5" (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
Output: [-34, -14, -10, -10, 10]
这种问题可以使用分治法，递归去处理运算符两边的字符串，边界条件就是不再可以按照运算符分割字符串，即字符串中只包含数字。
public class DifferentWaysToAddParentheses { public static List diffWaysToCompute(String input) { if (input == null) return null; List res = new ArrayList<>(); for (int i = 0; i < input.length(); i++) { if (input.charAt(i) == '+' || input.charAt(i) == '-' || input.charAt(i) == '*') { List res1 = diffWaysToCompute(input.substring(0, i)); List res2 = diffWaysToCompute(input.substring(i + 1)); for (int index1 = 0; index1 < res1.size(); index1++) { for (int index2 = 0; index2 < res2.size(); index2++) { if (input.charAt(i) == '+') { res.add(res1.get(index1) + res2.get(index2)); } else if (input.charAt(i) == '-') { res.add(res1.get(index1) - res2.get(index2)); } else { res.add(res1.get(index1) * res2.get(index2)); } } } } } if (res == null || res.size() == 0) res.add(Integer.valueOf(input)); return res; } public static void main(String[] args) { String input = "2*3-4*5"; System.out.println(diffWaysToCompute(input)); }} 转载地址：http://bihii.baihongyu.com/