Paréntesis emparejados

m0rG #1 Abr '06

Estoy estudiando para un examen de estructura de datos que está al caer y me ha surgido un problema que no soy capaz de resolver y que espero que alguien tenga alguna idea sobre cómo atacarlo.Pues bien el problema en cuestión es que tengo que diseñar un algoritmo que,dada una secuencia de caracteres en la que aparecen los delimitadores ( ) ,[ ],{ },< > ,decida si dichos delimitadores están bien emparejados.Es decir:
abc( ) (aba) [{bv} ( ) asd] ejemplo de secuencia bien parentizada;
((asd( ) }
[( ] ) secuencias mal parentizadas (los caracteres distintos de los delimitadores no importan).

El problema debe ser resuelto usando pilas y es sencillo cuando no hay delimitadores anidados(por ejemplo () { } [asas] ).¿A alguien se le ocurre cómo podría ser?

PD-No pido que me hagáis un programa en X lenguaje que lo haga,sólo ideas de qué hay que hacer en general.
PD2-Sí,he preguntado a mis compañeros pero digamos que esta asignatura no es muy popular por tener fama de difícil (merecida) y se suda bastante de estudiarla...

LOc0 #2 Abr '06

Puff, así de primeras lo que se me ocurre es definir una estructura llamada DELIMITADOR, que contenga 2 campos. Tipo (apertura, cierre) y Clase (<, (, [, {)

Después contaría todos los caracteres del texto a parsear y declararía un array de tipo DELIMITADOR con n elementos. (En vez del array puedes usar una lista enlazada).

Luego con un bucle iría analizando cada carácter y si encontrara <, (, [, {, lo metería en:

delimitador indicando su tipo y clase. Ejemplo:

delimitador.tipo=a
delimitador.clase=<

Incrementaría el contador i y seguiría analizando caracteres. Si te encuentras otro, lo comparas con delimitador[i-1] y "echas cuentas":

a) Que el tipo coincide, pues lo almacenas en delimitador, incrementas i y sigues leyendo caracteres.

b) Que el tipo no coincide, pues miras la clase y si es de la misma es que se ha cerrado ese "nivel", así que "borras" delimitador[i-1] y decrementas i.

c) Que el tipo no coincide y la clase tampoco, pues hay un error.

d) Al terminar de analizar todos los caracteres si i>0 (si queda algún delimitador abierto) entonces hay error.

Esto así grosso modo y sin pensarlo demasiado. Imagino que tendrá fallos, pero algo es algo xD.

Salu2

EDITADO -> http://pastebin.com/674044 (Más sencillo incluso)

m0rG #3 Abr '06

Gracias #2 te lo has currado muchísimo,lo miraré a ver si consigo hacerlo.He intentado hacerlo de la siguiente forma:

He hecho una función que analiza la cadena de caracteres y se queda sólo con aquellos que son delimitadores indicando en cada caso tipo y clase (tal como habías indicado) que son guardados en una variable(tupla) que se va almacenando en una tabla (de forma que en cada posición del array hay un delimitador).Ahora lo que había pensado era leer las posiciones de la tabla de 2 en 2 de forma que si hay dos delimitadores iguales seguidos(misma clase y tipo) el primero de ellos se apila para recuperarlo posteriormente en orden inverso cuando aparezca su clausura (si es que aparece).Aquí es donde entra en juego el uso de pilas.

El problema es que las comparaciones son un poco liosas y el algoritmo queda bastante complicado(aun no lo he terminado).Sin mencionar el detalle de que la secuencia se trata dos veces lo cual no es muy elegante xD.Sin embargo gracias por el post,ha sido de gran ayuda .

T

t4m4g0tch1 #4 Abr '06

aqui tienes la funcioncita en C, que e presentado... espero que la disfrutes... juega con las restas delos caracteres y si la resta es 2 o 1... 2 pops de la pila y magia...

int evaluar(pila *p,char *c){
int i=0;
char x;
while (c!='\0'){
if ((c=='{') || (c=='(') || (c=='[') || (c=='}') || (c==')') || (c==']'))
{
push(p,c);
i++;
}
else i++;
if (p->datos[p->tope]-p->datos[p->tope-1]==1 || p->datos[p->tope]-p->datos[p->tope-1]==2){
pop(p,&x);
pop(p,&x);
}
}

if (pilaVacia(p)==0)
{
	printf("La expresion ta bien");
	return 0;
}
else
	printf("La as cagado");
return 1;

}

PD: Está echo en C... faltan la parte de <>... pero vueno es easy, mira los caracteres ascii y listo.
Disfrutalo

maRc #5 Abr '06

Vas analizando cada caracter de la cadena:

Si es un paréntesis de apertura, lo metes es una pila.

Si es un paréntesis de clausura, extraes un elemento de la pila (como es una pila, el último que has metido), si no es que el se corresponde (si has leido un '(' y es un ']', por ejemplo, cuando lo correcto sería encontrar un ')'), o la pila está vacía, están mal emparejados.

Si una vez has leído toda la linea, te quedan elementos en la pila, están mal emparejados.

Si lo lees todo, no falla a mitad del bucle ni al salir del bucle te quedan elementos en la pila, están bien emparejados.

BlisZ #6 Abr '06

una pila es un array?

maRc #7 Abr '06

Una pila es una estructura de datos de tipo LIFO (Last In First Out) que tiene dos operaciones básica: "push" y "pop".

Con "push", lo que haces es insertar un elemento.
Con "pop", extraes un elemento. Al ser de tipo LIFO, el elemento que extraes es el último que has metido.

Se implementa muy fácilmente con un vector, añadiendo los elementos al final y extrayendo el último.

Una cola es como una pila, pero en lugar de ser LIFO, es FIFO, es decir, extraes el primero que metes.

m0rG #8 Abr '06

Gracias por las respuestas ahora ya lo he entendido,así da gusto .

Usuarios habituales