Parsing A Boolean Expression

A boolean expression is an expression that evaluates to either true or false. It can be in one of the following shapes: 't' which evaluates to true, 'f' which evaluates to false, '!(subExpr)' which evaluates to the logical NOT of the inner expression subExpr, '&(subExpr1, subExpr2, ..., subExprn)' which evaluates to the logical AND of the inner expressions subExpr1, subExpr2, ..., subExprn where n >= 1, or '|(subExpr1, subExpr2, ..., subExprn)' which evaluates to the logical OR of the inner expressions subExpr1, subExpr2, ..., subExprn where n >= 1. Given a string expression representing a boolean expression, return the evaluation of that expression. It is guaranteed that the given expression is valid and follows the given rules.

Constraints

• 1 <= expression.length <= 2 * 10^4
• expression[i] is one of the following characters: '(', ')', '&', '|', '!', 't', 'f', and ','.