Parsing A Boolean Expression

LeetCode Q 1106 - Parsing A Boolean Expression

Return the result of evaluating a given boolean expression, represented as a string. An expression can either be:

• "t", evaluating to True;
• "f", evaluating to False;
• "!(expr)", evaluating to the logical NOT of the inner expression expr;
• "&(expr1,expr2,...)", evaluating to the logical AND of 2 or more inner expressions expr1, expr2, …;
• "|(expr1,expr2,...)", evaluating to the logical OR of 2 or more inner expressions expr1, expr2, …

Example 1: Input: expression = "!(f)" ; Output: true
Example 2: Input: expression = "|(f,t)" ; Output: true
Example 3: Input: expression = "&(t,f)" ; Output: false
Example 4: Input: expression = "|(&(t,f,t),!(t))" ; Output: false

Constraints:

• 1 <= expression.length <= 20000
• expression[i] consists of characters in {'(', ')', '&', '|', '!', 't', 'f', ','}.
• expression is a valid expression representing a boolean, as given in the description.

Solution: Stack

The key point is we also push '(' in to stack flags to seperate different expressions.

Code:

public boolean parseBoolExpr(String expression) {
  Deque<Character> signs = new ArrayDeque<>();
  Deque<Character> flags = new ArrayDeque<>();

  for (char ch: expression.toCharArray()) {
    if (ch == 't' || ch == 'f' || ch == '(')
      flags.push(ch);
    else if (ch == '&' || ch == '|' || ch == '!')
      signs.push(ch);
    else if (ch == ')') {
      char sign = signs.pop();

      String str = "";
      while (!flags.isEmpty() && flags.peek() != '(')
        str += flags.pop();

      boolean flag = evaluateFlags(str, sign);

      if (!flags.isEmpty()) flags.pop(); // pop previous '('

      if (flag) flags.push('t');
      else flags.push('f');
    }
  }

  char res = flags.pop();
  if(res == 't') return true;

  return false;
}

private boolean evaluateFlags (String str, char operator) {
  if (operator == '&') {
    for (char ch: str.toCharArray()) {
      if (ch == 'f') return false;
    }
    return true;
  } else if (operator == '|') {
    for (char ch: str.toCharArray()) {
      if (ch == 't') return true;
    }
    return false;
  } else {
    return str.equals("t") ? false : true;
  }
}