RPN Calculator
February 19, 2009
Implement an RPN calculator that takes an expression like 19 2.14 + 4.5 2 4.3 / - * which is usually expressed as (19 + 2.14) * (4.5 - 2 / 4.3) and responds with 85.2974. The program should read expressions from standard input and print the top of the stack to standard output when a newline is encountered. The program should retain the state of the operand stack between expressions.
Pages: 1 2
Haskell:
import Control.Applicative.Error import Control.Monad import Data.Map (fromList, (!)) main = getContents >>= mapM_ (print . take 1) . scanl calculate [] . lines calculate :: [Float] -> String -> [Float] calculate stack = foldl process stack . words process :: [Float] -> String -> [Float] process stack word = case maybeRead word of Just x -> x:stack Nothing -> (operators ! word) (stack !! 1) (stack !! 0) : drop 2 stack where operators = fromList [("+", (+)), ("-", (-)), ("*", (*)), ("/", (/))]I’m using problems on this site to learn haskell. Please do let me know if I could have solved this in a better way.
import Data.List (intercalate)
evaluate :: String -> Float
evaluate str = calculate (tokenize str)
tokenize :: String -> [String]
tokenize = words
calculate :: [String] -> Float
calculate exp = rpn_eval exp [0.0]
rpn_eval :: [String] -> [Float] -> Float
rpn_eval [] stack = stack!!0
rpn_eval (x:xs) stack | isOperator x = rpn_eval xs ((eval_expr x (take 2 stack)) : (drop 2 stack))
| otherwise = rpn_eval xs ((read x :: Float) : stack)
isOperator :: String -> Bool
isOperator token = token `elem` ["+","-","/","*"]
eval_expr :: String -> [Float] -> Float
eval_expr “+” [x,y] = x + y
eval_expr “-” [x,y] = y – x
eval_expr “*” [x,y] = x * y
eval_expr “/” [x,y] = y / x
eval_expr _ [x,y] = undefined
calculateExprs :: String -> String
calculateExprs str = intercalate “\n” (map (show . evaluate) (lines str))
main = do interact calculateExprs
A slight redesign of my previous code:
my Ocaml version.
My haskell version, similar to that of FalconNL, although a bit more verbose
parse :: String -> Either Double (Double -> Double -> Double)
parse s = maybe (Left $ read s) Right (lookup s ops)
where ops = zip ["+","-","*","/"] [(+),(-),(*),(/)]
go :: [Double] -> [String] -> [Double]
go stack [] = stack
go stack (w:ws) = case parse w of
Left x -> go (x:stack) ws
Right f -> go (apply f stack) ws
where apply f (x:y:xs) = (f x y:xs)
eval :: [[String]] -> [Double]
eval = map head . tail . scanl go []
main = getContents >>= mapM_ print . eval . map words . lines
Sorry, I didn’t follow the instruction concerning howto paste code. Here is a link to the formatted code : http://codepad.org/x3Ai1SN2
Here’s my Python solution.
def get_input_tokens(msg='> '): """get user input and return it as tokens in a list""" expression = raw_input(msg) return expression.split() def to_float(number): try: return float(number) except: return number def convert_to_expression(tokens): """convert the RPN expression to algebraic notation""" operations = ('^', '*', '/', '+', '-') num_operations = len([item for item in tokens if item in operations]) num_numbers = len(tokens) - num_operations if num_operations + 1 != num_numbers: raise ValueError, "number of operations don't correspond with numerals" # parse the RPN expression expression = '' for token in tokens[:]: if token in operations: i = tokens.index(token) if tokens[i] == '^': tokens[i] = '**' tokens = tokens[:i - 2] +\ ['(' + ' '.join([tokens[i - 2]] +\ [tokens[i]] + [tokens[i - 1]]) + ')']\ + tokens[i + 1:] return tokens[0] if __name__ == '__main__': while True: expression = raw_input('>> ') if expression == 'exit': break if expression[0] in (';', ':', '>'): import os os.system(expression[1:]) print continue expression = expression.split() try: print '=> ' + str(eval(convert_to_expression(expression[:]))) except: print 'Invalid expression.' printI bet that there’s an easier way to do this in Python. But this is what I came up with.
It’s kind of like an interactive shell. Just enter the RPN expression, and it’ll return the value.
Although the expression we’re supposed to use for testing gives me 222149.08271379699 instead of 85.2974.
I have just began learning Erlang so it is probably far from perfect :)
-module(rpn). -export([start/0]). process(Token, Stack)-> case Token of {_,_,Value} -> [Value|Stack]; {Operator,_} -> [X,Y|Tail] = Stack, case Operator of '+' -> [X+Y|Tail]; '-' -> [Y-X|Tail]; '*' -> [Y*X|Tail]; '/' -> [Y/X|Tail] end end. start() -> start([]). start(Stack) -> Line = io:get_line(">"), {ok, Tokens,_} = erl_scan:string(Line), NewStack = lists:foldl(fun process/2,Stack,Tokens), [First|_] = NewStack, io:fwrite("~w~n", [First]), start(NewStack).I’ve just been learning lisp, so I’m giving that a shot first:
(defun split-by-one-space (string)
“Returns a list of substrings of string
divided by ONE space each.
Note: Two consecutive spaces will be seen as
if there were an empty string between them.
Thanks to http://cl-cookbook.sourceforge.net/strings.html”
(loop for i = 0 then (1+ j)
as j = (position #\Space string :start i)
collect (subseq string i j)
while j))
(defun evaluate-rpn(expr)
(loop
with stack = (list)
for token in (split-by-one-space expr)
do (let ((digit (read-from-string token nil))
(*read-eval* nil)) ; By default, read-from-string will evaluate things. Boo!
(cond
((realp digit)
;;Digit is a number
(push digit stack))
(t
;; Gotta pop the two values off the stack
;; and evaluate them, what fun!
(let ((b (pop stack))
(a (pop stack)))
;; If the function is one we can parse, then go ahead and
;; evaluate it
(cond
((find digit ‘(+ – / * mod sin cos atan tan))
(push (funcall digit a b) stack))
(t (format t “Could not parse ~s~%” token)))))))
finally (return (car stack))))
;; Now loop through and actually do it
(loop
(format t “~&> “)
(force-output)
(print (evaluate-rpn (read-line))))
And my undocumented python solution:
#!/usr/bin/env python import math import operator """ Simple RPN evaluator """ operations = { "+": operator.add, "-": operator.sub, "*": operator.mul, "/": operator.div, "sin": math.sin, "cos": math.cos, } def rpn_eval(string): stack = [] for token in string.split(" "): if set(token).issubset(set("0123456789.")): stack.append(float(token)) elif token in operations: b = stack.pop() a = stack.pop() stack.append(operations[token](a, b)) else: print "Unparsable token: \"%s\"" % token return stack.pop() while True: print rpn_eval(raw_input("> "))[...] is a simple calculator that handles Reverse Polish Notation (RPN) caculations. The problem is givenhere , and my solution in Java is given [...]
Ruby example:
$stack = [] def solve(ops) while (op = ops.pop) do if '+-*/'.index op raise "Not enough operands" if $stack.length < 2 a,b = $stack.pop(2) case op when '+' then $stack.push(a + b) when '-' then $stack.push(a - b) when '*' then $stack.push(a * b) when '/' then $stack.push(a / b) end else $stack.push(op.to_f) end end end loop { print "RPN > "; STDOUT.flush solve(readline.split(' ').reverse) p $stack }Example output:
RPN > 10 2 *
[20.0]
RPN > 5 +
[25.0]
RPN > 5 /
[5.0]
RPN > 3 -
[2.0]
RPN > 1
[2.0, 1.0]
RPN > +
[3.0]
RPN > 19 2.14 + 4.5 2 4.3 / – *
[3.0, 85.2974418604651]
; programming praxis exercise 1 – RPN Calculator
(defn rpn [stack value]
(let [[s1 s2] stack
v (eval (read-string value))]
(cond
(number? v) (conj stack v)
(fn? v) (conj (rest (rest stack)) (v s2 s1))
:else stack)))
(defn calc [stack line]
(let [newstack (reduce rpn stack (.split line " "))]
(println (first newstack))
newstack))
(defn rpn-repl []
(loop [stack '()]
(recur (calc stack (read-line)))))