problemmediumdatabaseleetcode-1440leetcode 1440leetcode1440

Evaluate Boolean Expression

MediumUpdated: Aug 2, 2025
Practice on:
LeetCode

Problem

Table Variables:

+---------------+---------+
| Column Name   | Type    |
+---------------+---------+
| name          | varchar |
| value         | int     |
+---------------+---------+
In SQL, name is the primary key for this table.
This table contains the stored variables and their values.

Table Expressions:

+---------------+---------+
| Column Name   | Type    |
+---------------+---------+
| left_operand  | varchar |
| operator      | enum    |
| right_operand | varchar |
+---------------+---------+
In SQL, (left_operand, operator, right_operand) is the primary key for this table.
This table contains a boolean expression that should be evaluated.
operator is an enum that takes one of the values ('<', '>', '=') The values of left_operand and right_operand are guaranteed to be in the Variables table.

Evaluate the boolean expressions in Expressions table.

Return the result table in any order.

The result format is in the following example.

Examples

Example 1:

Input: 
Variables table:
+------+-------+
| name | value |
+------+-------+
| x    | 66    |
| y    | 77    |
+------+-------+
Expressions table:
+--------------+----------+---------------+
| left_operand | operator | right_operand |
+--------------+----------+---------------+
| x            | >        | y             |
| x            | <        | y             |
| x            | =        | y             |
| y            | >        | x             |
| y            | <        | x             |
| x            | =        | x             |
+--------------+----------+---------------+
Output: 
+--------------+----------+---------------+-------+
| left_operand | operator | right_operand | value |
+--------------+----------+---------------+-------+
| x            | >        | y             | false |
| x            | <        | y             | true  |
| x            | =        | y             | false |
| y            | >        | x             | true  |
| y            | <        | x             | false |
| x            | =        | x             | true  |
+--------------+----------+---------------+-------+
Explanation: 
As shown, you need to find the value of each boolean expression in the table using the variables table.

Solution

Method 1 – Recursive Evaluation with Variable Lookup (SQL, Pandas)

Intuition

To evaluate a boolean expression with variables, recursively parse the expression, replacing variables with their values from the Variables table. Evaluate the expression using standard boolean logic.

Approach

  1. For each expression, recursively parse and evaluate:
    • Replace variable names with their values from the Variables table.
    • Evaluate the expression using boolean logic (AND, OR, NOT, parentheses).
  2. In SQL, use a recursive CTE or a user-defined function to evaluate the expression.
  3. In Pandas, use Python's eval after replacing variable names with their values.
  4. Return the result for each expression.

Code

MySQL
-- This problem is not directly solvable in standard SQL without a UDF or procedural extension.
-- Below is a conceptual approach using a recursive CTE and string replacement (for platforms that support it):
-- Assume Expressions table has columns: id, expr
-- Assume Variables table has columns: name, value
--
-- Pseudocode:
-- For each expression, replace variable names in expr with their values from Variables, then evaluate the boolean expression.
--
-- Example (for platforms with string replace and eval):
-- SELECT id, EVAL(REPLACE_VARIABLES(expr)) AS result FROM Expressions;
PostgreSQL
-- Similar to MySQL, this requires procedural code or an extension to evaluate dynamic expressions.
-- Example using PL/pgSQL or plpythonu extension.
-- Not directly possible in pure SQL.
Python (Pandas)
import pandas as pd
import re

def evaluate_boolean_expressions(variables: pd.DataFrame, expressions: pd.DataFrame) -> pd.DataFrame:
    var_map = dict(zip(variables['name'], variables['value']))
    def eval_expr(expr: str) -> int:
        # Replace variable names with their values
        def repl(m):
            v = m.group(0)
            return str(var_map.get(v, 0))
        expr_eval = re.sub(r'\b[a-zA-Z_][a-zA-Z0-9_]*\b', repl, expr)
        # Replace logical operators with Python equivalents
        expr_eval = expr_eval.replace('AND', 'and').replace('OR', 'or').replace('NOT', 'not')
        return int(eval(expr_eval))
    expressions['result'] = expressions['expr'].apply(eval_expr)
    return expressions[['id', 'result']]

Complexity

  • ⏰ Time complexity: O(n * m) where n is the number of expressions and m is the length of each expression.
  • 🧺 Space complexity: O(m) for the largest expression string.

Comments