2

Estou construindo uma tabela verdade, onde eu recebo uma equação com várias proposições (q, p, r, s) e conectivos (!, *, =).

Minha equação vem no seguinte formato:

String equation = "!(q+p)*r=(s+r)";

A idéia é que eu consiga pegar os valores de dentro do parênteses utilizando um método semelhante ao split, onde eu conseguiria um vetor com todos os valores dentro de parênteses na string, sendo que caso possua vários e caso não exista nenhum parênteses na String, ficando algo do tipo:

equation[0] = (q+p)

equation[1] = (s+r)

Com isso, acho que seria mais simples eu retirar os parênteses depois e conseguir calcular os valores das proposições. Se possível, seria interessante quando houvesse negação (!), a variável também o retornaria:

equation[0] = !(q+p);

Caso depois eu precise tirar os parênteses, como ficaria?

Ex:

String equation = (q+p)

equation[0] = q+p

1 Resposta 1

1

Se você precisa avaliar qualquer tipo possível de equação, regex não é a melhor solução. Eu recomendaria o uso de algum parser específico para a tarefa, pois como veremos abaixo, regex é bem limitada para este tipo de coisa.


Usando um parser

Conforme já explicado aqui, uma opção é usar o Antlr.

Neste projeto também usei o Maven, por facilitar alguns passos, e o JDK 11. A estrutura é bem simples:

ExpressionParser (diretório raiz do projeto)
 |
 |- pom.xml
 |
 |- src/main
         |
         |- java/expressionparser/main
         |     |
         |     |- Main.java
         |     |
         |     |- ExpressionEvaluator.java
         |
         |- antlr4/expressionparser
               |
               |- Expression.g4

No pom.xml adicionamos o Antlr nas dependências, e configuramos o respectivo plugin que fará o build:

<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
    <modelVersion>4.0.0</modelVersion>
    <groupId>com.tests</groupId>
    <artifactId>expressionparser</artifactId>
    <packaging>jar</packaging>
    <version>1.0</version>
    <name>expressionparser</name>
    <properties>
        <antlr4.version>4.3</antlr4.version>
        <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
        <project.reporting.outputEncoding>UTF-8</project.reporting.outputEncoding>
    </properties>
    <build>
        <plugins>
            <plugin>
                <groupId>org.antlr</groupId>
                <artifactId>antlr4-maven-plugin</artifactId>
                <version>${antlr4.version}</version>
                <configuration>
                    <arguments>
                        <argument>-visitor</argument>
                    </arguments>
                </configuration>
                <executions>
                    <execution>
                        <goals>
                            <goal>antlr4</goal>
                        </goals>
                    </execution>
                </executions>
            </plugin>
            <plugin>
                <groupId>org.apache.maven.plugins</groupId>
                <artifactId>maven-compiler-plugin</artifactId>
                <version>3.1</version>
                <configuration>
                    <source>11</source>
                    <target>11</target>
                </configuration>
            </plugin>
            <plugin>
                <groupId>org.codehaus.mojo</groupId>
                <artifactId>exec-maven-plugin</artifactId>
                <version>1.2.1</version>
                <configuration>
                    <mainClass>expressionparser.main.Main</mainClass>
                </configuration>
            </plugin>
        </plugins>
    </build>
    <dependencies>
        <dependency>
            <groupId>org.antlr</groupId>
            <artifactId>antlr4-runtime</artifactId>
            <version>${antlr4.version}</version>
        </dependency>
        <dependency>
            <groupId>org.antlr</groupId>
            <artifactId>antlr4-maven-plugin</artifactId>
            <version>${antlr4.version}</version>
            <scope>compile</scope>
        </dependency>    
    </dependencies>
</project>

Já no arquivo Expression.g4 definimos a gramática das expressões que queremos fazer o parsing:

grammar Expression;

parse : expr;

expr
 : prop EQ prop      #eqExpr
 ;

prop
 : ID                #idExpr
 | prop AND prop     #andExpr
 | prop OR prop      #orExpr
 | NOT prop          #notExpr
 | brackets          #parExpr
 ;


brackets : OPAR prop? CPAR;
OR : '+';
AND : '*';
NOT : '!';
EQ : '=';
OPAR : '(';
CPAR : ')';
ID : [a-zA-Z]+;
SPACE : [ \t\r\n] -> skip;

Basicamente definimos que uma expressão pode ter identificadores (ID, uma sequência de uma ou mais letras). Além disso, expressões podem estar entre parênteses (brackets), e por fim também podemos ter expressões como operandos do operador + (definido por OR), além do * (operador AND) e ! (operador NOT). Por fim, a expressão consiste em duas proposições sendo comparadas com o = (operador EQ).

