PKU 2792 - Brackets Removal

Autor da análise: gabrielrcpgabrielrcp

Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=2792

Resumo

Dada uma expressão matemática, devemos reescrevê-la removendo parênteses desnecessários. Deve-se deixar apenas os parênteses que servem para fazer a "distribuitiva" entre multiplicação/divisão e adição/subtração, como por exemplo $a*(b+c)$. (não podemos/devemos transformar essa expressão em $a*b+ a*c)$)

No entanto deve-se remover parênteses que "invertem" o sinal da adição/subtração e multiplicação/divisão. Por exemplo:

  • $a-(b+c-d)$ deve virar $a-b-c+d$
  • $a/(b*c/d)$ deve virar $a/b/c*d$

Solução

Eu dei umas "voltas" na minha solução, talvez haja algo mais "direto".

Primeiro fiz o parsing da expressão, armazenando-a na memória como uma árvore. Depois eu a imprimi usando parênteses somente quando necessário.

Representação de expressões através de árvores

Eu acho que essa parte não deve ser novidade para ninguém aqui, mas vou tentar descrever, até para ficar como referência futura. Talvez muitos (como eu) não mexam com isso desde os cursos introdutórios à computação.

Podemos representar qualquer expressão matemática, que use os operadores "normais" como uma árvore binária, onde os vértices internos são os operadores e as folhas são números ou variáveis. *Alguém sabe se ela tem um nome?*

Aí você pode avaliar o valor de uma expressão com o seguinte pseudocódigo: (o problema não pede para avaliar a expressão, só estou deixando isso aqui porque talvez fique mais fácil de entender qual a idéia dessa representação)

avalia (arvore)
    se valor(arvore) é número ou variável
        devolve valor(arvore)
    v1 <- avalia(arvore.filho_esquerda);
    v2 <- avalia(arvore.filho_direita);
    se valor(arvore) == '+'
        devolve v1 + v2
    se valor(arvore) == '-'
        devolve v1 - v2
    se valor(arvore) == '*'
        devolve v1 * v2
    se valor(arvore) == '/'
        devolve v1 / v2

Você pode ainda generalizar essa idéia para contar outros operadores, como exponencial, fatorial e qualquer outro. Essa é uma estura muito eficiente para avaliar expressões (eu não conheço maneira melhor).

Montar a árvore

Voltando para o problema, a primeira coisa que devemos fazer é ler a expressão e montar essa árvore. A idéia para fazer isso é quase a mesma que usamos para transformar uma expressão infixa em posfixa (ou polonesa reversa).

Vamos usar duas pilhas para isso, uma de caracteres, onde vamos armazenar operadores, e outra de ponteiros para structs que armazenam os nós da nossa árvore, que vamos chamar de final. Coloque um '(' no começo da expressão e um ')' no final, para que não precisemos nos preocupar com pilhas vazias ou esvazia-las no final.

Leia a expressão, caractere por caractere, da esquerda para a direita, e faça:

  • Se o caractere for uma variável, crie uma nova folha para ela e a insira na pilha final.
  • Se o caractere for um '(', o insira na pilha dos operadores.
  • Se o caractere for um ')', retire e processe todos os caracteres da pilha dos operadores, até encontrar um ')', retire-o e continue.
  • Se encontrar um operador ('+', '-', '*' ou '/'), retire e processe os caracteres da pilha de operadores até encontrar um de precedência estritamente menor ou um '(', depois insira o caractere atual na pilha de operadores.

A operação de processar um operador consiste em criar um novo nó para ele, retirar dois elementos do topo da pilha final e coloca-los como filhos desse novo nó, depois inserir-lo na pilha final.

Quando você terminar de varrer a expressão, se ela estiver bem formada e você tiver adicionado os parênteses no começo e no fim, a sua pilha de operadores estará vazia e sua pilha final terá apenas um elemento, que é a raiz da sua árvore.

Imprimir a expressão

Como quase sempre quando temos uma árvore, vamos tratar o problema de maneira recursiva (árvores são lindas!).

Vamos primeiro imaginar que houvessem apenas sinais de '+' e '*' nela.

Olhem para o valor da raiz, se for uma variável, então basta imprimi-la. Se for um sinal de '+', então podemos imprimir o filho à esquerda, o sinal de '+' e depois o filho à direita. Note que não precisamos de parênteses porque o '+' já é o operador de menor precedência, então ele sem nenhum parênteses já vai ser avaliado depois de toda à expressão à esquerda. E caso ele seja avaliado antes de alguém da expressão da direita, é porque na direita também tinha outro '+', aí a associatividade da adição nos garante que tanto faz.

Se o valor da expressão for '*', aí podemos ter que colocar alguns parênteses. A idéia básica continua imprima o filho à esquerda, imprima um '*' e depois imprima o filho à direita. Mas agora antes de imprimir cada filho, olhe para eles. Se o último sinal a ser avaliado (o que está na raiz) num filho for '+' ou '-', então você vai precisar colocar esse filho entre parêntesis, caso contrário, não precisa.

Agora o que fazer com os '-' e '/'?

Quanto à parenteses, você os trata de maneira análoga ao '+' e '*'. O problema é tratar expressões do tipo $a-(b+c-d) = a-b-c+d$.

Pode-se resolver isso passando mais dois valores booleanos como parâmetros para a sua função recursiva, um dizendo se temos que "inverter" os '+' e '-' e outro dizendo se temos que inverter os '*' e '/'.
Se encontrarmos um '+', imprimimos um '+' ou um '-' de acordo com o valor do booleano correspondente. Se encontrarmos um '-', também imprimimos um '-' ou '+' de acordo com o booleano e, ao imprimir o filho da direita, passamos a negação desse booleano como parâmetros. Em ambos os casos passamos um false para a inversão do '*' com o '/'.

A mesma coisa quando encontramos um '*' e '/'. Com a restrição adicional de que se você colocar algum parênteses, então "zere" os booleanos ao imprimir aquele filho.

Testes

Entrada

O programa deve ler só uma expressão. Mas coloquei várias em seguida, com as respostas na mesma ordem.

((a-b)-(c-d)-(z*z*g/f)/(p*(t))*((y-u)))
a-(b+c-d)
a/(b*c/d)
a*b-(c+d-e*(f-g/h))

Saída

a-b-c+d-z*z*g/f/p/t*(y-u)
a-b-c+d
a/b/c*d
a*b-c-d+e*(f-g/h)

Enquete

Qualidade do enunciado

Dificuldade do problema

Problema interessante

Discuta o problema

Add a New Comment
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License