C: Um exemplo de simplificação de expressão lógica

No outro dia vi uma expressão assim:

        if(((situacao == situacao_a) ||
            ((situacao == situacao_b) && (strcmp(string,UMA_MACRO) == 0))) ||
            ((situacao == situacao_c) ||
            ((situacao == situacao_d) && (strcmp(string,UMA_MACRO) == 0))))
        {
                        /* ... */
        }

Este código acima está abaixo do ótimo, tanto em geração de código quanto em desempenho. Mas como otimizar?

Antes de continuar lendo, que tal você mesmo tentar fazer uma versão melhor dele? O artigo sobre avaliação incompleta pode ajudar.

Só o fato de chamar duas vezes a strcmp com os mesmos parâmetros já pode chamar a atenção que pode ter algo errado. Se puder ser simplificada, a expressão pode vir a ter uma só chamada a ela o que diminui o código gerado. A não ser que fique esperando que o compilador melhore a expressão, o que pode acontecer ou não, dependendo do caso.

Vamos aumentar a legibilidade do código acima:

        if(
                (
                        (situacao == situacao_a) ||
                        (
                                (situacao == situacao_b) &&
                                (strcmp(string,UMA_MACRO) == 0)
                        )
                ) ||
                (
                        (situacao == situacao_c) ||
                        (
                                (situacao == situacao_d) &&
                                (strcmp(string,UMA_MACRO) == 0)
                        )
                )
        )
        {
                /* ... */
        }

Aqui fica bem claro que o programador pensou que a expressão or só pode ser executada aos pares, o que não é bem verdade. A primeira simplificação pode ser a abaixo:

        if(
                (situacao == situacao_a) ||
                (
                        (situacao == situacao_b) &&
                        (strcmp(string,UMA_MACRO) == 0)
                ) ||
                (situacao == situacao_c) ||
                (
                        (situacao == situacao_d) &&
                        (strcmp(string,UMA_MACRO) == 0)
                )
        )
        {
                /* ... */
        }

Assim temos um or seguido do outro, mais ainda temos duas chamadas à strcmp. Reduzindo de novo:

        if(
                (situacao == situacao_a) ||
                (situacao == situacao_c) ||
                (
                        (
                                (situacao == situacao_b) ||
                                (situacao == situacao_d)  
                        ) &&
                        ( strcmp(string,UMA_MACRO) == 0 )
                )
        )
        {
                /* ... */
        }

Aqui a chamada da strcmp só existirá uma vez no código.

Uma característica interessante deste caso é que a strcmp só seria chamada uma só vez, se a variável situacao for situacao_b ou situacao_d, mesmo no código original. Mas se o código fosse bem diferente?

        if(
                (
                        (a == x) ||
                        (
                                (b == x) &&
                                (strcmp(string,UMA_MACRO) == 0)
                        )
                ) ||
                (
                        (c == y) ||
                        (
                                (d == y) &&
                                (strcmp(string,UMA_MACRO) == 0)
                        )
                )
        )
        {
                /* ... */
        }

Se a for diferente de x, c for diferente de y, b for igual a x e d for igual a y, a strcmp pode ser chamada duas vezes, bastando que a string seja diferente de UMA_MACRO. Fez sentido? Neste caso todas as avaliações seriam feitas, inclusive duas chamadas à strcmp. Isto pode ser melhorado? Obviamente sim:

        if(
                (a == x) ||
                (c == y) ||
                (
                        (
                                (b == x) ||
                                (d == y)   
                        ) &&
                        (strcmp(string,UMA_MACRO) == 0)
                )
        )
        {
                /* ... */
        }

Na nova forma, se as condições citadas anteriormente acontecerem, não só a strcmp só será chamada uma só vez, como a comparação entre d e y não será feita, pois a comparação entre b e x já dará verdadeiro.

Ainda cabe melhorias no código acima? Talvez sim. Se c tem mais chance de ser igual a y do que a igual a x, então vale a pena trocar a ordem entre estas comparações. O mesmo pode ser feito com as comparações envolvendo b e d. O grande problema é saber quais são as possibilidades destas coisas acontecerem para tirar proveito delas.

Nota final: Se conseguiu um código melhor que o meu, coloque nos comentários, e explique a sua resposta.