gistfile1.java

  public boolean solve(String equation) {
    StringTokenizer t = new StringTokenizer(equation, " ()", true);
    List<String> parsed = new ArrayList<String>();
    while (t.hasMoreTokens()) {
      parsed.add(t.nextToken().trim());
    }
    return solveSubExpression(parsed, new int[]{0, 0});
  }

  public boolean solveSubExpression(List<String> parsed, int[] limits) {
    int current = limits[0];
    List<Boolean> operands = new ArrayList<Boolean>();
    List<String> ops = new ArrayList<String>();
    while (true) {

      if (parsed.get(current).equals("OR") || parsed.get(current).equals("AND") || parsed.get(current).equals("XOR")) {
        ops.add(parsed.get(current));
      } else if (parsed.get(current).equals("true")) {
        operands.add(true);
      } else if (parsed.get(current).equals("false")) {
        operands.add(false);
      } else if (parsed.get(current).equals("(")) {
        int[] childLimits = new int[]{limits[0] + 1, 0};
        operands.add(solveSubExpression(parsed, childLimits));
        current = childLimits[1] + 1; // restart computation after
      }

      if (current >= (parsed.size() - 1) || parsed.get(current).equals(")")) {
        // we ended a boolean evaluation
        // ( true AND false )
        // here, we can't have any kind of paranthesis
        boolean tmp = operands.get(0);
        for (int i = 1; i < operands.size(); i++) {
          int opsIndex = i - 1;
          if (ops.get(opsIndex).equals("OR")) {
            tmp |= operands.get(i);
          } else if (ops.get(opsIndex).equals("AND")) {
            tmp &= operands.get(i);
          } else if (ops.get(opsIndex).equals("AND")) {
            tmp ^= operands.get(i);
          }
        }
        limits[1] = current;
        return tmp;
      }
      current++;
    }
  }