Ejercicio de clase: Conversión de infijo a posfijo
Esta actividad es para ser resuelta en clase. No se debe entregar nada.
En un mismo archivo fuente llamado infijo_a_posfijo.cpp, escribe el código de C++ que resuelva el siguiente problema. Debes usar la implementación de la clase Stack<T> contenida en el archivo stack.h que se escribió en clase.
string infix_to_postfix(const string& expr)
Esta función recibe como entrada la cadena expr que contiene una expresión aritmética en notación infija. Devuelve una cadena con la expresión equivalente en notación posfija. No realiza ningún tipo de validación respecto a la expresión de entrada.
Descripción del algoritmo
NOTA: El algoritmo que se presenta a continuación es una variación del algoritmo shunting yard inventado por Edsger Dijkstra y publicado por vez primera en 1961.
Empieza con una pila vacía y un vector resultante vacío. Para extraer los números y operadores de la cadena expr usa otro vector y la función split definida en la práctica #5.
-
Procesa en orden cada uno de los elementos ya extraídos de
expr:- Si encuentras un número, insértalo en el vector resultante.
-
Si encuentras un paréntesis izquierdo
(, insértalo en la pila. -
Si encuentras un operador ⊗ (donde ⊗ puede ser
+,-,*o/), realiza lo siguiente:-
Mientras que la pila no esté vacía y además el tope de la pila sea diferente al paréntesis izquierdo
(, realiza lo siguiente:- Si el elemento del tope de la pila tiene mayor o igual precedencia que ⊗, entonces hay que sacar dicho elemento de la pila e insertarlo en el vector resultante. De lo contrario se debe terminar este ciclo anidado.
- Inserta ⊗ en la pila.
-
Mientras que la pila no esté vacía y además el tope de la pila sea diferente al paréntesis izquierdo
-
Si encuentras un paréntesis derecho
), realiza lo siguiente:-
Mientras que la pila no esté vacía y además el tope de la pila sea diferente al paréntesis izquierdo
(, realiza lo siguiente:- Saca el elemento del tope de la pila e insértalo en el vector resultante.
-
Si la pila no está vacía, remueve el paréntesis izquierdo
(del tope de la pila.
-
Mientras que la pila no esté vacía y además el tope de la pila sea diferente al paréntesis izquierdo
-
Si al llegar a este punto la pila no está vacía, remueve uno por uno todos elementos de la pila e insértalos en el vector resultante.
-
Finalmente, devuelve una cadena conformada por la concatenación de todos los elementos del vector resultante, usando un espacio en blanco como separador entre elementos.
TIP: Puedes usar la siguiente función para determinar si el elemento del tope de la pila tiene mayor precedencia que el operador ⊗:
bool has_higher_or_equal_precedence( const string& stack_top, const string& other) { return !((stack_top == "+" || stack_top == "-") && (other == "*" || other == "/")); }
Prueba la función infix_to_postfix con el siguiente código. En la salida se deben imprimir puros unos.
cout << ("42" == infix_to_postfix("42")) << endl; cout << ("1 2 +" == infix_to_postfix("1 + 2")) << endl; cout << ("1 2 * 3 +" == infix_to_postfix("1 * 2 + 3")) << endl; cout << ("1 2 + 3 + 4 +" == infix_to_postfix("1 + 2 + 3 + 4")) << endl; cout << ("1 2 +" == infix_to_postfix("(1 + 2)")) << endl; cout << ("1 2 3 4 + + +" == infix_to_postfix("(1 + (2 + (3 + 4)))")) << endl; cout << ("1 2 3 * +" == infix_to_postfix("1 + 2 * 3")) << endl; cout << ("1 2 + 3 *" == infix_to_postfix("(1 + 2) * 3")) << endl; cout << ("1 2 3 * + 4 +" == infix_to_postfix("1 + 2 * 3 + 4")) << endl; cout << ("1 2 + 3 4 + *" == infix_to_postfix("(1 + 2) * (3 + 4)")) << endl; cout << ("1 2 + 3 4 * 5 / -" == infix_to_postfix("1 + 2 - 3 * 4 / 5")) << endl; cout << ("1 2 / 3 * 4 - 5 +" == infix_to_postfix("1 / 2 * 3 - 4 + 5")) << endl; cout << ("1 2 / 3 4 * - 5 +" == infix_to_postfix("1 / 2 - 3 * 4 + 5")) << endl; cout << ("1 2 3 - + 4 5 / *" == infix_to_postfix("(1 + (2 - 3)) * (4 / 5)")) << endl; cout << ("1 2 3 - / 4 5 + *" == infix_to_postfix("1 / (2 - 3) * (4 + 5)")) << endl; cout << ("1 2 3 - 4 5 + * /" == infix_to_postfix("1 / ((2 - 3) * (4 + 5))")) << endl; cout << ("1 2 3 4 * - 5 + /" == infix_to_postfix("1 / (2 - 3 * 4 + 5)")) << endl; cout << ("42" == infix_to_postfix("(42)")) << endl; cout << ("42" == infix_to_postfix("(((42)))")) << endl; cout << ("1 2 +" == infix_to_postfix("(1 + 2)")) << endl; cout << ("1 2 *" == infix_to_postfix("(((1) * (2)))")) << endl;