Boa tarde,
Estou fazendo um trabalho sobre árvores e me enrolei em um dos pontos. Devo receber uma String como entrada e gerar a respectiva árvore descrita por ela.
Considerações:
1. A entrada é uma expressão parentetizada válida.
2. Todas as árvores são balanceadas (todas as folhas em um mesmo nível).
Exemplos: (1(2(3))) e (1(2(4)(5))(3(6))).
Inicialmente comecei com árvores binárias e o seguinte algoritmo cumpre o propósito, percorrendo a expressão e utilizando uma pilha para gerar a árvore resultante.
public binaryTree buildTree(String s) {
binaryTree f = new binaryTree();
Pilha p = new Pilha();
String arg = "";
int i = 0;
while (i < s.length()) {
if (s.charAt(i) == '(') {
i++;
arg = "";
while (s.charAt(i) != '(' && s.charAt(i) != ')') {
if (s.charAt(i) != ' ')
arg += s.charAt(i);
i++;
}
binaryTree aux = new binaryTree(arg, null, null);
if (p.tamanho > 0) {
f = (binaryTree) p.pop().info;
f.addEsquerda(aux);
p.push(f);
}
p.push(aux);
}
if (s.charAt(i) == ')') {
if (i < s.length() && s.charAt(i) == ')') {
f = (binaryTree) p.pop().info;
i++;
}
if (i < s.length() && s.charAt(i) == '(') {
i++;
arg = "";
while (s.charAt(i) != '(' && s.charAt(i) != ')') {
if (s.charAt(i) != ' ')
arg += s.charAt(i);
i++;
}
binaryTree aux2 = new binaryTree(arg, null, null);
f = (binaryTree) p.pop().info;
f.addDireita(aux2);
p.push(f);
p.push(aux2);
if (i < s.length() && s.charAt(i) == ')') {
f = (binaryTree) p.pop().info;
i++;
}
}
}
}
return f;
}
Basicamente, o algoritmo consiste em percorrer a String e, ao encontrar um ‘(’, cria um nó que contém a árvore cuja raiz é restante da String. Em seguida, este nó é conectado ao que estava no topo da pilha (desempilhando-o), à esquerda, então o nó desempilhado é reempilhado e o nó criado é empilhado por cima.
Ao encontrar um ‘)’, desempilha-se um nó da pilha, caso o próximo caractere seja um ‘(’, executa-se o passo anterior, desta vez conectando à direita.
Até aqui tudo bem, porém agora eu preciso adaptar tudo para construir árvores n-árias, para as quais utilizo Listas (encadeadas) genéricas. Para os exemplos dados, basicamente, para construir suas árvores:
(1(2(3))): lista1 = new Lista(new Integer(1));
lista2 = new lista(new Integer(2));
lista3 = new lista(new Integer(3));
lista1.add(lista3);
lista1.add(lista2);
(1(2(4)(5))(3(6))): lista1 = new Lista(new Integer(1));
lista2 = new Lista(new Integer(2));
lista3 = new Lista(new Integer(3));
lista4 = new Lista(new Integer(4));
lista5 = new Lista(new Integer(5));
lista6 = new Lista(new Integer(6));
lista3.add(lista6);
lista2.add(lista5);
lista2.add(lista4);
lista1.add(lista3);
lista1.add(lista2);
Para uma árvore que não seja binária:
(1(2)(3)(4)): lista1 = new lista(new Integer(1));
lista2 = new lista(new Integer(2));
lista3 = new lista(new Integer(3));
lista4 = new lista(new Integer(4));
lista1.add(lista4);
lista1.add(lista3);
lista1.add(lista2);
Eu não consigo visualizar uma forma de mecanizar a construção dessas árvores (como “listas de listas”) para uma entrada qualquer, transformar tal lógica em um algoritmo, será que alguém poderia me ajudar?
Desde já grato,
Ricardo Gonçalves.
PS: Acabei de ver que foram criados dois tópicos repetidos, quando fui postar houve um erro, então eu voltei e postei de novo para não perder o que escrevi, não reparei que já tinha sido postado, alguém, por favor, feche ou apague um dos tópicos.