No final tem uma opção para ignorar um ou mais espaços.

Para saber mais sobre como definir uma gramática, sugiro ler a documentação (aqui e aqui).

A princípio pode parecer mais complicado do que a regex, mas se você aprender ambas verá que na verdade esta é a solução mais adequada.


Por enquanto não precisa criar os arquivos Main.java e ExpressionEvaluator.java. Primeiro rode o Maven:

mvn clean install

Assim ele irá criar o diretório target/generated-sources/antlr4/ na raiz do projeto, com várias classes geradas a partir da gramática que definimos acima:

$ find target/generated-sources/antlr4/
target/generated-sources/antlr4/ExpressionLexer.tokens
target/generated-sources/antlr4/expressionparser
target/generated-sources/antlr4/expressionparser/ExpressionVisitor.java
target/generated-sources/antlr4/expressionparser/ExpressionBaseListener.java
target/generated-sources/antlr4/expressionparser/ExpressionLexer.java
target/generated-sources/antlr4/expressionparser/ExpressionBaseVisitor.java
target/generated-sources/antlr4/expressionparser/ExpressionListener.java
target/generated-sources/antlr4/expressionparser/ExpressionParser.java
target/generated-sources/antlr4/Expression.tokens

Se estiver usando uma IDE, veja como configurá-la para que as classes acima façam parte do classpath do seu projeto (no Netbeans, por exemplo, é automático, veja como é na sua).

A partir daí, podemos criar as nossas classes, que usam o parser e o lexer gerados acima.

Primeiro a classe ExpressionEvaluator:

package expressionparser.main;

import expressionparser.ExpressionBaseVisitor;
import expressionparser.ExpressionParser;
import java.util.HashMap;
import java.util.Map;
import org.antlr.v4.runtime.misc.NotNull;

public class ExpressionEvaluator extends ExpressionBaseVisitor<Boolean> {
    private Map<String, Boolean> props = new HashMap<>();
    public ExpressionEvaluator(Map<String, Boolean> props) {
        this.props = props;
    }

    @Override
    public Boolean visitBrackets(ExpressionParser.BracketsContext ctx) {
        ExpressionParser.PropContext prop = ctx.prop();
        return prop == null ? false : this.visit(prop);
    }
    @Override
    public Boolean visitIdExpr(@NotNull ExpressionParser.IdExprContext ctx) {
        // se não está no Map, assume que é false
        return this.props.getOrDefault(ctx.getText(), Boolean.FALSE);
    }
    @Override
    public Boolean visitEqExpr(@NotNull ExpressionParser.EqExprContext ctx) {
        return visit(ctx.prop(0)).equals(visit(ctx.prop(1)));
    }
    @Override
    public Boolean visitAndExpr(@NotNull ExpressionParser.AndExprContext ctx) {
        return visit(ctx.prop(0)) && visit(ctx.prop(1));
    }
    @Override
    public Boolean visitOrExpr(@NotNull ExpressionParser.OrExprContext ctx) {
        return visit(ctx.prop(0)) || visit(ctx.prop(1));
    }
    @Override
    public Boolean visitNotExpr(@NotNull ExpressionParser.NotExprContext ctx) {
        return !visit(ctx.prop());
    }
}

No caso, eu apenas criei uma subclasse de ExpressionBaseVisitor (que é uma classe que "visita" todos os tokens da expressão sendo analisada).

O Antlr gerou vários métodos como visitAndExpr, que usa o mesmo nome que usamos no arquivo Expression.g4 (no caso, andExpr). Cada método é chamado quando a respectiva expressão é encontrada. Por exemplo, em visitAndExpr, sabemos que há dois operandos que na gramática chamamos de prop, pois foi definida como:

prop AND prop     #andExpr

Assim, usando ctx.prop(0) eu pego o primeiro operando, e ctx.prop(1) pega o segundo. Uso o método visit para calcular de forma recursiva o valor de cada um, e no final uso o operador && para computar o resultado final.

Para as proposições p, q, etc, eu uso um Map, que pode ser customizado à vontade, como veremos a seguir. Se algum valor não estiver no Map, eu considero que é false.


Depois, no arquivo Main.java, basta usar o ExpressionEvaluator para calcular a expressão:

package expressionparser.main;

import expressionparser.ExpressionLexer;
import expressionparser.ExpressionParser;
import java.util.HashMap;
import java.util.Map;
import org.antlr.v4.runtime.ANTLRInputStream;
import org.antlr.v4.runtime.CommonTokenStream;
import org.antlr.v4.runtime.tree.ParseTree;

