MAC0122-2015: [EP9] Como tratar o menos unário

Na função infixa_para_posfixa, usando o algorítmo sugerido na bibliografia, o operador 'menos unário' dá problema quando utilizado em sequência.

A cada vez que a iteração vê um operador, verifica-se se há um operador na pilha de maior ou igual precedência, e o adiciona ao output, e depois coloca o operador visto na pilha. Quando há um número ou variável, apenas se o adiciona ao output diretamente. Aí, quando é fornecida um expressão do tipo:

>>> ! ! 1

Em vez de virar "1 ! !" na notação pós-fixa, a expressão vira "! 1 !", que é errado.

Ainda entre problemas com menos unário, ao escrever:

>>> ! 2 ^ 3

Devo ler como "-(2^3)" ou "(-2)^3" ?

Enfim, como lido com esses casos?

Re: [EP9] Como tratar o menos unário

by José Coelho de Pina - Thursday, 29 October 2015, 4:33 PM

Aí, quando é fornecida um expressão do tipo:

>>> ! ! 1

Em vez de virar "1 ! !" na notação pós-fixa, a expressão vira "! 1 !", que é errado.

Acho que aqui é que está a diferença entre a precedência ser da esquerda para a direita ou direita para a esquerda (veja aqui).
No seu programa você deve separar o tratamento dos operadores em dois casos.
O tratamendo dos operadores em que a precedência é da esquerda para a direita e da direita para a esquerda
é levemente diferente (no código troca-se um ≥ por um >).

>> tokens = tokeniza("!!! !1")
>>> imprima_tokens(tokens)
[O('!'), O('!'), O('!'), O('!'), N(1)]
>>> posfixa = infixa_para_posfixa(tokens)
>>> imprima_tokens(posfixa)
[N(1), O('!'), O('!'), O('!'), O('!')]
>>> hp = Calculadora()
>>> hp.eval("! !! !1")
1.0
>>>

Ainda entre problemas com menos unário, ao escrever:

>>> ! 2 ^ 3

Devo ler como "-(2^3)" ou "(-2)^3" ?

>>> 
>>> tokens = tokeniza("!(2^3) # assim que se escreve -(2^3)")
>>> imprima_tokens(tokens)
[O('!'), P('('), N(2), O('^'), N(3), P(')')]
>>> posfixa = infixa_para_posfixa(posfixa)
>>> imprima_tokens(posfixa)
[N(1), O('!'), O('!'), O('!'), O('!')]
>>> hp.eval("!(2^3) # assim que se escreve -(2^3)")
-8.0
>>> tokens = tokeniza("(!2)^3 # = em python (-2)**3")
>>> imprima_tokens(tokens)
[P('('), O('!'), N(2), P(')'), O('^'), N(3)]
>>> posfixa = infixa_para_posfixa(tokens)
>>> imprima_tokens(posfixa)
[N(2), O('!'), N(3), O('^')]
>>> hp.eval("(!2)^3 # = em python (-2)**3")
-8.0
>>> -2**3
-8
>>> (-2)**3
-8
>>> -2**4
-16
>>> (-2)**4
16
>>> hp.eval("(!2)^4")
16.0
>>> hp.eval("!(2)^4")
-16.0
>>>

Re: [EP9] Como tratar o menos unário

by Willian Akira Mizutani - Thursday, 29 October 2015, 11:39 PM

"O tratamendo dos operadores em que a precedência é da esquerda para a direita e da direita para a esquerda é levemente diferente (no código troca-se um ≥ por um >)."

A solução parece funcionar, mas não entendi por quê. Entendi conceitualmente o porquê de ser assim, mas não entendi a implementação em código.

Aliás, não entendi o algorítmo como um todo, mas isso é outro rolê já.

Ah sim, obrigado

Re: [EP9] Como tratar o menos unário

by José Coelho de Pina - Friday, 30 October 2015, 10:03 AM

mas não entendi a implementação em código.

Quando a precedência é da direira par a esquerda, quando há empate na precedência entre o operador sendo examinado e o operador no topo da pilha, o operador do topo da pilha deve permancer na pilha e o novo operador será empilhado. Com isso garantimos que na expressão posfixa esses operadores apareçam no ordem inversa àquela que foram examinados.

>>> 
>>> tokens = tokeniza("2^3^4^5")
>>> imprima_tokens(tokens)
[N(2), O('^'), N(3), O('^'), N(4), O('^'), N(5)]
>>> posfixa = infixa_para_posfixa(tokens)
-----
token a ser examinado =  N(2)
posfixa =[]
pilha   = []
-----
token a ser examinado =  O('^')
posfixa =[N(2)]
pilha   = []
-----
token a ser examinado =  N(3)
posfixa =[N(2)]
pilha   = [O('^')]
-----
token a ser examinado =  O('^')
posfixa =[N(2), N(3)]
pilha   = [O('^')]
-----
token a ser examinado =  N(4)
posfixa =[N(2), N(3)]
pilha   = [O('^'), O('^')]
-----
token a ser examinado =  O('^')
posfixa =[N(2), N(3), N(4)]
pilha   = [O('^'), O('^')]
-----
token a ser examinado =  N(5)
posfixa =[N(2), N(3), N(4)]
pilha   = [O('^'), O('^'), O('^')]
-----
desempilhando tokens... 
posfixa =[N(2), N(3), N(4), N(5)]
pilha   = [O('^'), O('^'), O('^')]
-----
desempilhando tokens... 
posfixa =[N(2), N(3), N(4), N(5), O('^')]
pilha   = [O('^'), O('^')]
-----
desempilhando tokens... 
posfixa =[N(2), N(3), N(4), N(5), O('^'), O('^')]
pilha   = [O('^')]
-----
posfixa =[N(2), N(3), N(4), N(5), O('^'), O('^'), O('^')]
pilha   = []
>>> 
>>> tokens = tokeniza("2+3+4+5")
>>> imprima_tokens(tokens)
[N(2), O('+'), N(3), O('+'), N(4), O('+'), N(5)]
>>> posfixa = infixa_para_posfixa(tokens)
-----
token a ser examinado =  N(2)
posfixa =[]
pilha   = []
-----
token a ser examinado =  O('+')
posfixa =[N(2)]
pilha   = []
-----
token a ser examinado =  N(3)
posfixa =[N(2)]
pilha   = [O('+')]
-----
token a ser examinado =  O('+')
posfixa =[N(2), N(3)]
pilha   = [O('+')]
-----
token a ser examinado =  N(4)
posfixa =[N(2), N(3), O('+')]
pilha   = [O('+')]
-----
token a ser examinado =  O('+')
posfixa =[N(2), N(3), O('+'), N(4)]
pilha   = [O('+')]
-----
token a ser examinado =  N(5)
posfixa =[N(2), N(3), O('+'), N(4), O('+')]
pilha   = [O('+')]
-----
desempilhando tokens... 
posfixa =[N(2), N(3), O('+'), N(4), O('+'), N(5)]
pilha   = [O('+')]
-----
posfixa =[N(2), N(3), O('+'), N(4), O('+'), N(5), O('+')]
pilha   = []
>>>