Parseo de expresiones

Se da un string que contiene una expresión matemática con números y varios operadores. Tenemos que computar su valor en $O(n)$, donde $n$ es la longitud del string.

El algoritmo que se discute aquí traduce una expresión a la llamada notación polaca inversa (explícita o implícitamente), y evalúa esta expresión.

Notación polaca inversa

La notación polaca inversa es una forma de escribir expresiones matemáticas en la que los operadores se ubican después de sus operandos. Por ejemplo la siguiente expresión

$$a + b * c * d + (e - f) * (g * h + i)$$

se puede escribir en notación polaca inversa de la siguiente manera:

$$a b c * d * + e f - g h * i + * +$$

La notación polaca inversa fue desarrollada por el filósofo y especialista en ciencias de la computación australiano Charles Hamblin a mediados de la década de 1950, sobre la base de la notación polaca, que fue propuesta en 1920 por el matemático polaco Jan Łukasiewicz.

La conveniencia de la notación polaca inversa es que las expresiones en esta forma son muy fáciles de evaluar en tiempo lineal. Usamos una pila, que inicialmente está vacía. Iteraremos sobre los operandos y operadores de la expresión en notación polaca inversa. Si el elemento actual es un número, entonces ponemos el valor en la cima de la pila; si el elemento actual es un operador, entonces tomamos los dos elementos de la cima de la pila, realizamos la operación y ponemos el resultado de nuevo en la cima de la pila. Al final quedará exactamente un elemento en la pila, que será el valor de la expresión.

Obviamente esta evaluación simple corre en tiempo $O(n)$.

Parseo de expresiones simples

Por el momento solo consideramos un problema simplificado: asumimos que todos los operadores son binarios (es decir, toman dos argumentos), y todos son asociativos por la izquierda (si las prioridades son iguales, se ejecutan de izquierda a derecha). Se permiten paréntesis.

Prepararemos dos pilas: una para números, y otra para operadores y paréntesis. Inicialmente ambas pilas están vacías. Para la segunda pila mantendremos la condición de que todas las operaciones están ordenadas por prioridad estrictamente decreciente. Si hay paréntesis en la pila, entonces cada bloque de operadores (correspondiente a un par de paréntesis) está ordenado, y la pila entera no está necesariamente ordenada.

Iteraremos sobre los caracteres de la expresión de izquierda a derecha. Si el carácter actual es un dígito, entonces ponemos el valor de este número en la pila. Si el carácter actual es un paréntesis de apertura, entonces lo ponemos en la pila. Si el carácter actual es un paréntesis de cierre, entonces ejecutamos todos los operadores de la pila hasta llegar al paréntesis de apertura (en otras palabras, realizamos todas las operaciones dentro del paréntesis). Finalmente, si el carácter actual es un operador, entonces mientras la cima de la pila tenga un operador con la misma prioridad o una mayor, ejecutaremos esta operación, y pondremos la nueva operación en la pila.

Después de procesar el string entero, algunos operadores podrían seguir en la pila, así que los ejecutamos.

Aquí está la implementación de este método para los cuatro operadores $+$ $-$ $*$ $/$:

bool delim(char c) {
    return c == ' ';
}

