1197. Parsing A Boolean Expression

• Difficulty: Hard

• Topics: String

• Similar Questions:

Problem:

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.

Solutions:

class Solution {
public:
    bool negate(string& expression, int& pos) {
        bool ret = !helper(expression, pos);
        ++pos; // remove )
        return ret;
    }

    bool logicAdd(string& expression, int& pos) {
        bool ret = true;
        do {
            ret = helper(expression, pos) && ret;
        } while (expression[pos++] == ',');
        return ret;
    } 

    bool logicOr(string& expression, int& pos) {
        bool ret = false;
        do {
            ret = helper(expression, pos) || ret;
        } while (expression[pos++] == ',');
        return ret;
    } 

    bool parseBoolExpr(string expression) {
        int pos = 0;
        return helper(expression, pos);
    }

    bool helper(string& expression, int& pos) {
        //bool ret;
        //for (;pos < expression.length(); ++pos) {
            char c = expression[pos];
            if (c == '!') {
                ++pos; // remove !
                ++pos; // remove (
                return negate(expression, pos);
            } 

            if (c == '&') {
                ++pos; // remove &
                ++pos; // remove (
                return logicAdd(expression, pos);
            }

            if (c == '|') {
                ++pos; // remove |
                ++pos; // remove (
                return logicOr(expression, pos);
            }

            ++pos;
            if (c == 't') {
                return true;
            }
            else return false;
        //}
    }
};