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 *.

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]

Understand the problem:
The question can be solved by using divide-and-conquer. We first cut the expression into two halves and calculate the list of result for each half. Then we traverse the two lists and get the final result. 

Code (Java):

public class Solution {
    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> result = new ArrayList<>();
        if (input == null || input.length() == 0) {
            return result;
        }
        
        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            
            if (!isOperator(c)) {
                continue;
            }
            
            List<Integer> left = diffWaysToCompute(input.substring(0, i));
            List<Integer> right = diffWaysToCompute(input.substring(i + 1));
            
            for (int num1 : left) {
                for (int num2 : right) {
                    int val = calculate(num1, num2, c);
                    result.add(val);
                }
            }
        }
        
        // only contains one number
        if (result.isEmpty()) {
            result.add(Integer.parseInt(input));
        }
        
        return result;
    }
    
    private int calculate(int num1, int num2, char operator) {
        int result = 0;
        
        switch(operator) {
            case '+' : result = num1 + num2;
            break;
            
            case '-' : result = num1 - num2;
            break;
            
            case '*' : result = num1 * num2;
            break;
        }
        
        return result;
    }
    
    private boolean isOperator(char operator) {
        return (operator == '+') || (operator == '-') || (operator == '*');
    }
}

Summary:
The problem itself is not hard. The essence of the problem is to compute the different ways to compute the expression. There is only one trick here is how to handle the input has only one number there, e.g. "1". Then we need to add the number into the result list. The idea is to check if the result is empty after the divide-and-conquer step. If it is empty, means only one number left in the input. Note that we cannot check using if the first character of the input string is digit, because each and every input string starts from a number.