Menu Close

Notación polaca inversa

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

6 soluciones de “Notación polaca inversa

  1. enrnarbej

    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
    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
    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
    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
    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
    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 Fran Cruz Cancel reply

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