1
class Solution {
2

3
  int pos = 0;
4

5
  public boolean parseBoolExpr(String s) {
6
    pos = 0;
7
    return solve(s, '-');
8
  }
9

10
  public boolean solve(String s, char prev_sign) {
11

12
    boolean res = s.charAt(pos) == 'f' ? false : true;
13
    char cur_sign = ' ';
14
    int flag_res_init = 0;
15
    while (pos < s.length()) {
16

17
      char cur_char = s.charAt(pos++);
18

19
      if (isExpr(cur_char)) {
20
        res = eval(cur_char == 't' ? true : false, res, prev_sign);
21
      } else if (isSign(cur_char)) {
22
        cur_sign = cur_char;
23
      } else if (cur_char == '(') {
24
        if (flag_res_init == 1 || prev_sign == '!') res = eval(solve(s, cur_sign), res, prev_sign);
25
        else {
26
          res = solve(s, cur_sign);
27
          flag_res_init = 1;
28
        }
29
      } else if (cur_char == ')') {
30
        return res;
31
      }
32
    }
33
    return res;
34
  }
35

36
  public boolean isExpr(char c) {
37
    return (c == 'f' || c == 't');
38
  }
39

40
  public boolean isSign(char c) {
41
    return (c == '!' || c == '&' || c == '|');
42
  }
43

44
  public boolean eval(boolean e1, boolean e2, char sign) {
45

46
    boolean res = false;
47
    if (sign == '!') res = !e1;
48
    else if (sign == '|') res = e1 | e2;
49
    else if (sign == '&') res = e1 & e2;
50

51
    return res;
52
  }
53
}