Cómo Parsear y Evaluar Expresiones Booleanas en Java

En este artículo, vamos a aprender cómo resolver el problema «Parsing A Boolean Expression» usando Java. Este problema es popular en plataformas como LeetCode y requiere que, dada una cadena que representa una expresión booleana, devolvamos la evaluación de dicha expresión.

Descripción del Problema

Una expresión booleana es aquella que se evalúa como true o false. Puede estar en una de las siguientes formas:

• ‘t’ que se evalúa como true.
• ‘f’ que se evalúa como false.
• ‘!(subExpr)’ que se evalúa como el NOT lógico de la expresión interna subExpr.
• ‘&(subExpr1, subExpr2, …, subExprn)’ que se evalúa como el AND lógico de las expresiones internas subExpr1, subExpr2, …, subExprn donde n >= 1.
• ‘|(subExpr1, subExpr2, …, subExprn)’ que se evalúa como el OR lógico de las expresiones internas subExpr1, subExpr2, …, subExprn donde n >= 1.

Solución en Java

A continuación, presentamos una solución en Java que utiliza un enfoque recursivo para evaluar las expresiones booleanas:

import java.util.*;

public class BooleanExpressionParser {

    public boolean parseBoolExpr(String expression) {
        if (expression == null || expression.isEmpty()) return false;
        return evaluate(expression, 0, expression.length() - 1);
    }

    private boolean evaluate(String expr, int left, int right) {
        if (left == right) {
            return expr.charAt(left) == 't';
        }

        char operator = expr.charAt(left);
        int start = left + 2; // Skip operator and following '('
        int open = 0;

        List<Boolean> subResults = new ArrayList<>();

        for (int i = start; i <= right - 1; i++) { // right - 1 to skip final ')'
            if (expr.charAt(i) == ',' && open == 0) continue; // Ignore commas not within sub-expressions
            if (expr.charAt(i) == '(') open++;
            if (expr.charAt(i) == ')') open--;

            if ((expr.charAt(i) == ',' && open == 0) || i == right - 1) { // End of a sub-expression
                subResults.add(evaluate(expr, start, i));
                start = i + 1;
            }
        }

        switch (operator) {
            case '!':
                return !subResults.get(0);
            case '&':
                for (boolean result : subResults) {
                    if (!result) return false;
                }
                return true;
            case '|':
                for (boolean result : subResults) {
                    if (result) return true;
                }
                return false;
            default:
                return false; // Shouldn't happen
        }
    }

    public static void main(String[] args) {
        BooleanExpressionParser parser = new BooleanExpressionParser();
        System.out.println(parser.parseBoolExpr("&(t,f)")); // Output: false
        System.out.println(parser.parseBoolExpr("|(!t,f)")); // Output: true
        System.out.println(parser.parseBoolExpr("!(&(t,t))")); // Output: true
    }
}

Explicación del Código

La solución se basa en procesar cada tipo de operación lógica por separado y evaluar las subexpresiones contenidas entre paréntesis. Utilizamos el enfoque de dividir y vencer para simplificar la expresión en componentes más pequeños que se evaluarán de manera recursiva.

Una implementación adecuada considera los diferentes operadores lógicos como el NOT (!), AND (&) y OR (|), aplicándolos en el orden correcto para evaluar la expresión completa conforme a las reglas lógicas.