bool is_op(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

int priority (char op) {
    if (op == '+' || op == '-')
        return 1;
    if (op == '*' || op == '/')
        return 2;
    return -1;
}

void process_op(stack<int>& st, char op) {
    int r = st.top(); st.pop();
    int l = st.top(); st.pop();
    switch (op) {
        case '+': st.push(l + r); break;
        case '-': st.push(l - r); break;
        case '*': st.push(l * r); break;
        case '/': st.push(l / r); break;
    }
}

int evaluate(string& s) {
    stack<int> st;
    stack<char> op;
    for (int i = 0; i < (int)s.size(); i++) {
        if (delim(s[i]))
            continue;
        
        if (s[i] == '(') {
            op.push('(');
        } else if (s[i] == ')') {
            while (op.top() != '(') {
                process_op(st, op.top());
                op.pop();
            }
            op.pop();
        } else if (is_op(s[i])) {
            char cur_op = s[i];
            while (!op.empty() && priority(op.top()) >= priority(cur_op)) {
                process_op(st, op.top());
                op.pop();
            }
            op.push(cur_op);
        } else {
            int number = 0;
            while (i < (int)s.size() && isalnum(s[i]))
                number = number * 10 + s[i++] - '0';
            --i;
            st.push(number);
        }
    }

    while (!op.empty()) {
        process_op(st, op.top());
        op.pop();
    }
    return st.top();
}

Así aprendimos a calcular el valor de una expresión en $O(n)$; al mismo tiempo usamos implícitamente la notación polaca inversa. Modificando ligeramente la implementación de arriba también es posible obtener la expresión en notación polaca inversa de forma explícita.

Operadores unarios

Ahora supongamos que la expresión también contiene operadores unarios (operadores que toman un argumento). El más unario y el menos unario son ejemplos comunes de tales operadores.

Una de las diferencias en este caso es que necesitamos determinar si el operador actual es unario o binario.

Se puede notar que antes de un operador unario siempre hay otro operador o un paréntesis de apertura, o nada en absoluto (si está al comienzo mismo de la expresión). Por el contrario, antes de un operador binario siempre habrá un operando (número) o un paréntesis de cierre. Así es fácil marcar si el siguiente operador puede ser unario o no.

Además necesitamos ejecutar un operador unario y uno binario de forma distinta. Y necesitamos elegir la prioridad de un operador unario más alta que la de todos los operadores binarios.

Además cabe notar que algunos operadores unarios (p. ej. el más unario y el menos unario) son de hecho asociativos por la derecha.

Asociatividad por la derecha

Asociativo por la derecha significa que, cuando las prioridades son iguales, los operadores deben evaluarse de derecha a izquierda.

Como se notó arriba, los operadores unarios suelen ser asociativos por la derecha. Otro ejemplo de un operador asociativo por la derecha es el operador de exponenciación ($a \wedge b \wedge c$ suele percibirse como $a^{b^c}$ y no como $(a^b)^c$).

¿Qué cambio necesitamos hacer para manejar correctamente los operadores asociativos por la derecha? Resulta que los cambios son mínimos. La única diferencia será que, si las prioridades son iguales, pospondremos la ejecución de la operación asociativa por la derecha.

La única línea que hay que reemplazar es

while (!op.empty() && priority(op.top()) >= priority(cur_op))

por

while (!op.empty() && (
        (left_assoc(cur_op) && priority(op.top()) >= priority(cur_op)) ||
        (!left_assoc(cur_op) && priority(op.top()) > priority(cur_op))
    ))

donde left_assoc es una función que decide si un operador es asociativo por la izquierda o no.

Aquí está una implementación para los operadores binarios $+$ $-$ $*$ $/$ y los operadores unarios $+$ y $-$.

bool delim(char c) {
    return c == ' ';
}

bool is_op(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

bool is_unary(char c) {
    return c == '+' || c=='-';
}

int priority (char op) {
    if (op < 0) // operador unario
        return 3;
    if (op == '+' || op == '-')
        return 1;
    if (op == '*' || op == '/')
        return 2;
    return -1;
}

void process_op(stack<int>& st, char op) {
    if (op < 0) {
        int l = st.top(); st.pop();
        switch (-op) {
            case '+': st.push(l); break;
            case '-': st.push(-l); break;
        }
    } else {
        int r = st.top(); st.pop();
        int l = st.top(); st.pop();
        switch (op) {
            case '+': st.push(l + r); break;
            case '-': st.push(l - r); break;
            case '*': st.push(l * r); break;
            case '/': st.push(l / r); break;
        }
    }
}

int evaluate(string& s) {
    stack<int> st;
    stack<char> op;
    bool may_be_unary = true;
    for (int i = 0; i < (int)s.size(); i++) {
        if (delim(s[i]))
            continue;
        
        if (s[i] == '(') {
            op.push('(');
            may_be_unary = true;
        } else if (s[i] == ')') {
            while (op.top() != '(') {
                process_op(st, op.top());
                op.pop();
            }
            op.pop();
            may_be_unary = false;
        } else if (is_op(s[i])) {
            char cur_op = s[i];
            if (may_be_unary && is_unary(cur_op))
                cur_op = -cur_op;
            while (!op.empty() && (
                    (cur_op >= 0 && priority(op.top()) >= priority(cur_op)) ||
                    (cur_op < 0 && priority(op.top()) > priority(cur_op))
                )) {
                process_op(st, op.top());
                op.pop();
            }
            op.push(cur_op);
            may_be_unary = true;
        } else {
            int number = 0;
            while (i < (int)s.size() && isalnum(s[i]))
                number = number * 10 + s[i++] - '0';
            --i;
            st.push(number);
            may_be_unary = false;
        }
    }

    while (!op.empty()) {
        process_op(st, op.top());
        op.pop();
    }
    return st.top();
}