Análise de expressões

Uma string contendo uma expressão matemática contendo números e vários operadores é fornecida. Temos que calcular o valor dela em $O(n)$, onde $n$ é o comprimento da string.

O algoritmo discutido aqui traduz uma expressão na chamada notação polonesa reversa (explícita ou implicitamente) e avalia essa expressão.

Notação polonesa reversa

A notação polonesa reversa é uma forma de escrever expressões matemáticas, na qual os operadores estão localizados após seus operandos. Por exemplo, a seguinte expressão $$a + b * c * d + (e - f) * (g * h + i)$$ pode ser escrita em notação polonesa reversa da seguinte maneira: $$a b c * d * + e f - g h * i + * +$$

A notação polonesa reversa foi desenvolvida pelo filósofo e especialista em ciência da computação australiano Charles Hamblin em meados da década de 1950, com base na notação polonesa, proposta em 1920 pelo matemático polonês Jan Łukasiewicz.

A conveniência da notação polonesa reversa é que as expressões nesta forma são mais fáceis de avaliar em tempo linear. Usamos uma pilha, que está inicialmente vazia. Iremos iterar sobre os operandos e operadores da expressão em notação polonesa reversa. Se o elemento atual é um número, colocamos o valor no topo da pilha, se o elemento atual é um operador, obtemos os dois elementos principais da pilha, executamos a operação e colocamos o resultado novamente no topo da pilha. a pilha. No final, haverá exatamente um elemento restante na pilha, que será o valor da expressão.

Obviamente, essa avaliação simples é executada em $O(n)$.

Parsing de expressões simples

Por enquanto, consideramos apenas um problema simplificado: assumimos que todos os operadores são binários (ou seja, recebem dois argumentos) e todos são associativos à esquerda (se as prioridades são iguais, são executadas da esquerda para a direita). Parênteses são permitidos.

Vamos configurar duas pilhas: uma para números e outra para operadores e parênteses. Inicialmente, ambas as pilhas estão vazias. Para a segunda pilha, manteremos a condição de que todas as operações sejam ordenadas estritamente por ordem descendente. Se houver parênteses na pilha, cada bloco de operadores (correspondente a um par de parênteses) será ordenado e a pilha inteira não será necessariamente ordenada.

Iremos iterar os caracteres da expressão da esquerda para a direita. Se o caractere atual for um dígito, colocaremos o valor desse número na pilha. Se o caractere atual é um parêntese de abertura, colocamos na pilha. Se o caractere atual é um parêntese de fechamento, executamos todos os operadores na pilha até atingirmos o colchete de abertura (em outras palavras, executamos todas as operações dentro do parêntese). Finalmente, se o caractere atual for um operador, enquanto o topo da pilha tiver um operador com a mesma ou maior prioridade, executaremos esta operação e colocaremos a nova operação na pilha.

Depois que processamos a string inteira, alguns operadores ainda podem estar na pilha, então nós os executamos.

Aqui está a implementação deste método para os quatro 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();
}

Assim, aprendemos como calcular o valor de uma expressão em $O(n)$, ao mesmo tempo em que usamos implicitamente a notação polonesa reversa. Modificando ligeiramente a implementação acima, também é possível obter a expressão na notação polonesa reversa de forma explícita.

Operadores unários

Agora, suponha que a expressão também contenha operadores unários (operadores que usam um argumento). O mais unário e o menos unário são exemplos comuns de tais operadores.

Uma das diferenças nesse caso é que precisamos determinar se o operador atual é unário ou binário.

Você pode notar que, antes de um operador unário, sempre existe outro operador ou um parêntese de abertura, ou nada (se estiver no início da expressão). Pelo contrário, antes de um operador binário, sempre haverá um operando (número) ou um parêntese de fechamento. Portanto, é fácil sinalizar se o próximo operador pode ser unário ou não.

Além disso, precisamos executar um operador unário e um binário de maneira diferente. E precisamos escolher a prioridade de um operador binário mais alto que todas as operações binárias.

Além disso, deve-se notar que alguns operadores unários (por exemplo, unário mais e unário menos) são na verdade associativos à direita.

Associativos à direita

Associativo à direita significa que sempre que as prioridades são iguais, os operadores devem ser avaliados da direita para a esquerda.

Como observado acima, operadores unários geralmente são associativos à direita. Outro exemplo para um operador associativo à direita é o operador de exponenciação ($a \wedge b \wedge c$ é geralmente percebido como $a^{b^c}$ e não como $(a^b)^c$).

Que diferença precisamos fazer para lidar corretamente com os operadores associativos à direita? Acontece que as mudanças são muito mínimas. A única diferença será que, se as prioridades forem iguais, adiaremos a execução da operação associativa à direita.

A única linha que precisa ser substituída é

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))
    ))

onde left_assoc é uma função que decide se um operador é associativo_a_esquerda ou não.

Aqui está uma implementação para os operadores binários $+$ $-$ $*$ $/$ e os operadores unários $+$ e $-$.

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 unário
        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();
}