Data Structures

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.

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;