Parsing A Boolean Expression
Hard
2 views
Topics:
RecursionStacksStrings
A boolean expression is an expression that evaluates to either true or false. It can be in one of the following shapes:
't'that evaluates totrue.'f'that evaluates tofalse.'!(subExpr)'that evaluates to the logical NOT of the inner expressionsubExpr.'&(subExpr1, subExpr2, ..., subExprn)'that evaluates to the logical AND of the inner expressionssubExpr1, subExpr2, ..., subExprnwheren >= 1.'|(subExpr1, subExpr2, ..., subExprn)'that evaluates to the logical OR of the inner expressionssubExpr1, subExpr2, ..., subExprnwheren >= 1.
Given a string expression that represents a boolean expression, return the evaluation of that expression.
It is guaranteed that the given expression is valid and follows the given rules.
Example 1:
Input: expression = "&(|(f))" Output: false Explanation: First, evaluate |(f) --> f. The expression is now "&(f)". Then, evaluate &(f) --> f. The expression is now "f". Finally, return false.
Example 2:
Input: expression = "|(f,f,f,t)" Output: true Explanation: The evaluation of (false OR false OR false OR true) is true.
Example 3:
Input: expression = "!(&(f,t))" Output: true Explanation: First, evaluate &(f,t) --> (false AND true) --> false --> f. The expression is now "!(f)". Then, evaluate !(f) --> NOT false --> true. We return true.
Constraints:
1 <= expression.length <= 2 * 104- expression[i] is one following characters:
'(',')','&','|','!','t','f', and','.
Solution
Clarifying Questions
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
- What characters can appear in the boolean expression beyond parentheses, 'true', 'false', '&', and '|'? Are spaces allowed?
- Is operator precedence enforced? If so, what is the precedence order (e.g., is '&' higher precedence than '|' or vice versa)?
- What should the function return if the expression is invalid or malformed (e.g., missing parentheses, invalid characters)? Should I throw an exception, or return a specific boolean value?
- Is the expression guaranteed to be non-empty? What should be returned if the expression is an empty string?
- Are the keywords 'true' and 'false' case-sensitive?
Brute Force Solution
Approach
When parsing a boolean expression the brute force way, we consider every possible combination of interpreting the expression. We evaluate each possibility to determine if it results in true or false. After evaluating all possible scenarios, we can determine the final result.
Here's how the algorithm would work step-by-step:
- Start by considering all possible ways to interpret the expression, paying attention to the order of operations.
- For each possible interpretation, work through the expression step-by-step, evaluating each part.
- If you encounter a variable, try substituting both 'true' and 'false' for it in each evaluation.
- Evaluate logical operators like 'AND', 'OR', and 'NOT' according to their standard rules.
- Continue breaking down the expression until you reach a single 'true' or 'false' value for that particular interpretation.
- Repeat this process for every possible interpretation of the expression.
- Finally, analyze all the results you've collected to determine the overall outcome based on the problem's requirements. Perhaps you need to find just one interpretation that results in 'true', or perhaps you need to find all interpretations that result in 'true'.
Code Implementation
def parse_boolean_expression_brute_force(expression):
# This function exhaustively checks all variable assignments.
variables = set()
for char in expression:
if char.isalpha():
variables.add(char)
variable_list = list(variables)
number_of_variables = len(variable_list)
number_of_combinations = 2**number_of_variables
results = []
for i in range(number_of_combinations):
# Generate a truth assignment for each combination.
variable_values = {}
for j in range(number_of_variables):
if (i >> j) & 1:
variable_values[variable_list[j]] = True
else:
variable_values[variable_list[j]] = False
# Evaluate the expression with the current assignment.
result = evaluate_expression(expression, variable_values)
results.append(result)
return results
def evaluate_expression(expression, variable_values):
expression = expression.replace(' ', '')
def evaluate(sub_expression):
if sub_expression == 'true':
return True
if sub_expression == 'false':
return False
if sub_expression in variable_values:
return variable_values[sub_expression]
# Handle NOT operator
if sub_expression.startswith('!'):
operand = evaluate(sub_expression[1:])
return not operand
# Find the AND or OR operator with the lowest precedence.
and_index = -1
or_index = -1
parenthesis_level = 0
for index, char in enumerate(sub_expression):
if char == '(':
parenthesis_level += 1
elif char == ')':
parenthesis_level -= 1
elif char == '&' and parenthesis_level == 0:
and_index = index
elif char == '|' and parenthesis_level == 0:
or_index = index
# Evaluate AND operation.
if and_index != -1:
left_operand = evaluate(sub_expression[:and_index])
right_operand = evaluate(sub_expression[and_index + 1:])
return left_operand and right_operand
# Evaluate OR operation.
if or_index != -1:
left_operand = evaluate(sub_expression[:or_index])
right_operand = evaluate(sub_expression[or_index + 1:])
return left_operand or right_operand
# Handle parentheses.
if sub_expression.startswith('(') and sub_expression.endswith(')'):
return evaluate(sub_expression[1:-1])
return False # Should not reach here
return evaluate(expression)
Big(O) Analysis
Time Complexity
O(2^n) – The algorithm considers all possible interpretations of a boolean expression. The dominant factor impacting runtime is the number of possible truth assignments for variables. If the expression contains 'n' distinct variables, each variable can be either 'true' or 'false', leading to 2^n possible combinations. Evaluating the expression for each combination takes O(n) time (assuming expression length is n), but the 2^n term dominates. Therefore, the time complexity is O(2^n).
Space Complexity
O(N) – The plain English explanation describes considering all possible interpretations of the boolean expression. In the worst-case scenario, this would involve creating temporary copies of subexpressions or storing intermediate results for each possible interpretation, potentially leading to a number of copies proportional to the length of the expression. Also, if the expression contains N variables, evaluating all true/false combinations of them may require storing up to 2^N intermediate results or copies of subexpressions depending on implementation. Thus, the auxiliary space used is determined by the size of the expression itself, represented by N. Therefore, the auxiliary space complexity is O(N).
Optimal Solution
Approach
The most efficient way to solve this problem is using a method that understands the order of operations and simplifies the expression bit by bit. This approach uses something called recursion which means solving a smaller version of the same problem until you get to the answer. By breaking down the complex expression into manageable parts, the answer becomes simple.
Here's how the algorithm would work step-by-step:
- Imagine we're peeling an onion, we want to start with the innermost part of the expression, usually something inside parentheses.
- First, figure out which parts of the expression need to be calculated first by looking for the deepest set of parentheses. Evaluate the expression inside those parentheses.
- Once the innermost part is calculated, replace that part with its result, making the overall expression simpler.
- Repeat the process of finding the next innermost set of parentheses and calculating its value. Keep doing this until there are no more parentheses.
- Now, you should be left with a simplified expression with just ANDs, ORs, NOTs and simple True/False values. Evaluate the 'NOT' operations first.
- After all the 'NOT' operations are done, evaluate the 'AND' operations from left to right.
- Finally, evaluate the 'OR' operations from left to right. This leaves you with the final True or False result of the whole expression.
- By breaking down the problem into smaller parts and evaluating them in the right order, we can efficiently find the final result without having to try out every single possibility.
Code Implementation
def parse_boolean_expression(expression):
def evaluate(sub_expression):
if '(' not in sub_expression:
# Base case: no more parentheses, evaluate directly
sub_expression = evaluate_not(sub_expression)
sub_expression = evaluate_and(sub_expression)
sub_expression = evaluate_or(sub_expression)
return sub_expression
start_index = sub_expression.rfind('(')
end_index = find_matching_paren(sub_expression, start_index)
inner_expression = sub_expression[start_index + 1:end_index]
result = evaluate(inner_expression)
return evaluate(sub_expression[:start_index] + result + sub_expression[end_index + 1:])
def find_matching_paren(expression, start_index):
count = 1
for i in range(start_index + 1, len(expression)):
if expression[i] == '(':
count += 1
elif expression[i] == ')':
count -= 1
if count == 0:
return i
return -1
def evaluate_not(expression):
index = 0
while index < len(expression):
if expression[index] == '!':
#Evaluate the NOT operation.
operand = expression[index + 1]
result = 'F' if operand == 'T' else 'T'
expression = expression[:index] + result + expression[index + 2:]
else:
index += 1
return expression
def evaluate_and(expression):
index = 0
while index < len(expression):
if expression[index] == '&':
# Evaluate AND operation from left to right.
left_operand = expression[index - 1]
right_operand = expression[index + 1]
result = 'T' if left_operand == 'T' and right_operand == 'T' else 'F'
expression = expression[:index - 1] + result + expression[index + 2:]
index -= 1 # Adjust index due to string replacement
else:
index += 1
return expression
def evaluate_or(expression):
index = 0
while index < len(expression):
if expression[index] == '|':
# Evaluate OR operation from left to right.
left_operand = expression[index - 1]
right_operand = expression[index + 1]
result = 'T' if left_operand == 'T' or right_operand == 'T' else 'F'
expression = expression[:index - 1] + result + expression[index + 2:]
index -= 1 # Adjust index due to string replacement
else:
index += 1
return expression
final_result = evaluate(expression)
return final_result == 'T'Big(O) Analysis
Time Complexity
O(n^2) – The algorithm recursively processes the input string of length n. Finding the innermost parentheses involves scanning the string, potentially taking O(n) in each recursive call. Evaluating the expression within those parentheses and replacing it back into the original string also takes O(n) in each recursive call. Since the expression is simplified and reduced in length with each recursion, in the worst case, we might need to perform these operations on a significant portion of the string multiple times, leading to roughly O(n) work for each of O(n) recursive calls to evaluate parens and simplify the expression. The operations of resolving NOT, AND, and OR operations also take O(n) to iterate through the string. Therefore, the overall time complexity is dominated by the potentially O(n) operations within potentially O(n) levels of recursion which leads to O(n^2).
Space Complexity
O(N) – The recursion depth depends on the nesting level of the parentheses. In the worst-case scenario, the expression could consist of nested parentheses leading to a recursion depth of N, where N is the length of the expression. Each recursive call consumes stack space, thus the auxiliary space due to the recursion stack is O(N). Additionally, temporary string objects are created when replacing the evaluated expressions, which, in the worst case, can also contribute O(N) to the space complexity.
Edge Cases
| Case | How to Handle |
|---|---|
| Empty or Null Input String | Return a default value (e.g., false, or throw an IllegalArgumentException) indicating an invalid expression. |
| Input string with only whitespace | Trim the input string before parsing to handle whitespace-only expressions. |
| Invalid characters in the expression (e.g., '%', '$') | Throw an exception (e.g., IllegalArgumentException) or return an error code indicating invalid syntax. |
| Unbalanced parentheses (more opening or closing) | Detect and report unbalanced parentheses as a syntax error using a stack to track them. |
| Nested parentheses with high depth | Ensure the solution handles deeply nested parentheses without causing stack overflow errors (consider iterative approach). |
| Consecutive operators (e.g., 'true && && false') | Detect and report consecutive operators as a syntax error because that shouldnt occur in correct expressions. |
| Missing operands for operators (e.g., 'true &&') | Detect missing operands and report as syntax errors or evaluate to a predefined value (e.g., false). |
| Large input string exceeding memory limits | Implement input validation to prevent excessively large expressions from causing memory exhaustion or consider streaming input processing. |
Explore Interview QuestionsGoogle Interview QuestionsMeta Interview QuestionsAmazon Interview QuestionsApple Interview QuestionsNetflix Interview Questions
Explore Jobs By LevelEntry-Level Software Engineer JobsMid-Level Software Engineer JobsSenior Software Engineer JobsStaff Software Engineer Jobs
