Expressao regular recursiva

Nunca vi recursividade em regex, no máximo backreference ou aqueles asserts loucos q não tem implementação em todo o lugar.

Mas diz ai qual é o objetivo q a gente pode pensar em uma estratégia alternativa

Não entendi o que você quer fazer, mas de antemão saiba que “expressões regulares não sabem contar parênteses”. Ou seja, elas são insuficientes para verificar se uma expressão aritmética está bem-formada.

Bom estou fazendo um trabalho da faculdade que converte uma expressao digitada em arvore…

ex:
expressao: a[b+c]

arvore: a
/
b c

quando tenho um expressao simples é facil… e quando coloca mais niveis… por exemplo a[b[d+e]+c[f+g]] ou a[b[d[h+i]+e[j+m]]+c[f[n+o]+g[p+q]]], e assim por diante…
precisava validar isso, para ver se a expressao não é invalida, e o professor disse q tem q ser com expressao regular…

Estou usando o Patter e Macther e estava tentando encontrar um expressao que validade isso…
pois é essa a ideia do trabalho…

pesquisando na net encontrei q o PHP faz essas expressao regulares recusivas, basta colocar (expresao)R e pronto…

como será q posso contornar esse problema… na ideia a funcao deveria suportar quantos niveis quizer

Em Java não é possível escrever uma expressão regular recursiva, e ponto. O que você pode fazer é o seguinte: escrever uma rotina recursiva que capta o “[” e o “]” mais externo (isso é possível fazer via expressões regulares sem problemas ) e joga o que está dentro desse grupo de colchetes.

Vou dar um exemplo com sua entrada, daqui a pouco.

Hum… é mais difícil que imaginava. O programa abaixo não está correto, mas você pode tentar entender a minha ideia.

import java.util.regex.*;

class ExpressaoRegular {

    // <letter>? "[" <expr> "]"
    // <letter>
    // <letter>+<letter>
    // <expr> ( + <expr> )*

    // Expressão válida: <letter> [ <expr> ]
    private Pattern pat0 = Pattern.compile ("[a-z]?\\[(.*)\\]");
    // Expressão válida: <letter>
    private Pattern pat1 = Pattern.compile ("[a-z]");
    // Expressão válida: <letter>
    private Pattern pat2 = Pattern.compile ("[a-z]\\+[a-z]");
    // Expressão válida: <expr> + <expr>
    private Pattern pat3 = Pattern.compile ("(.*)(\\+(.*))+");


    public boolean expressaoValida (String expressao) {
        Matcher mat;
        if ((mat = pat0.matcher (expressao)).matches()) {
            System.out.println ("0)" + mat.group (1));
            return expressaoValida (mat.group(1));
        } else if ((mat = pat1.matcher (expressao)).matches()) {
            System.out.println ("1) " + expressao);
            return true;
        } else if ((mat = pat2.matcher (expressao)).matches()) {
            System.out.println ("2) " + expressao);
            return true;
        } else if ((mat = pat3.matcher (expressao)).matches()) {
            System.out.println ("3)" + mat.group (1) + " <==> " + mat.group (3));
            return expressaoValida (mat.group (1)) && expressaoValida (mat.group (3));
        } else {
            return false;
        }
    }

    public static void main(String[] args) {
        String expressaoCorreta = "a[b[d[h+i]+e[j+m]]+c[f[n+o]+g[p+q]]]"; 
        String expressaoIncorreta = "a[b[d[h+i]+e[j+m]]+c[f[n+o+g[p+q]]]"; 
        ExpressaoRegular er = new ExpressaoRegular ();
	System.out.println (er.expressaoValida (expressaoCorreta));
	System.out.println (er.expressaoValida (expressaoIncorreta));
    }
}

A saída é:

0)b[d[h+i]+e[j+m]]+c[f[n+o]+g[p+q]]
0)d[h+i]+e[j+m]]+c[f[n+o]+g[p+q]
0)h+i]+e[j+m]]+c[f[n+o]+g[p+q
3)h+i]+e[j+m]]+c[f[n+o]+g[p <==> q
3)h+i]+e[j+m]]+c[f[n+o] <==> g[p
3)h+i]+e[j+m]]+c[f[n <==> o]
3)h+i]+e[j+m]] <==> c[f[n
3)h+i]+e[j <==> m]]
3)h+i] <==> e[j
3)h <==> i]
1) h
false
0)b[d[h+i]+e[j+m]]+c[f[n+o+g[p+q]]
0)d[h+i]+e[j+m]]+c[f[n+o+g[p+q]
0)h+i]+e[j+m]]+c[f[n+o+g[p+q
3)h+i]+e[j+m]]+c[f[n+o+g[p <==> q
3)h+i]+e[j+m]]+c[f[n+o <==> g[p
3)h+i]+e[j+m]]+c[f[n <==> o
3)h+i]+e[j+m]] <==> c[f[n
3)h+i]+e[j <==> m]]
3)h+i] <==> e[j
3)h <==> i]
1) h
false

Obviamente as expressões regulares não foram escolhidas corretamente.

Não só em java, como em lugar algum…

ricardoguth:

Acho q o q seu professor quis é q vc identificasse e separasse o padrão e usasse função recursiva com cada padrão encontrado com regex…

Fiz uma implementação disso ai agora usando recursividade e alguns macetes…

As dicas que eu te dou são:

[list]Pense simples, se complicar, jogue fora e comece d novo. Habilidade com programação ou linguagem não importam, matemática e bom senso são tudo nessa hora.[/list]
[list]Vc precisa validar e não calcular… então, vc pode substituir um conjunto de padrão por uma representação e ir simplificando a cada iteração.
Por ex: a[b+c[d+e]] ===> a[b+x] ===> x[/list]
[list]Use apenas um padrão generalizado e não vários para cada “situação”[/list]
[list]Uma característica importante tanto do padrão de substituição do item 1 quanto do exemplo do entanglement é que a expressão obrigatoriamente diminui a cada iteração. Isso pode ser utilizado como critério de parada para a recursividade.[/list]

Bom desenvolvimento

PS: posso postar o código q eu fiz, mas acho importante vc tentar ao máximo antes e claro, postar sua solução

e voce pode fazer um WHILE, e so sair do WHILE quando o novo Matcher parar de retornar true no matches()