@@ -0,0 +1,2013 @@
+package com.freetymekiyan.algorithms.level.medium;%0A%0Aimport java.util.LinkedList;%0Aimport java.util.List;%0A%0A/**%0A * Given a string of numbers and operators, return all possible results from computing all the different possible ways%0A * to group numbers and operators. The valid operators are +, - and *.%0A * %3Cp%3E%0A * Example 1%0A * Input: %222-1-1%22.%0A * %3Cp%3E%0A * ((2-1)-1) = 0%0A * (2-(1-1)) = 2%0A * Output: %5B0, 2%5D%0A * %3Cp%3E%0A * Example 2%0A * Input: %222*3-4*5%22%0A * %3Cp%3E%0A * (2*(3-(4*5))) = -34%0A * ((2*3)-(4*5)) = -14%0A * ((2*(3-4))*5) = -10%0A * (2*((3-4)*5)) = -10%0A * (((2*3)-4)*5) = 10%0A * Output: %5B-34, -14, -10, -10, 10%5D%0A * %3Cp%3E%0A * Tags: Divide and Conquer%0A * Similar Problems: (M) Unique Binary Search Trees II, (H) Basic Calculator, (H) Expression Add Operators%0A */%0Apublic class DifferentWaysToAddParentheses %7B%0A%0A    /**%0A     * Divide and Conquer.%0A     * Divide the input into sub-strings according to the operator: left and right.%0A     * Stop until there is no operator in the string, parse the integer and add it to result list.%0A     * Then combine left and right result lists with the operator to generate result.%0A     */%0A    public List%3CInteger%3E diffWaysToCompute(String input) %7B%0A        List%3CInteger%3E res = new LinkedList%3C%3E();%0A        for (int i = 0; i %3C input.length(); i++) %7B%0A            char c = input.charAt(i);%0A            if (c == '*' %7C%7C c == '-' %7C%7C c == '+') %7B%0A                List%3CInteger%3E left = diffWaysToCompute(input.substring(0, i));%0A                List%3CInteger%3E right = diffWaysToCompute(input.substring(i + 1, input.length()));%0A                for (int j = 0; j %3C left.size(); j++) %7B%0A                    for (int k = 0; k %3C right.size(); k++) %7B%0A                        res.add(calculate(c, left.get(j), right.get(k)));%0A                    %7D%0A                %7D%0A            %7D%0A        %7D%0A        if (res.size() == 0) %7B%0A            res.add(Integer.parseInt(input));%0A        %7D%0A        return res;%0A    %7D%0A%0A    private int calculate(char op, int a, int b) %7B%0A        return op == '*' ? a * b : op == '+' ? a + b : a - b;%0A    %7D%0A%0A%7D%0A

add Different Ways to Add Parentheses