> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/stacks-and-queues/parsing-a-boolean-expression.md).

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

```java
class Solution {
    public boolean isSymbol(char c) {
        if (c == '|' || c == '&' || c == '!')
            return true;
        return false;
    }

    public boolean parseBoolExpr(String expression) {
        Stack<Character> bracket = new Stack<>();
        Stack<Character> symbols = new Stack<>();
        for (char c : expression.toCharArray()) {
            if (isSymbol(c))
                symbols.push(c);
            else {
                if (c == ')') {
                    if (symbols.size() == 0) {
                        // This means if given expression is valid then there is only one char between
                        // these braces
                        char temp = bracket.pop();
                        bracket.pop(); // Removing redundant bracket
                        bracket.push(temp);
                    } else {
                        char symbol = symbols.pop();
                        // This means only 1 char will be inside
                        if (symbol == '!') {
                            char temp = bracket.pop();
                            bracket.pop();
                            bracket.push(temp == 't' ? 'f' : 't');
                        } else if (symbol == '|') {
                            boolean ans = false;
                            while (bracket.peek() != '('){
                                if(bracket.peek()==','){
                                    bracket.pop();
                                    continue;
                                }
                                ans = ans || bracket.peek() == 't' ? true : false;
                                bracket.pop();
                            }
                            bracket.pop();
                            bracket.push(ans ? 't' : 'f');
                        } else {
                            boolean ans = true;
                            while (bracket.peek() != '('){
                                if(bracket.peek()==','){
                                    bracket.pop();
                                    continue;
                                }
                                ans = ans && bracket.peek() == 't' ? true : false;
                                bracket.pop();
                            }
                            bracket.pop();
                            bracket.push(ans ? 't' : 'f');
                        }
                    }
                } else
                    bracket.push(c);
            }
        }
        return bracket.pop() == 't' ? true : false;
    }
}
```