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'that evaluates totrue.'f'that evaluates tofalse.'!(subExpr)'that evaluates to the logical NOT of the inner expressionsubExpr.'&(subExpr1, subExpr2, ..., subExprn)'that evaluates to the logical AND of the inner expressionssubExpr1, subExpr2, ..., subExprnwheren >= 1.'|(subExpr1, subExpr2, ..., subExprn)'that evaluates to the logical OR of the inner expressionssubExpr1, subExpr2, ..., subExprnwheren >= 1.
Given a string expression that represents a boolean expression, return the evaluation of that expression.
It is guaranteed that the given expression is valid and follows the given rules.
Example 1
Input
expression = "&(|(f))"Output
falseFirst evaluate
|(f) to f, then evaluate &(f) to f, so the final result is false.Example 2
Input
expression = "|(f,f,f,t)"Output
trueThe evaluation of
(false OR false OR false OR true) is true.Constraints
- 1 <= expression.length <= 2 * 10^4
- expression[i] is one following characters:
'(',')','&','|','!','t','f', and','.