3.9. Expressões Infixas, Prefixas and Posfixas¶

3.9.1. Conversão de Expressões Infixas para Prefixas e Posfixas¶

Até agora, usamos métodos ad hoc para converter expressões infixas para expressões prefixas e posfixas equivalentes. Como você pode imaginar, existem maneiras algorítmicas que permitem convertermos qualquer expressão de qualquer complexidade para uma expressão equivalente.

A primeira técnica que vamos considerar usa a noção de um expressão entre parênteses que foi discutida anteriormente. Lembre-se que A + B * C pode ser escrita como (A + (B * C)) para mostrar explicitamente que a multiplicação tem precedência sobre a adição. Em uma observação mais cuidadosa, no entanto, você pode ver que cada par de parênteses também determina o início e o fim de um par de operandos com o operador correspondente no meio.

Observe o parêntese direito na subexpressão (B * C) acima. Se movermos o símbolo de multiplicação para a posição do parêntese a direita e removermos o parêntese da esquerda, obtendo B C *, teremos, de fato, convertido a subexpressão para a notação posfixa. Se o operador adição também for movido para a posição correspondente ao parêntese à direita e o parêntese esquerdo correspondente foi removido, teremos a expressão posfixa completa (veja Figura 6).

Figure 6: Movendo Operadores para a Direita para a Expressão Posfixa¶

Se fizermos a mesma coisa, mas em vez de mover o símbolo para a posição do parêntese direito, nós o movemos para a esquerda, obtemos a notação prefixa (veja Figura 7). A posição do par parênteses é na verdade, uma pista para a posição final do operador entre parênteses.

Figure 7: Movendo Operadores para a Esquerda para a Expressão Prefixa¶

Então, para converter uma expressão, não importa o quão complexa, para a notação de prefixa ou posfixa, considere a expressão totalmente parentizada equivalente. Em seguida, mova o operador envolto pelos parênteses para a posição do parêntese esquerdo ou direito, dependendo se você quer notação de prefixa ou posfixa.

Aqui está uma expressão mais complexa: (A + B) * C - (D - E) * (F + G). Figure 8 mostra a conversão para a notação posfixa e prefixa.

Figure 8: Convertendo uma Expressão Complexa para as Notações Prefixa and Posfixa¶

3.9.2. Conversão Genérica de Infixa para Posfixa¶

Precisamos desenvolver um algoritmo para converter qualquer expressão infixa para uma expressão posfixa equivalente. Para fazer isso, vamos olhar mais de perto o processo de conversão.

Considere mais uma vez a expressão A + B * C. Como mostrado acima, A B C * + é a posfixa equivalente. Já observamos que o os operandos A, B e C permanecem em suas posições relativas. São apenas o operadores que mudam de posição. Vamos olhar novamente para os operadores na expressão infixada. O primeiro operador que aparece da esquerda para a direita é +. No entanto, na expressão posfixa, + está no final ja que o próximo operador, *, tem precedência sobre a adição. A ordem dos operadores na expressão original é invertida na expressão posfixa resultante.

Enquanto processamos a expressão, os operadores precisam ser salvos em algum lugar já que seus operandos correspondentes ainda não foram vistos. Também a ordem desses operadores salvos pode precisar ser revertida devido à precedência. Este é o caso da adição e da multiplicação do exemplo. Como o operador de adição vem antes do operador de multiplicação e tem menor precedência, ele precisa aparecer depois que o operador de multiplicação ser aplicado. Devido a essa reversão de ordem, faz sentido considerar o uso de uma pilha para manter os operadores até que sejam necessários.

E quanto a (A + B) * C? Lembre-se de que A B + C * é a posfixa equivalente. Novamente, examinando essa expressão infixada da esquerda para a direita, nós vemos + primeiro. Neste caso, quando vemos *, + já foi colocado na expressão resultante porque tem precedência sobre * em virtude dos parênteses. Agora podemos começar a ver como o algoritmo de conversão vai funcionar. Quando vemos um parêntese à esquerda, vamos salvá-lo para denotar que outro operador de alta precedência estará chegando. Aquele operador terá que esperar até que o parêntese direito correspondente apareça indicando sua posição (lembre-se da técnica para expressões totalmente parentizadas). Quando o parêntese direito é aparece, o operador pode ser removido da pilha.

Enquanto examinamos a expressão infixa da esquerda para a direita, usaremos uma pilha para manter os operadores. Isso fornecerá a reversão que observamos no primeiro exemplo. O topo da pilha terá sempre o operador mais recentemente salvo. Sempre que vemos um novo operador, precisaremos considerar como a precedência desse operador se compara com a precedência dos operadores na pilha, caso haja algum.

Suponha que a expressão infixa é uma string de itens (tokens) delimitados por espaços. Os itens operadores são *, /, + e -. Temos ainda os itens abre e fecha parênteses, ( e ). Os itens que representam os operandos são os caracteres A, B, C e assim por diante. Os passos seguintes irão produzir um string que representa a expressão posfixa equivalente.

1. Crie uma pilha vazia chamada opstack para manter os operadores. Cria uma lista vazia para a saída.

2. Converta a string infixa input para uma lista usando o método split().

3. Examine os itens da lista da esquerda para a direita.

   • Se o item é um operador, coloque-o no final da lista da saída.

   • Se o item é um abre parêntese, insira-o (push()) na pilha opstack.

   • Se o item é um fecha parênteses, remova ( pop()) os itens de opstack até que o abre parêntese correspondente seja removido. Coloque cada operador removido no final da lista da saída.

   • Se i item é um operador, *, /, +, or -, insira-o na pilha opstack. Entretanto, remova antes os operadores que estão na pilha que têm precedência maior ou igual ao operador encontrado e coloque-os na final da lista da saída.

