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: .. sourcecode:: python 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: .. sourcecode:: python >>> 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}`` ============================================================================== ================================ =======================