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)))))
A straightforward perl example with no error handling
use strict; use warnings; my @stack = (); my %operators = ( '+' => sub { $_[1] + $_[0] }, '-' => sub { $_[1] - $_[0] }, '*' => sub { $_[1] * $_[0] }, '/' => sub { $_[1] / $_[0] }, ); while (my $line = <STDIN>) { chomp $line; my @symbols = split /\s+/, $line; foreach my $s (@symbols) { if (defined $operators{$s}) { push @stack, $operators{$s}->(pop @stack, pop @stack); } else { push @stack, $s; } } if (scalar @stack != 1) { print "Error parsing expression.\n"; } else { print(pop(@stack), "\n"); } }Scheme version, worked to make adding new operations easy:
#lang racket ;; two funcs from (draga utils) ;; asss : string alist -> alist or boolean ;; as assq, but uses string=? for comparisons (define (asss str alist) (cond [(null? alist) #f] [(and (string? (caar alist)) (string=? str (caar alist))) (car alist)] [else (asss str (cdr alist))])) ;; asss/ci : string alist -> alist or boolean ;; as assq, but uses string-ci=? for comparisons (define (asss/ci str alist) (cond [(null? alist) #f] [(and (string? (caar alist)) (string-ci=? str (caar alist))) (car alist)] [else (asss str (cdr alist))])) ;; action : line stack -> stack ;; given an input line and the current stack, take the action requested and return ;; the updated stack (define (action line stack) (cond [(eof-object? line) (newline) (exit)] [(string->number line) => (lambda (n) (cons n stack))] [(asss/ci line action-list) => (lambda (a) ((cdr a) stack))] [else (display "ERROR\n") (exit #f)])) (define (rpn-top stack) (display (car stack)) (newline) stack) (define (rpn-plus stack) (cons (+ (cadr stack) (car stack)) (cddr stack))) (define (rpn-minus stack) (cons (- (cadr stack) (car stack)) (cddr stack))) (define (rpn-times stack) (cons (* (cadr stack) (car stack)) (cddr stack))) (define (rpn-divby stack) (cons (/ (cadr stack) (car stack)) (cddr stack))) (define action-list `( ( "" . ,rpn-top) ( "+" . ,rpn-plus) ( "-" . ,rpn-minus) ( "*" . ,rpn-times) ( "/" . ,rpn-divby) )) (define (rpn) (display "? ") (let ([in (current-input-port)]) (let loop ([l (read-line in)] [s '()]) (let ([new-s (action l s)]) (display "? ") (loop (read-line in) new-s))))) (rpn)Here’s another ruby version, you can see it fully commented at http://steamcode.blogspot.com/2010/07/rpn-calculator.html
class Array alias :peek :last end stack = Array.new while true print ">> " line = gets.chomp while line.size > 0 if line =~ /^\s*([-+]?[0-9]*\.?[0-9]+)\s*/ stack.push $1.to_f elsif line =~ /^\s*([\+\-\*\/])\s*/ then operator = $1 operand_2 = stack.pop operand_1 = stack.pop stack.push case operator when '+' operand_1 + operand_2 when '-' operand_1 - operand_2 when '*' operand_1 * operand_2 when '/' operand_1 / operand_2 end end line.sub!($&, "") end puts "Top of stack = #{stack.peek}" end[...] And that is why in the lines to follow I will share my PHP solution to the RPC calculator challenge. [...]
Here’s my own version:
#!/usr/bin/env python from sys import stdout, stdin, exit stack = [] def evaluate_expression(): for token in stdin.readline()[:-1].split(" "): if token != "": if token in ["+", "-", "*", "/"]: y = stack.pop() x = stack.pop() result = { "+": lambda: x + y, "-": lambda: x - y, "*": lambda: x * y, "/": lambda: x / y }[token]() stack.append(result) else: try: stack.append(float(token)) except ValueError: print "%s ain't no number I ever heard of." % token exit(-1) return result def main(): while True: stdout.write(">>> ") stdout.write("%f\n" % evaluate_expression()) if __name__ == "__main__": main()