Tratamento de expressões posfixas

Para ler esta seção é necessário que você tenha entendido pilhas e dicionários.

A calculadora a ser implementada deve ler várias expressões na notação polonesa na forma de strings (a função input() faz o serviço) e calcular o valor de cada uma das expressões, de maneira semelhante ao Python Shell.

Para calcular o valor de uma expressão, o string de entrada deve ser processado para identificar cada elemento (token) que compõe a expressão. Essa foi a missão do EP6 e EP7.. Os tokens permitidos nesse EP são de 3 categorias: NUMERO, VARIAVEL, e OPERADOR.

O nome de uma variável é uma sequência de letras, números e _, começando por uma letra.

Por exemplo, a expressão polonesa 'abc 7 5 2 - * 4 ! / =', que equivale a expressão infixa 'abc = (7*(5-2))/!4', é composta de 10 tokens, como a função tokeniza() pode comprovar:

Python 3.4.3 (default, Mar 26 2015, 22:03:40)
[GCC 4.9.2] on linux
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>>
>>> lista = tokeniza("abc 7 5 2 - * 4 ! / =")
>>> imprima_tokens(lista)
[V('abc'), N(7), N(5), N(2), O('-'), O('*'), N(4), O('!'), O('/'), O('=')]
>>>

Os tokens são representados como objetos da classe Token. Como foi feito no EP7, esses objetos serão instâncias da classe Token que foi definida no modulo tokeniza.py.

Uma vez convertida a expressão para uma lista de tokens pela função tokeniza(), cada token é processado da seguinte forma. Considere uma pilha de execução inicialmente vazia e um dicionário de variáveis também inicialmente vazio:

• Tokens das categorias NUMERO e VARIAVEL são empilhados na pilha de execução. A pilha de execução contém apenas objetos da classe Token que são das categorias NUMERO e VARIAVEL.
• Tokens da categoria OPERADOR exigem que desempilhemos um número apropriado de operandos (= números ou variáveis) da pilha de execução, a operação é executada utilizando os valores desses tokens como argumentos. No caso de uma variável, o valor numérico armazenado no dicionário e utilizado como argumento. O resultado da operação é empilhado na pilha de execução como um novo objeto da classe ``Token`` de categoria NUMERO.
• O operador de atribuição (símbolo '=') pode alterar o valor de uma variável já existente no dicionário de variáveis ou criar uma nova variável que está sendo criada pela primeira vez. Esse comportamento é identico ao do Python.
• Quando o último token da lista de tokens é processado, caso a expressão seja válida, o resultado deve ser o único objeto na pilha de execução, Esse elemento deve ser um token da categoria NUMERO ou VARIAVEL. Em caso contrário a expressão é inválida.

Para entender esse processamento, acompanhe a simulação a seguir.

Exemplo

Considere a seguinte lista de de tokens:

>>> tokens = tokeniza("var 7 5 2 -* 4 !/=")
>>> imprima_tokens(tokens)
[V('var'), N(7), N(5), N(2), O('-'), O('*'), N(4), O('!'), O('/'), O('=')]
>>> >>> tokens = tokeniza("var 7 5 2 -* 4 !/=")
>>> imprima_tokens(tokens)
[V('var'), N(7), N(5), N(2), O('-'), O('*'), N(4), O('!'), O('/'), O('=')]
>>>

A medida que a lista tokens é processada da esquerda para a direita:

• V('var'), N(7), N(5) e N(2) são empilhados na pilha de execução;
• O('-') exige que N(5) e N(2) sejam desempilhado e o valor de 5-2 seja calculado e token N(3) seja empilhado;
• O('*') faz que N(3) e N(7) e sejam desempilhado, o valor de 7*3 seja calculado e empilha na forma do token N(21);
• N(4) é empilhado;
• O('!') faz com que N(4) seja desempilhado , o valor de -4 seja calculado e empilha na forma do token N(-4);
• O('/') desempilha N(-4) e N(21), calcula o valor de 21/-4, e empilha o resultado na forma N(-5.25); e
• O('=') faz com que N(-5.25) e V('var') sejam desempinhados, insere chave 'var'``no dicionário de variáveis com valor ``-5.25, e empilha esse valor na forma N(-5.25).

A tabela abaixo mostra o estado da lista de tokens a serem processados, da pilha de execução e do dicionário de variáveis a cada vez que um token da lista é tratado.

lista de tokens	pilha de execução	dicionário de variáveis
[V('var'), N(7), N(5), N(2), O('-'), O('*'), N(4), O('!'), O('/'), O('=')]	[]	{}
[N(7), N(5), N(2), O('-'), O('*'), N(4), O('!'), O('/'), O('=')]	[V('var')]	{}
[N(5), N(2), O('-'), O('*'), N(4), O('!'), O('/'), O('=')]	[V('var'), N(7)]	{}
[N(2), O('-'), O('*'), N(4), O('!'), O('/'), O('=')]	[V('var'), N(7), N(5)]	{}
[O('-'), O('*'), N(4), O('!'), O('/'), O('=')]	[V('var'), N(7), N(5), N(2)]	{}
[O('*'), N(4), O('!'), O('/'), O('=')]	[V('var'), N(7), N(3)]	{}
[N(4), O('!'), O('/'), O('=')]	[V('var'), N(21)]	{}
[O('!'), O('/'), O('=')]	[V('var'), N(21), N(4)]	{}
[O('/'), O('=')]	[V('var'), N(21), N(-4)]	{}
[O('=')]	[V('var'), N(-5.25)]	{}
[]	[N(-5.25)]	{'var': -5.25}