# Parsing A Boolean Expression

## [Parsing A Boolean Expression](https://leetcode.com/problems/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

```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);

    }
};
```