RPN Calculator in Haskell

In the following program, the function evalrpn takes a list of tokens and returns, through show, the string representation of the number that results from evaluatinng the respective RPN expression, or the string "error". Reading the input, doing initial processing on it, and printing the outcome of evalrpn is the responsibility of main.

By calling getContents, the entire input stream is obtained as a single string. However, reading is actually lazy, progressing only as far as there is demand for it, which in particular makes it possible to be interlaced with printing the values of the RPN expressions. The result of getContents is passed to a composition of several transformations (dot (.) is the composition operator). lines splits the input into lines, thus producing a list of strings. map words then breaks each line down to a list of individual tokens. Further on, any possible empty lists of tokens (i.e., all empty lines) are filter-ed out. Finally, each remaining line, as a list of tokens, is reverse-d, passed to evalrpn, and the result of the latter is printed. The composition of these three actions that constitute the processing of a single line is applied through mapM_, which is the monadic (in the Haskell sense of the word monad) variant of map. This, together with the lazyness of the language and the use of the (also monadic) operator >>= to communicate the result of getContents to the composition of functions that processes it, ensures that the input and output are properly sequenced as required by the interactive nature of the calculator. Explicitly setting a line-level buffering for the standard input and output channels, so as to keep/flush the buffer of each at the right times is still needed, though, hence done before any reading takes place.

evalrpn uses a locally defined function, eval, to do the real work of evaluating an expression. eval is recursive on its argument – the reversed list of RPN expression tokens. It checks whether a token tk is a number. If tk is not a number, but appears to be an operator, and if the two recursive calls of eval on the rest of the token list are successful in producing arguments y and x for that operator, tk is mapped (by means of the inner case expression) to the corresponding function and the latter is applied to x and y.

Both the parsing of a token as a number and the extraction of the correspondng numeric value are done entirely within the program – the part after the let, resulting in computing the value maybenum. This is not because Haskell does not have its own library functions for parsing numeric values, but because these functions – and the language itself – accept no leading or trailing dots in floating-point numeric denotations. Neither do they accept numbers with a + arithmetic sign.

After doing all the necessary checks on tk in order to ensure that it represents a number according to our specification, the respective numeric value gets stored in maybenum as a value of type Maybe, such as e.g. Just 217 or Just 23.8. If tk turns to be not a number, maybenum holds the value Nothing (also of type Maybe). The remainder of the program ‘knows’ if tk was a number by distinguishing whether maybenum was constructed by Just or not.

Notably, it is precisely because of the explicit parsing of numbers that the program has to import library functions from the modules Data.List, Data.Char and Data.Maybe.

In order to keep track of the consumption of the token list across its recursive self-invocations, eval returns a pair where the second item is the unused part of its argument – a list of tokens. The first item in the pair is the computed number. An RPN expression is successfully evaluated if the top-level call of eval returns an empty list z. In case of syntax error in the expression, including eval calling itself with an empty list, eval returns (an insignificant 0 and) a list with a single empty string in it. That way, an error is propagated upwards to the top-level call of eval and eventually leads to returning "error" from evalrpn.

import System.IO;  import Data.List;  import Data.Char;  import Data.Maybe

main = do hSetBuffering stdin LineBuffering
          hSetBuffering stdout LineBuffering
          getContents >>= mapM_ (putStrLn . evalrpn . reverse) .
                          filter (/=[]) . map words . lines

evalrpn tks = if null z then show r else "error"  where
  (r,z) = eval tks
  eval []       = (0,[""])
  eval (tk:tks) =
    let h:t = tk
        tk1 = if elem h "+-" then t else tk
        tk2 = delete '.' tk1
        sgn = if h=='-' then -1 else 1
        dp = fromMaybe 0 (findIndex (=='.') (reverse tk1))
        cnum v d = 10*v + fromIntegral (digitToInt d)
        maybenum = if tk2==[] || not (all isDigit tk2) then Nothing
                   else Just (sgn * foldl cnum 0 tk2 / 10^dp)
    in case maybenum of
         Just r -> (r,tks)
         _ -> if t==[] && elem h "+-*/" && z2/=[""]
              then ((case tk of "+" -> (+); "-" -> (-)
                                "*" -> (*); "/" -> (/)) x y, z2)
              else (0,[""])
                where  (y,z1) = eval tks
                       (x,z2) = eval z1

boykobbatgmaildotcom