Parsing A Boolean Expression

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.

Solutions

🧠 Cpp

class Solution
{
    // IN: string with coma separated BOOL expressions
    // OUT: list of corresponding BOOL values
    list<bool> deduceBoolList(string exprs)
    {
        list<bool> res;

        const char *c_exprs = exprs.c_str();
        do
        {
            //if we are on coma. step over it
            if(*c_exprs == ',')
                c_exprs++;

            //if we have an operator with argumets
            if(c_exprs[1] == '(')
            {
                //to find the end, we must count every ()
                const char *exp_end = c_exprs+2;
                size_t active_parentheses_num = 1;
                while(active_parentheses_num)
                {
                    exp_end++;
                    if(*exp_end == '(')
                        active_parentheses_num++;
                    if(*exp_end == ')')
                        active_parentheses_num--;
                }

                //when end is found form string with whole expression
                string exp(c_exprs, exp_end-c_exprs+1);
                res.push_back(parseBoolExpr(exp));
                c_exprs = exp_end+1;
            }
            else
            {
                string exp(1,*c_exprs);
                res.push_back(parseBoolExpr(exp));
            }

        }
        while(c_exprs = strchr(c_exprs, ','));

        return res;
    }

    using fbbb = function<bool(bool,bool)>;

public:

    bool parseBoolExpr(string expression)
    {
        if(expression == "f")
            return false;
        if(expression == "t")
            return true;

         //3 chars: !()
        string in_parentheses = expression.substr(2, expression.size() - 3);

        //check for !
        if(expression.front() == '!')
            return !parseBoolExpr(in_parentheses); 


        //else we have & or |        
        list<bool> values = deduceBoolList(in_parentheses);
        auto operation = expression.front() == '&' ? 
                         (fbbb)bit_and<bool>() :
                          bit_or<bool>();

        return std::accumulate(values.begin(), values.end(), values.front(),
                               operation);

    }
};