Problem Description:

Given a boolean expression consisting of the constants "true" and "false", the operators "&" (AND), "|" (OR), and "!" (NOT), and parentheses, evaluate the expression and return its result.

The expression is represented in the following syntax:

Expression ::= "true" | "false" | Expression "&" Expression | Expression "|" Expression | "!" Expression | "(" Expression ")"

Example 1:

Input: expression = "!(true)&false" Output: false Explanation: The expression is equivalent to "!true&false" which evaluates to false. Example 2:

Input: expression = "|(false)" Output: false Example 3:

Input: expression = "!(false)&!(false|true)&!(true)" Output: true

Solution:

The task is to parse a boolean expression and evaluate it. In this problem statement, we are given some expressions which may contain boolean operators like OR, AND, NOT, parenthesis, and True, False values. We need to parse the expression and evaluate its value.

Let's first understand the different boolean operators used in this problem:

"!" (NOT) - It is an unary operator. It reverses the value of its operand. For example, if the operand is True, then the value after applying the NOT operator would be False.

"&" (AND) - It is a binary operator. It takes two operands and returns True only if both operands are True.

"|" (OR) - It is a binary operator. It takes two operands and returns True if at least one of the operands is True.

The problem statement consists of two main parts:

Parsing the expression

Evaluating the expression

To parse the expression, we use a stack. Before we go through the code, let's see how we can break down the expression using an example. Consider the following expression:

"!(false)&!(false|true)&!(true)"

We can break down the expression as follows:

("!" (false) ")&("!" (false | true)")&("!" (true))

In the above expression, each parentheses group represents an operand and operator. We can use a stack to store these operands and operators.

To evaluate the expression, we use a recursive approach. We evaluate each operand and operator until we get the final result. Let's look at the code for both parts.

Pseudo-code for parsing the expression:

stack = [] for c in expression: if c is ")" : operands = [] while stack[-1] is not "(" : operands.append(stack.pop()) stack.pop() # remove the "(" operator = stack.pop() if operator == "!" : stack.append(evaluate_not(operands[0])) else : stack.append(evaluate_binary(operator, operands[0], operands[1])) else : stack.append(c)

return stack.pop()

In the above code, we scan the input string character by character. If we find a closing parenthesis, we pop elements from the stack until we get an opening parenthesis. We then take the operator and operands out of the stack and evaluate the expression.

Pseudo-code for evaluating the expression:

def evaluate_not(operand): return not operand

def evaluate_binary(operator, operand1, operand2): if operator == "&" : return operand1 and operand2 else : return operand1 or operand2

def evaluate_expression(expression): if expression == "true": return True elif expression == "false": return False else : operator = expression[0] if operator == "!" : return evaluate_not(evaluate_expression(expression[1:])) elif operator == "&" or operator == "|" : operands = get_operands(expression) return evaluate_binary(operator, evaluate_expression(operands[0]), evaluate_expression(operands[1]))

In the above code, we have three functions - evaluate_not, evaluate_binary, and evaluate_expression.

evaluate_not takes one operand and evaluates the NOT operator.

evaluate_binary takes two operands and an operator and evaluates the Boolean expression.

evaluate_expression recursively evaluates the expression until we get the final result.

We also have a utility function called get_operands that splits the expression into two parts before and after the binary operator.

Time Complexity Analysis :

In the worst-case scenario, each one of the “operators” is given by a boolean expression and thus the recursion tree has a depth of n. Thus the time complexity of this solution is O(n).

Space Complexity Analysis :

The space the program requires is because of the stack. The maximum size of the stack is in the worst-case scenario the input string size. The space complexity of this solution is O(n).

Let's look at the complete code now:

function to handle binary operators

def evaluate_binary(operator, operand1, operand2): if operator == "&": return operand1 and operand2 elif operator == "|": return operand1 or operand2

function to handle NOT operator

def evaluate_not(operand): return not operand

utility function to get the operands

def get_operands(expression): stack = [] operands = [] for c in expression: if c == ")" and stack[-1] != "(": operands.append(stack.pop()) elif c == "(" and stack[-1] != ")" : operator = stack.pop() operands.append(operator) elif c == ")" and stack[-1] == "(" : stack.pop() elif c in ["|", "&"] : operands.append(stack.pop()) stack.append(c) elif c == "!" : stack.append(c) else : stack.append(c)

operands.append(stack[-1])

return operands

recursive function to evaluate the expression

def evaluate_expression(expression): if expression == "true": return True elif expression == "false": return False else : operator = expression[0] if operator == "!": return evaluate_not(evaluate_expression(expression[1:])) elif operator == "&" or operator == "|": operands = get_operands(expression[1:-1]) return evaluate_binary(operator, evaluate_expression(operands[0]), evaluate_expression(operands[1]))

main function to parse the expression

def parse_bool_expression(expression): stack = [] for c in expression: if c == ")": operands = [] while stack[-1] != "(": operands.append(stack.pop())

        stack.pop()

        operator = stack.pop()

        if operator == "!":
            stack.append(evaluate_not(operands[0]))
        else:
            stack.append(evaluate_binary(operator, operands[0], operands[1]))
    else:
        stack.append(c)

return stack[-1]

test the code

print(parse_bool_expression("!(true)&false")) # False print(parse_bool_expression("!(false)&!(false|true)&!(true)")) # True print(parse_bool_expression("|(false)")) # False

I hope this explanation is helpful in understanding the solution to the problem of parsing a boolean expression on LeetCode.

1