0votos

notación posfija en Haskell

por josejuan hace 1 año

Una simple.

realizar algoritmo que calcule el resultado de cualquier notación posfija dada

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
pf :: [String] ->[String] ->[String] 
pf    []  rs = rs 
pf (x:xs) rs = case x of 
                 "+"   ->pf xs $ bi (+) rs 
                 "-"   ->pf xs $ bi (-) rs 
                 "/"   ->pf xs $ bi (/) rs 
                 "*"   ->pf xs $ bi (*) rs 
                 "neg" ->pf xs $ un negate rs 
                 "cos" ->pf xs $ un cos rs 
                 "sin" ->pf xs $ un sin rs 
                 x     ->pf xs (x:rs) 
  where bi f (a:b:rs) = show (f (read a) (read b)): rs 
        bi _       _  = error "bad state" 
        un f (a:rs)   = show (f (read a)): rs 
        un _     _    = error "bad state" 
 
{- 
> pf ["3", "4", "+", "2", "*", "neg", "cos"] [] 
["0.1367372182078336"] 
-} 
5 comentarios
0votos

Escrito por AverageUser hace 1 año

*Main> pf ["10", "2", "/"] []
["0.2"]

Debería dar 5 en realidad, pero es algo fácil de corregir.
Ahora subo una solución también
0votos

Escrito por josejuan hace 1 año

¿Porqué tiene que dar 5?
1votos

Escrito por AverageUser hace 1 año

En todos los lugares donde he leído sobre RPN (Reverse Polish Notation)
se evalúa de esa forma, es decir: las funciones binarias no conmutativas evalúan primero primero lo que se leyó primero.

Ej: 3 2 - == (3 - 1) , 10 2 / = (10/2), 3 2 - 5 - = ((3-2) - 5)

No conozco la definición original de RPN, así que no puedo estar seguro, pero es lo que he visto

The infix expression "5 + ((1 + 2) × 4) − 3" can be written down like this in RPN:

    5 1 2 + 4 × + 3 − 

este extracto de wikipedia donde 5 + ((1+2)x4) -3 = 14

evalúa de esta forma en tu programa
*Main> pf ["5", "1", "2", "+", "4", "*", "+", "3", "-"] []
["-14"]
1votos

Escrito por josejuan hace 1 año

Lógicamente no hay por qué seguir la convención pero tiene sentido lo que comentas. ¡Gracias por el apunte!

(Para corregir aplicar `flip` en esos casos)
0votos

Escrito por AverageUser hace 1 año

Claro, es cosa de definición solamente. Aun que si creo que es mas intuitiva la forma convencional, para un humano, para el programa no.

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.