Skip to content

1106. Parsing A Boolean Expression 👍

  • Time:
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
 public:
  bool parseBoolExpr(string expression) {
    int i = 0;
    return parse(expression, i);
  }

 private:
  bool parse(const string& exp, int& i) {
    if (exp[i] == 't') {
      ++i;
      return true;
    }
    if (exp[i] == 'f') {
      ++i;
      return false;
    }
    if (exp[i] == '!') {
      i += 2;
      bool ans = !parse(exp, i);
      ++i;
      return ans;
    }

    bool isAnd = exp[i] == '&';
    bool ans = isAnd;
    i += 2;
    while (exp[i] != ')') {
      bool parsed = parse(exp, i);
      if (isAnd)
        ans &= parsed;
      else
        ans |= parsed;
      if (exp[i] == ',')
        ++i;
    }
    ++i;
    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
  public boolean parseBoolExpr(String expression) {
    return dfs(expression, 0, expression.length() - 1);
  }

  private boolean dfs(final String expression, int s, int e) {
    if (s == e)
      return expression.charAt(s) == 't';

    List<Boolean> exps = new ArrayList<>();
    int layer = 0;
    int left = 0;
    char op = ' ';

    for (int i = s; i <= e; ++i) {
      char c = expression.charAt(i);
      if (layer == 0 && (c == '!' || c == '&' || c == '|'))
        op = c;
      else if (c == '(' && ++layer == 1)
        left = i + 1;
      else if (c == ')' && --layer == 0)
        exps.add(dfs(expression, left, i - 1));
      else if (c == ',' && layer == 1) {
        exps.add(dfs(expression, left, i - 1));
        left = i + 1;
      }
    }

    if (op == '&') {
      boolean ans = true;
      for (boolean exp : exps)
        ans &= exp;
      return ans;
    }

    if (op == '|') {
      boolean ans = false;
      for (boolean exp : exps)
        ans |= exp;
      return ans;
    }

    return !exps.get(0);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
  def parseBoolExpr(self, expression: str) -> bool:
    def dfs(s: int, e: int) -> list[str]:
      if s == e:
        return True if expression[s] == 't' else False

      exps = []
      layer = 0

      for i in range(s, e + 1):
        c = expression[i]
        if layer == 0 and c in '!&|':
          op = c
        elif c == '(':
          layer += 1
          if layer == 1:
            left = i + 1
        elif c == ')':
          layer -= 1
          if layer == 0:
            exps.append(dfs(left, i - 1))
        elif c == ',' and layer == 1:
          exps.append(dfs(left, i - 1))
          left = i + 1

      if op == '|':
        return functools.reduce(operator.or_, exps)
      if op == '&':
        return functools.reduce(operator.and_, exps)
      if op == '!':
        return not exps[0]

    return dfs(0, len(expression) - 1)