public class Main {

    public static void main(String[] args) throws Exception {
        String[] entrada = {
            "!(q+p)*r=(s+r)",
            "!(q+(p *r))=s+r*q"
        };
        for (String stringToVerify : entrada) {
            parse(stringToVerify);
        }
    }

    static void parse(String expressao) {
        // proposições, mude à vontade para testar
        Map<String, Boolean> props = new HashMap<>();
        props.put("r", true);
        props.put("q", true);
        props.put("p", false);
        // não precisa adicionar "s", que será false, mas se quiser pode adicionar de forma explícita

        ExpressionLexer lexer = new ExpressionLexer(new ANTLRInputStream(expressao));
        ExpressionParser parser = new ExpressionParser(new CommonTokenStream(lexer));
        ParseTree tree = parser.parse();
        ExpressionEvaluator evaluator = new ExpressionEvaluator(props);
        System.out.printf("\nEntrada: %s\n", expressao);
        System.out.println("result=" + evaluator.visit(tree));
    }
}

Você pode rodar com o próprio Maven se quiser (mvn exec:java).

Desta forma, não importa o tamanho da expressão, se tem ou não parênteses (inclusive aninhados, não há limite de níveis), etc. Assim fica bem mais flexível e fácil de modificar e entender, se comparado a uma regex.


Regex

Se você só quer tratar os casos mais simples (apenas um par de parênteses, sem outros parênteses aninhados), uma solução (ingênua e limitada, já veremos porquê) seria:

List<String> equations = new ArrayList<String>();
Matcher matcher = Pattern.compile("!?\\([^()]+\\)").matcher("!(q+p)*r=(s+r)");
while (matcher.find()) {
    equations.add(matcher.group());
}
System.out.println(equations); // [!(q+p), (s+r)]

A regex possui uma exclamação (!), e o ? logo depois indica que ela é opcional. Depois temos o parênteses de abertura - que em regex deve ser escapado com \, mas dentro de uma string este deve ser escrito como \\, por isso o parênteses fica \\(.

Depois temos uma classe de caracteres negados: [^()]. Ela significa "qualquer coisa que não seja ( nem )" (o que confunde aqui é que dentro de colchetes, os parênteses não precisam ser escapados com \). E o quantificador + significa "uma ou mais ocorrências", ou seja, podemos ter vários caracteres que não sejam parênteses.

Por fim, temos o fechamento dos parênteses: \\). Ou seja, a regex pega um ! opcional, seguido de (, vários caracteres que não são parênteses e ). Eu percorro os matches e vou guardando os resultados em uma lista. No exemplo acima, a lista contém duas strings: "!(q+p)" e "(s+r)".


Se quiser eliminar os parênteses, basta usar replaceAll:

for (String eq : equations) {
    System.out.println(eq.replaceAll("[()]", ""));
}

A regex [()] procura por ( ou ), e o replaceAll substitui estes por uma String vazia (""), que é o mesmo que removê-los. O resultado é:

!q+p
s+r

Evidentemente, para a primeira expressão o resultado está errado, pois !q+p não é o mesmo que !(q+p), então você tem que verificar se faz sentido remover os parênteses.

Uma opção seria fazer if (! eq.startsWith("!")) { faz o replace } para só remover os parênteses caso a expressão não comece com !, por exemplo. Não ficou claro como você quer tratar cada caso, mas tendo a expressão isolada, você pode trabalhá-la da maneira que precisar.


Como eu disse, a regex acima é bem ingênua e propensa a erros. Ela só pega tudo que está entre parênteses, sem validar se de fato é uma expressão válida. Então se tiver coisas como ( ) ou (.$@#%), a regex também vai pegar. Ela só funciona se a expressão estiver bem formada. Se quiser uma regex que verifique qualquer expressão válida, aí já começa a não valer a pena, pois são possibilidades demais.

Até daria para assumir algumas premissas mais simples, como "as proposições sempre tem uma letra", "não há espaços nem quebras de linha", "não haverá caracteres 'estranhos', como @#%", etc, mas ainda sim há outros problemas.

Por exemplo, se tiver parênteses aninhados (como (q*(s+r))), ela também não serve, pois assumimos que dentro dos parênteses não há outros parênteses. Para estes casos, até seria possível usar regex recursiva, mas o Java não suporta este recurso, e de qualquer forma não é a melhor maneira.

A regex ficaria muito complicada, e além disso ela só verificaria se a expressão está certa, mas não avaliaria o resultado - para este caso você precisaria de um parser específico, então por que não usá-lo desde o começo? Regex é legal, mas nem sempre é a melhor solução.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .