Skip to content

Different Ways to Add Parentheses (diff idea)

Tim_Gao edited this page Sep 15, 2016 · 1 revision
  1. Different from normal expression evaluation
public class Solution {
    private boolean isOperator(char ch){
        if (ch == '*' || ch == '-' || ch == '+'){
            return true;
        } else {
            return false;
        }
    }
    private int cal(int l, int r, char op){
        if (op == '+'){
            return l+r;
        } else if (op == '-'){
            return  l-r;
        } else if (op == '*'){
            return l*r;
        }
        return 0;
    }
    public List<Integer> diffWaysToCompute(String input) {
        ArrayList<Integer> res = new ArrayList<>();
        for (int i=0; i<input.length(); ++i){
            if(isOperator(input.charAt(i))){
                List<Integer> left = diffWaysToCompute(input.substring(0, i));
                List<Integer> right = diffWaysToCompute(input.substring(i+1));
                for (int l=0; l<left.size(); ++l){
                    for (int r = 0; r<right.size(); ++r){
                        res.add(cal(left.get(l), right.get(r), input.charAt(i)));
                    }
                }
            }
        }
        if (res.size() == 0){
            res.add(Integer.parseInt(input));
        }
        return res;
    }
}

Clone this wiki locally