A Nested Logic Formula

Hard

You are given a string formula holding a logical formula. Evaluate it and return True or False. A formula is built as follows: - t is true and f is false; - !(x) is the negation of the formula x; - &(x1,x2,...,xk) is the logical AND of the formulas x1, ..., xk, where k ≥ 1; - |(x1,x2,...,xk) is the logical OR of the formulas x1, ..., xk, where k ≥ 1. Arguments are separated by commas with no spaces. The formula is always well formed.

Example 1

formula="&(t,!(f),|(f,t))" → True

!(f) is true and |(f,t) is true, so the AND of three true values is true.

Example 2

formula="|(f,&(t,f),!(t))" → False

&(t,f) is false and !(t) is false, so the OR of three false values is false.

Example 3

formula="!(!(f))" → False

Constraints

1 ≤ len(formula) ≤ 2·10⁴
formula contains only the characters (, ), &, |, !, t, f and ,
The formula is well formed

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Stack Recursion String

Similar problems

Plus-Minus Calculator With Brackets Hard A Calculator With Brackets and Variables Hard Simplify a Letter Polynomial Hard Calculator With Brackets and Four Operations Hard Expand Repeat Brackets Medium

Input

formula="&(t,!(f),|(f,t))"

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 129 tests on the server, hidden ones included.