4. Quando a expressão tiver sido completamente examinada, verifique opstack. Qualquer operador que ainda está na pilha deve ser removido e colocado na lista da saída.

Figure 9 mostra o algoritmo de conversão trabalhando sobre a expressão A * B + C * D. Note que o primeiro * é removido assim que o operador + é encontrado. Também, + permanece na pilha quando o segundo * ocorre, já que multiplicação tem precedência sobre adição. Ao final da expressão infixa removemos da pilha ambos operadores + colocando-os como últimos opredaores da expressão posfixa.

Figure 9: Convertendo A * B + C * D para Notação Postfixa¶

Para implementar o algoritmo em Python, usaremos um dicionário chamado prec para manter os valores de precedência dos operadores. Este dicionário associará a cada operador um número inteiro que pode ser comparado com a precedência de outros operadores (arbitrariamente usamos os inteiros 3, 2 e 1). O parêntese esquerdo receberá o menor valor possível. Desta forma, qualquer operador que é comparado com ele terá maior precedência e será colocado em sobre ele na pilha. A linha 15 define os operandos como qualquer letra maiúsculo ou dígito . A função de conversão completa é mostrado em ActiveCode 1.

Mais alguns exemplos de conversão no Python shell estão logo abaixo.

>>> infixtopostfix("( A + B ) * ( C + D )")
'A B + C D + *'
>>> infixtopostfix("( A + B ) * C")
'A B + C *'
>>> infixtopostfix("A + B * C")
'A B C * +'
>>>

3.9.3. Avaliação Posfixa¶

Como um exemplo de final do uso de pilhas, vamos considerar a avaliação de um expressão que já está em notação posfixa. Neste caso, uma pilha é novamente a estrutura de dados de escolha. No entanto, enquanto você examina a expressão posfixa, são os operandos que devem esperar, não os operadores como no algoritmo de conversão acima. Outra maneira de pensar sobre a solução é que sempre que um operador é visto na entrada, os dois operandos mais recentes serão utilizados na avaliação.

Para ver isso em mais detalhes, considere a expressão postfix 4 5 6 * +. Ao examinar a expressão da esquerda para a direita, você primeiro encontrar os operandos 4 e 5. Neste ponto, você ainda não tem certeza do que fazer com eles até ver o próximo símbolo. Colocando cada em uma pilha garante que eles estejam disponíveis se um operador vier em seguida.

Nesse caso, o próximo símbolo é outro operando. Então, como antes, insira (push()) o operando na pilha e verifique o próximo símbolo. Agora vemos um operador, *. Isso significa que os dois operandos mais recentes precisam ser multiplicados. Removendo (pop()) dois itens da pilha, podemos obter os operandos apropriados e então realizar a multiplicação (nesse caso, obtendo o resultado 30).

Agora podemos lidar com esse resultado colocando-o na pilha para que ele possa ser usado como um operando dos operadores posteriores na expressão. Quando o operador final é processado, haverá apenas um valor restante na pilha. Remova-o e devolva-o como resultado da expressão. Figura 10 mostra o conteúdo da pilha como essa expressão está sendo processada.

Figure 10: Conteúdo da Pilha Durante a Avaliação¶

Figura 11 mostra um exemplo um pouco mais complexo, 7 8 + 3 2 + /. Há duas coisas a serem observadas neste exemplo. Primeiro, o tamanho da pilha cresce, encolhe e cresce novamente à medida que as subexpressões são avaliadas. Em segundo lugar, a operação de divisão precisa ser tratada com cuidado. Lembre-se de que os operandos na expressão posfixa estão em sua ordem original, na expressão posfixa mudamos apenas a colocação de operadores. Quando o operandos para a divisão são retirados da pilha, eles estão invertidos. Como a divisão não é um operador comutativo, em outras palavras \(15/5\) não é o mesmo que \(5/15\), devemos ter certeza que a ordem dos operandos não é alterada.

Figura 11: Um Exemplo Mais Complexo de Avaliação¶

Suponha que a expressão posfixa seja uma string de itens (tokens) delimitados por espaços. Os operadores são *, /, + e - e supomos que os operandos são valores inteiros de um dígito. A saída será um resultado inteiro.

1. Crie uma pilha vazia chamada operandStack.

2. Converta a string para uma lista usando o método string split().

3. Digitalize a lista de itens da esquerda para a direita.

   • Se o item for um operando, converta-o de uma string para um inteiro

     e insira-o em operandStack.

   • Se o item for um operador, *, /, + ou -, serão necessários dois operandos. Faça duas remoções de operandStack. O primeiro valor removido é o segundo operando e o segundo valor removido é o primeiro operando. Execute a operação aritmética. Insira o resultado em operandStack.

4. Quando a expressão de entrada foi completamente processada, o resultado está na pilha. Remova de operandStack o valor e retorne-o.

A função completa para a avaliação de expressões posfixa é mostrada em ActiveCode 2. Para ajudar com a aritmética, usamos uma função auxiliar doMath() que recebe dois operandos e um operador e, em seguida, executa e retorna o resultado da operação sobre os operandos.

É importante notar que tanto na conversão para posfixa quanto no programa de avaliação da expressão posfixa supomos que não havia erros no expressão de entrada. Usando esses programas como ponto de partida, você pode ver facilmente como a detecção e o relatório de erros podem ser incluídos. Nós deixamos isso como um exercício no final do capítulo.