content: {-# OPTIONS_GHC -fglasgow-exts -Wall #-}
  
  -- The RPN evaluator algorithm was originally based on:
  --   http://en.wikipedia.org/wiki/Haskell_programming_language
  -- However, the error handling in that algorithm was not to my
  -- liking, so this module has evolved since to mimic the method
  -- used in the Perl versions.
  
  -- Note that a Stack abstract data type seems unnecessary in
  -- Haskell since built-in lists can be used as a stack.
  -- (Indeed, I couldn't find a stack abstract data type
  -- anywhere in the GHC libraries).
  
  module Rpn (evaluate) where
  
  import Data.Char
  -- import Debug.Trace
  
  -- Check that a string consists of just digits.
  isStrDigit :: String -> Bool
  isStrDigit = all isDigit
  
  -- Check that a string matches regex /^-?\d+$/.
  isSNum :: String -> Bool
  isSNum []        = False
  isSNum "-"       = False
  isSNum ('-':xs)  = isStrDigit xs
  isSNum xs        = isStrDigit xs
  
  calc :: Int -> String -> Int -> Int
  calc x "+" y  = x+y
  calc x "-" y  = x-y
  calc x "*" y  = x*y
  calc x "/" y  = x`div`y
  calc _ tok _  = error $ "Invalid token:" ++ show tok
  
  evalStack :: [Int] -> String -> [Int]
  evalStack xs y
    | isSNum y        = (read y):xs
    | (a:b:cs) <- xs  = (calc b y a):cs
    | otherwise       = error "Stack underflow"
  
  evaluate :: String -> Int
  evaluate expr
    | [e] <- el       = e
    | otherwise       = error $ "Invalid stack:" ++ show el
    where
    el = foldl evalStack [] $ words expr
  
  -- Example trace line
  --   f (x:y:zs) "+" = trace ("k+" ++ show x ++ ":" ++ show y ++ ":" ++ show zs) (y+x:zs)
  