CTCI 9.11

Given a boolean expression consisting of the symbols 0, 1, &, |, and ^, and a desired boolean result value result, implement a function to count the number of ways of parenthesizing the expression such that it evaluates to result.
Example: (1^0|0|1, true)

CTCI 9.11.java

public static int countParenthesizeWays(String input, boolean result){
    HashMap<String, Integer> map = new HashMap<>();
    return countParenthesizeWays(input, result, 0, input.length() - 1, map);
}

public static int countParenthesizeWays(String input, boolean result, int begin, int end, HashMap<String, Integer> map){
    if(begin == end){
        if(input.charAt(begin) == '1' && result) return 1;
        else if(input.charAt(begin) == '0' && !result) return 1;
        else return 0;
    }
    String thisFormular = "" + result + begin + end;
    if(map.containsKey(thisFormular)) return map.get(thisFormular);
    int count = 0;
    if(result){
        for(int i = begin + 1; i < end; i += 2){
            if(input.charAt(i) == '|'){
                count += countParenthesizeWays(input, true, begin, i - 1, map) * countParenthesizeWays(input, true, i + 1, end, map);
                count += countParenthesizeWays(input, true, begin, i - 1, map) * countParenthesizeWays(input, false, i + 1, end, map);
                count += countParenthesizeWays(input, false, begin, i - 1, map) * countParenthesizeWays(input, true, i + 1, end, map);
            }
            else if(input.charAt(i) == '&'){
                count += countParenthesizeWays(input, true, begin, i - 1, map) * countParenthesizeWays(input, true, i + 1, end, map);
            }
            else if(input.charAt(i) == '^'){
                count += countParenthesizeWays(input, true, begin, i - 1, map) * countParenthesizeWays(input, false, i + 1, end, map);
                count += countParenthesizeWays(input, false, begin, i - 1, map) * countParenthesizeWays(input, true, i + 1, end, map);
            }
        }
    }
    else{
        for(int i = begin + 1; i < end; i += 2){
            if(input.charAt(i) == '|'){
                count += countParenthesizeWays(input, false, begin, i - 1, map) * countParenthesizeWays(input, false, i + 1, end, map);
            }
            else if(input.charAt(i) == '&'){
                count += countParenthesizeWays(input, false, begin, i - 1, map) * countParenthesizeWays(input, false, i + 1, end, map);
                count += countParenthesizeWays(input, true, begin, i - 1, map) * countParenthesizeWays(input, false, i + 1, end, map);
                count += countParenthesizeWays(input, false, begin, i - 1, map) * countParenthesizeWays(input, true, i + 1, end, map);
            }
            else if(input.charAt(i) == '^'){
                count += countParenthesizeWays(input, true, begin, i - 1, map) * countParenthesizeWays(input, true, i + 1, end, map);
                count += countParenthesizeWays(input, false, begin, i - 1, map) * countParenthesizeWays(input, false, i + 1, end, map);
            }
        }
    }
    map.put(thisFormular, count);
    return count;
}