Infija a postifija
Estructura de datos
El siguiente algoritmo en pseudocódigo traduce una expresión en notación infija a notación postfija,como paso previo a la obtención del árbol binario correspondiente a la expresión: Entrada: Una lista que contiene los términos de la ecuación en notación infija (la notación habitual). Salida: Una listaque contiene los términos de la ecuación en notación postfija. Datos locales: Una pila, que va a contener operadores y paréntesis izquierdos. INICIO Crear pila y la lista de salida, inicialmentevacías. MIENTRAS lista de entrada no este vacía y no se ha encontrado ningún error HACER Extraer el primer termino de la lista (lo llamaremos E) SEGUN-SEA E CASO E es número: Insertar E al final de lalista de salida CASO E es la variable x: Insertar E al final de la lista de salida CASO E es un paréntesis izquierdo: Insertar E en la pila CASO E es un paréntesis derecho: MIENTRAS La pila no esté vacíay su cima no sea un paréntesis izquierdo HACER Extraer elemento de la pila Insertarlo al final de la lista de salida FIN-MIENTRAS SI Encontramos el paréntesis izquierdo ENTONCES Extraerlo de la pila ydestruirlo SINO Se ha detectado un ERROR 2 FIN-SI Destruir E CASO E es un operador: MIENTRAS La pila no esté vacía y su cima sea un operador de precedencia mayor o igual que la de E HACER Extraerelemento de la pila Insertarlo al final de la lista de salida FIN-MIENTRAS Insertar E en la pila FIN-SEGUN-SEA FIN-MIENTRAS MIENTRAS Pila no esté vacía HACER Extraer elemento de la pila Insertarlo alfinal de la lista de salida FIN-MIENTRAS Destruir pila FIN
Traducción de notación postfija a árbol binario Entrada: La lista obtenida en el algoritmo anterior, que contiene los términos de laecuación en notación postfija. Salida: Un árbol binario que representa la ecuación. Datos locales: Una pila, que va a contener operandos (números, la variable x y expresiones (subárbols). INICIO Crear...
Regístrate para leer el documento completo.