Menu Close

Notación polaca inversa

José A. Alonso,

La notación polaca inversa (en inglés, Reverse Polish Notation, o RPN), es una forma alternativa de escribir expresiones matemáticas. Por ejemplo, la expresión "20 - (4 + 3) * 2" en RPN es "20 4 3 + 2 * -".

Para evaluar una expresión en RPN, usamos una lista auxiliar (inicialmente vacía) y recorremos la expresión de izquierda a derecha. Cada vez que encontramos un número, lo añadimos a la lista auxiliar. Cuando encontramos un operador, retiramos los dos números que hay al principio de la pila, utilizamos el operador con ellos y los quitamos de la lista y le añadimos el resultado. Cuando alcancemos el final de la expresión, debemos tener un solo número en la lista auxiliar si la expresión estaba bien formada, y éste representa el resultado de la expresión. Por ejemplo, la evaluación de RPN "20 4 3 + 2 * -" es la siguiente

   ""                 []
   "20"               [20]
   "20 4"             [4, 20]
   "20 4 3"           [3, 4, 20]
   "20 4 3 +"         [7, 20]
   "20 4 3 + 2"       [2, 7, 20]
   "20 4 3 + 2 *"     [14, 20]
   "20 4 3 + 2 * -"   [6]

Definir la función

   valor :: String -> Float

tal que (valor cs) es el valor de la expresión RPN cs. Por ejemplo,

   valor "4"               ==  4.0
   valor "4 3 +"           ==  7.0
   valor "4 3 + 2 *"       ==  14.0
   valor "20 4 3 + 2 * -"  ==  6.0
   valor "3 7 + 2 /"       ==  5.0

Soluciones

valor :: String -> Float
valor = head . foldl aux [] . words
  where aux (x:y:ys) "+" = (x + y) : ys
        aux (x:y:ys) "-" = (y - x) : ys
        aux (x:y:ys) "*" = (x * y) : ys
        aux (x:y:ys) "/" = (y / x) : ys
        aux xs cs        = read cs : xs
Posted in Medio
Tagged , , , ,

6 Comments

  1. enrnarbej
    Responder 

    valor :: String -> Float
valor cs = head $ valorAux [] (words cs)
  where
    valorAux :: [Float] -> [String] -> [Float]
    valorAux xs (y:ys)
      | y `elem` ["+","*","/","-"] =
           valorAux (opera y (take 2 xs) : (drop 2 xs)) ys
      | otherwise = valorAux (read y : xs) ys
    valorAux xs [] = xs
 
opera :: String -> [Float] -> Float
opera "+" (y:x:xs) = x + y
opera "*" (y:x:xs) = x * y
opera "-" (y:x:xs) = x - y
opera "/" (y:x:xs) = x / y
  2. Fran Cruz
    Responder 
    import Data.Char
 
valor :: String -> Float
valor = rpn []
  where rpn :: [Float] -> String -> Float
        rpn xs ys | null ys   = head xs
                  | isDigit y = rpn (read ns: xs) ts
                  | otherwise = rpn (op y a b: ms) ts
          where (y:_)    = ys
                (ns,rs)  = span (not.isSpace) ys
                ts       = dropWhile isSpace rs
                (a:b:ms) = xs
        op :: Char -> Float -> Float -> Float             
        op '+' a b = b + a
        op '-' a b = b - a
        op '*' a b = b * a
        op '/' a b = b / a
  3. albcercid
    Responder 
    valor :: String -> Float
valor cs = aux [] cs 0 0
 
aux :: [Float] -> String -> Float -> Float -> Float
aux v [] a t = head v
aux [] [x] a t = rN x
aux v (x:xs) a t
  | x == ' ' && t == 0 = aux (a:v) xs 0 0
  | x == ' ' = aux v xs 0 0
  | isInt x = aux v xs (10*a + rN x) 0
  | otherwise = aux (rOp x (head v) (head $ tail v): tail (tail v)) xs 0 1
 
isInt :: Char -> Bool
isInt x = x `elem` "0123456789"
 
rOp :: Char -> Float -> Float -> Float 
rOp x b c | x == '+'  = b+c
          | x == '-'  = c-b
          | x == '*'  = b*c
          | otherwise = c/b
  4. Chema Cortés
    Responder 
    import Data.Char (isDigit)
 
valor :: String -> Float
valor cs = rpn (words cs) []
  where rpn [] ss = head ss
        rpn (x:xs) ss | (isDigit.head) x  = rpn xs (read x:ss)
                      | otherwise         = rpn xs (apply (op x) ss)
 
data Op a = Inv
          | Unary (a -> a)
          | Binary (a -> a -> a)
 
apply :: Op a -> [a] -> [a]
apply Inv (x:y:xs)        = y : x : xs
apply (Unary f) (x:xs)    = f x : xs
apply (Binary f) (x:y:xs) = f y x : xs
apply _ _ = error "Stack empty"
 
op :: String -> Op Float
op "+"    = Binary (+)
op "-"    = Binary (-)
op "*"    = Binary (*)
op "/"    = Binary (/)
op "neg"  = Unary negate
op "!"    = Unary (x -> product [1..x])
op "inv"  = Inv
op "del"  = Binary const
op o      = error ("Operación no reconocida: " ++ o)
  5. albcercid
    Responder 
    valor :: String -> Float
valor cs = aux [] cs 0 0
  where aux v [] a t = head v
        aux [] [x] a t = rN x
        aux v (x:xs) a t
          | x == ' ' && t == 0 = aux (a:v) xs 0 0
          | x == ' ' = aux v xs 0 0
          | isInt x = aux v xs (10*a + rN x) 0
          | otherwise = aux ((rOp x (head v) (head $ tail v)):(tail $ tail v)) xs 0 1
        isInt x = elem x "0123456789"
        rOp x b c
          | x == '+' = b+c
          | x == '-' = c-b
          | x == '*' = b*c
          | otherwise = c/b
        rN x = fst $ head [ (a,b) | (a,b) <- zip [0..9] "0123456789", x == b]
  6. eliguivil
    Responder 
    valor :: String -> Float
valor = auxv []
  where
    auxv [n]      ""       = n
    auxv (n:m:ns) ('+':cs) = auxv (m+n:ns) cs
    auxv (n:m:ns) ('-':cs) = auxv (m-n:ns) cs
    auxv (n:m:ns) ('*':cs) = auxv (m*n:ns) cs
    auxv (n:m:ns) ('/':cs) = auxv (m/n:ns) cs
    auxv ns (c:cs)
      | isDigit c = auxv (read (takeWhile isDigit (c:cs)):ns)
                         (dropWhile isDigit (c:cs))
      | otherwise = auxv ns cs

Leave a Reply to Chema CortésCancel reply

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.