397. Truth Expression
A rule engine stores its conditions as compact text. The symbol t means true and f means false. A larger condition is written as !(e) (the opposite of the single condition e), &(e1,e2,...) (true only if all listed conditions are true) or |(e1,e2,...) (true if at least one listed condition is true). Conditions may be nested to any depth, and lists are separated by single commas with no spaces.
Given a well-formed condition text expression, return the truth value it evaluates to. The text can be tens of thousands of characters long and deeply nested, so a recursive evaluator may overflow the call stack in some languages and repeatedly rewriting the text is far too slow; aim for a single left-to-right pass.
Example 1
- Input:
- expression = "|(&(t,f,t),!(&(f,t)))"
- Output:
- true
- Explanation:
&(t,f,t) is false; &(f,t) is false so !(...) is true; |(false,true) is true.
Example 2
- Input:
- expression = "&(|(f,f),!(f),t)"
- Output:
- false
- Explanation:
|(f,f) is false, so the whole & list contains a false operand and the result is false.
Constraints
1 ≤ expression.length ≤ 4 * 104
The expression is valid and uses only the characters t f ! & | ( ) ,& and | lists have at least one operand; ! has exactly one.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)