Stack Title: parsing Boolean expressions

subject

Title and provenance

title ： Parse Boolean expressions

Source ：1106. Parse Boolean expressions

difficulty

6 level

Title Description

requirement

Give you a Boolean expression in the form of a string $\text{expression}$, Returns the result of the expression .

Valid expressions follow the following conventions ：

• $\text{"t"}$, The result of operation is $\text{True}$;
• $\text{"f"}$, The result of operation is $\text{False}$;
• $\text{"!(expr)"}$, The operation is on the internal expression $\text{expr}$ Perform logical non operation ;
• $\text{"\&(expr1,expr2,…)"}$, The operation process is to $\text{2}$ One or more inner expressions $\text{expr1, expr2, …}$ Perform logical and operations ;
• $\text{"|(expr1,expr2,…)"}$, The operation process is to $\text{2}$ One or more inner expressions $\text{expr1, expr2, …}$ Perform the operation of logical or .

Example

Example 1：

Input ：$\text{expression = "!(f)"}$
Output ：$\text{true}$

Example 2：

Input ：$\text{expression = "|(f,t)"}$
Output ：$\text{true}$

Example 3：

Input ：$\text{expression = "\&(t,f)"}$
Output ：$\text{false}$

Example 4：

Input ：$\text{expression = "|(\&(t,f,t),!(t))"}$
Output ：$\text{false}$

Data range

• $\text{1}\le \text{expression.length}\le \text{20000}$
• $\text{expression}$ from $\text{{‘(’, ‘)’, ‘\&’, ‘|’, ‘!’, ‘t’, ‘f’, ‘,’}}$ The characters in consist of
• $\text{expression}$ Is a valid expression given in the above form , Represents a Boolean value

solution

Ideas and algorithms

In Boolean expressions , Each logical operator （ And 、 or 、 Not ） All operations are performed on the inner expressions in the following pair of parentheses . Because we need to parse and operate according to each pair of matching parentheses , Finding matching parentheses requires the aid of stack data structures , Therefore, we can use the stack to parse Boolean expressions .

Because the comma in Boolean expression is used to separate internal expression , It does not affect the result of Boolean expression , So you can skip commas , Parsing and operation only for non bracketed characters .

Traverse Boolean expressions from left to right $\text{expression}$, Characters that are not parentheses and not right parentheses are put on the stack , When you encounter the right parenthesis, you start parsing , The parsing process is as follows .

1. Stack the elements in the stack in turn , Until the left parenthesis , Calculate the stack $\text{‘t’}$ and $\text{‘f’}$ The number of .

2. Put the left bracket out of the stack , Then stack the logical operators .

3. Calculate the value of the current internal expression according to the logical operator ：

   • If the logical operator is $\text{‘\&’}$, It is logic and operation , When $\text{‘f’}$ The number of is equal to $0$ when , The value of the inner expression is $\text{‘t’}$, Otherwise, the value of the inner expression is $\text{‘f’}$.

   • If the logical operator is $\text{‘|’}$, Is a logical or operation , When $\text{‘t’}$ The number of is greater than $0$ when , The value of the inner expression is $\text{‘t’}$, Otherwise, the value of the inner expression is $\text{‘f’}$.

   • If the logical operator is $\text{‘!’}$, Is a logical non operation , When $\text{‘f’}$ The number of is greater than $0$ when , The value of the inner expression is $\text{‘t’}$, Otherwise, the value of the inner expression is $\text{‘f’}$.

4. Put the value of the internal expression on the stack .

Repeat the above operation , Until the Boolean expression is traversed .

because $\text{expression}$ Is a valid Boolean expression , Therefore, it must be able to correctly interpret , At the end of traversal , There is only one element in the stack , Is the result of a Boolean expression . If the element in the stack is $\text{‘t’}$, return $\text{true}$, Otherwise return to $\text{false}$.

Code

class Solution {
    
    public boolean parseBoolExpr(String expression) {
    
        Deque<Character> stack = new ArrayDeque<Character>();
        int length = expression.length();
        for (int i = 0; i < length; i++) {
    
            char c = expression.charAt(i);
            if (c == ',') {
    
                continue;
            } else if (c == ')') {
    
                int tCount = 0, fCount = 0;
                while (stack.peek() != '(') {
    
                    char prev = stack.pop();
                    if (prev == 't') {
    
                        tCount++;
                    } else if (prev == 'f') {
    
                        fCount++;
                    }
                }
                stack.pop();
                char op = stack.pop();
                if (op == '&') {
    
                    char curr = fCount == 0 ? 't' : 'f';
                    stack.push(curr);
                } else if (op == '|') {
    
                    char curr = tCount > 0 ? 't' : 'f';
                    stack.push(curr);
                } else if (op == '!') {
    
                    char curr = fCount > 0 ? 't' : 'f';
                    stack.push(curr);
                }
            } else {
    
                stack.push(c);
            }
        }
        return stack.pop() == 't';
    }
}

Complexity analysis

• Time complexity ：$O(n)$, among $n$ Is a Boolean expression $\text{expression}$ The length of . You need to traverse the Boolean expression once , Each character can be put on and out of the stack at most once .

• Spatial complexity ：$O(n)$, among $n$ Is a Boolean expression $\text{expression}$ The length of . The space complexity mainly depends on the stack space , The number of elements in the stack will not exceed $n$.