## 1106. 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.

## Rust Solution

``````struct Solution;

use std::iter::Peekable;
use std::str::Chars;
use std::vec::IntoIter;

enum Tok {
Bool(bool),
Op(char),
}

impl Solution {
fn parse_bool_expr(expression: String) -> bool {
let tokens = Self::parse_tokens(&mut expression.chars());
let mut it = tokens.into_iter().peekable();
Self::parse(&mut it)
}

fn parse(it: &mut Peekable<IntoIter<Tok>>) -> bool {
let tok = it.next().unwrap();
match tok {
Tok::Bool(b) => b,
Tok::Op('!') => {
it.next();
let res = !Self::parse(it);
it.next();
res
}
Tok::Op('&') => {
it.next();
let mut res = Self::parse(it);
while let Some(&Tok::Op(',')) = it.peek() {
it.next();
res &= Self::parse(it);
}
it.next();
res
}
Tok::Op('|') => {
it.next();
let mut res = Self::parse(it);
while let Some(&Tok::Op(',')) = it.peek() {
it.next();
res |= Self::parse(it);
}
it.next();
res
}
_ => panic!(),
}
}

fn parse_tokens(it: &mut Chars) -> Vec<Tok> {
let mut res = vec![];
for c in it {
let tok = match c {
't' => Tok::Bool(true),
'f' => Tok::Bool(false),
_ => Tok::Op(c),
};
res.push(tok);
}
res
}
}

#[test]
fn test() {
let expression = "!(f)".to_string();
let res = true;
assert_eq!(Solution::parse_bool_expr(expression), res);
let expression = "|(f,t)".to_string();
let res = true;
assert_eq!(Solution::parse_bool_expr(expression), res);
let expression = "&(t,f)".to_string();
let res = false;
assert_eq!(Solution::parse_bool_expr(expression), res);
let expression = "|(&(t,f,t),!(t))".to_string();
let res = false;
assert_eq!(Solution::parse_bool_expr(expression), res);
}
``````

Having problems with this solution? Click here to submit an issue on github.