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.

About these ads

Pages: 1 2

46 Responses to “RPN Calculator”

  1. FalconNL said

    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 [("+", (+)), ("-", (-)), ("*", (*)), ("/", (/))]
    
  2. snowbeard said

    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

  3. FalconNL said

    A slight redesign of my previous code:

    import Control.Applicative.Error  
    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 = maybe (push_op (head word) stack) (:stack) $ maybeRead word
    
    push_op :: Char -> [Float] -> [Float]
    push_op op (s1:s2:ss) = (fromList (zip "+-*/" [(+),(-),(*),(/)]) ! op) s2 s1 : ss
    
  4. Paul said

    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

  5. Paul said

    Sorry, I didn’t follow the instruction concerning howto paste code. Here is a link to the formatted code : http://codepad.org/x3Ai1SN2

  6. ygd-coder said

    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.'
            print
    

    I 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.

  7. ucho said

    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).
    
  8. 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("> "))
    
  9. [...] is a simple calculator that handles Reverse Polish Notation (RPN) caculations. The problem is givenhere , and my solution in Java is given [...]

  10. Borland said

    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]

  11. gg said

    ; 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)))))

  12. ardnew said

    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");
        }
    }
    
  13. Jim Wise said

    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)                                                
    
    
  14. slabounty said

    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
    
  15. [...] And that is why in the lines to follow I will share my PHP solution to the RPC calculator challenge. [...]

  16. Bogdan Popa said

    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()
    
  17. My solution (almost ok with the constraints besides the one line thingy) in scheme (Gambit): http://github.com/AlexandreAbreu/programming-praxis-answers/blob/master/001.scm

  18. Michael Lilley said

    Ruby – bit of a hack, but fun non-the-less.

    $stack = []
    
    $ops = Hash.new { |h,k| lambda { k.to_f } }
    $ops['+'] = lambda {   $stack.pop + $stack.pop }
    $ops['-'] = lambda {  -$stack.pop + $stack.pop }
    $ops['*'] = lambda {   $stack.pop * $stack.pop }
    $ops['/'] = lambda { 1/$stack.pop * $stack.pop }
    
    loop do
      print "> "
      STDIN.gets.split(' ').each { |x| $stack.push $ops[x].() }
      puts $stack.last
    end
    
  19. [...] This exercise comes from programming praxis. [...]

  20. [...] of the earliest Programming Praxis challenges is called RPN Calculator . Our task is to write a RPN module capable of evaluating simple RPN expressions and return the [...]

  21. [...] my last article I’ve presented some solutions (scala, java, python) for the RPN Calculator exercise from Programming Praxis . Today I am going to present you the solution in Haskell [...]

  22. Matthew said
    -module(rpncalc).
    -export([init/1]).
    
    init(RPNString) ->
    	parse(string:strip(RPNString), []).
    	
    parse_strip(RPNString, Args) ->
    	parse(string:strip(RPNString), Args).
    	
    parse([], Total) ->
    	Total;
    parse([$*|RPNString], [X2, X1|Args]) ->
    	parse_strip(RPNString, [X1*X2|Args]);
    parse([$/|RPNString], [X2, X1|Args]) ->
    	parse_strip(RPNString, [X1/X2|Args]);
    parse([$+|RPNString], [X2, X1|Args]) ->
    	parse_strip(RPNString, [X1+X2|Args]);
    parse([$-|RPNString], [X2, X1|Args]) ->
    	parse_strip(RPNString, [X1-X2|Args]);
    parse(RPNString, Args) ->
    	{Arg, RPNString_1} = case string:to_float(RPNString) of
    		{error, no_float} ->
    			string:to_integer(RPNString);
    		Else ->
    			Else
    	end,
    	parse_strip(RPNString_1, [Arg|Args]).
    
  23. JScript version of the task

    var RPN = {
    	ops: {
    		'+': function(a, b) { return +a + +b; },
    		'-': function(a, b) { return a - b; },
    		'*': function(a, b) { return a * b; },
    		'/': function(a, b) { return a / b; },
    		'**': Math.pow
    	},
    	stack: [],
    	eval: function(line)
    	{
    		var tokens = line.split(/\s+/);
    		for (var i = 0; i < tokens.length; i++) {
    			var t = tokens[i];
    
    			var op = this.ops[t];
    
    			if ( ! op ) {
    				this.error(isNaN(Number(t)), 'Illegal number.');
    
    				this.stack.push(t);
    				continue;
    			}
    
    			this.error(this.stack.length  ');
    	},
    	input: function()
    	{
    		return WScript.StdIn.ReadLine();
    	},
    	alert: function(msg)
    	{
    		WScript.StdOut.WriteLine(msg.join('\n'));
    	},
    	error: function(cond, msg)
    	{
    		if ( ! cond ) {
    			return;
    		}
    		throw new Error(msg);
    	},
    	quit: function()
    	{
    		WScript.Quit();
    	}
    };
    
    while ( true ) {
    	RPN.prompt();
    	RPN.alert(RPN.eval(RPN.input()));
    }
    
  24. ftt said

    My Python version is somewhat clumsy.

    #!/usr/bin/env python
    
    
    import operator
    import sys
    from numbers import Number
    
    
    _OPERATORS = {
        '+': operator.add,
        '-': operator.sub,
        '*': operator.mul,
        '/': operator.div
    }
    
    class ParseException(Exception):
        pass
    
    def _to_number(string):
        '''Accepts a string or and returns a number represented by that string.
        If a number is passed, that number is returned intact.'''
        if isinstance(string, Number):
            return string
        try:
            return int(string)
        except ValueError:
            return float(string)
    
    
    def _calculate(stack):
        '''Takes a list representing an expression stack and solves the first expression found.
        Changes the list in place.'''
        op = None
        for op_index in xrange(len(stack)):
            if stack[op_index] in _OPERATORS.keys():
                op = stack[op_index]
                break
        if op is None or op_index < 2:
            return
        left_operand, right_operand = stack[op_index - 2:op_index]
        try:
            left_operand = _to_number(left_operand)
            right_operand = _to_number(right_operand)
        except ValueError:
            raise ParseException('Unknown numbers')
        stack[op_index - 2] = _OPERATORS[op](left_operand, right_operand)
        stack[op_index - 1:] = stack[op_index + 1:]
    
    
    def main():
        stack = []
        print 'RPN calculator. Enter an empty line to quit.'
        while True:
            user_input = sys.stdin.readline().split()
            if not user_input:
                return
            stack.extend(user_input)
            old_len = len(stack)
            while True:
                try:
                    _calculate(stack)
                except ParseException as e:
                    print '{0}\nStack is cleared.'.format(e.message)
                    stack = []
                    break
                if len(stack) == old_len:
                    break
                old_len = len(stack)
            print '> {0}'.format(' '.join(str(n) for n in stack))
    
    
    if __name__ == '__main__':
        main()
    
  25. dmitru said
    def rpn(expr):
        st = []
        for term in expr.split():
            if term in ('+', '-', '*', '/', '%'):
                op1 = st.pop()
                op2 = st.pop()
                res = eval('%f %s %f' % (op2, term, op1))
                st.append(res)
            else:
                st.append(float(term))
        return st[0]
    
    def main():
        while True:
            s = input('RPN> ')
            if s in ('quit', 'exit'):
                exit()
            if not s:
                continue
            print(' ' * 4, end='')
            try:
                print(rpn(s))
            except ZeroDivisionError:
                print('Error: division by zero.')
            except (IndexError, ValueError):
                print('Error: the expression isn\'t correct.')
           
    if __name__ == '__main__':
        main()
    
  26. mlieb said

    Here’s how I solved it with Python. There’s not any error handling, but it’s a single purpose program so I didn’t really think it was necessary.

    operators = ‘+-/*’

    def get_input():
    input = raw_input(“input: “)
    return input

    def number(num):
    if ‘.’ in num:
    return float(num)
    elif num not in operators:
    return int(num)

    def parse_input(text):
    text = text.split()
    stack = []
    for x in text:
    if x.isdigit() or number(x):
    stack.insert(0, number(x))
    elif x in operators:
    stack.insert(0, operate(stack, x))
    return stack

    def operate(nums, operator):
    b = nums.pop(0)
    a = nums.pop(0)
    if operator == ‘+':
    return a + b
    elif operator == ‘-‘:
    return a – b
    elif operator == ‘/':
    return a / b
    else: return a * b

    if __name__ == ‘__main__':
    answer = parse_input(‘get_input’)[0]
    print answer

  27. #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    const int MAX_LINE = 1024;
    const int MAX_STACK = 1024;
    const int MAX_OP = 10;
    
    double stack[MAX_STACK];
    int stack_ptr = 0;
    
    void push_stack(double x)
    {
        stack[stack_ptr++] = x;
    }
    
    double pop_stack()
    {
        return stack[--stack_ptr];
    }
    
    double calculate(char* expr)
    {
        char op[MAX_OP];
        char *expr_ptr = expr;
    
        while (sscanf(expr_ptr, "%s", op) == 1)
        {
            expr_ptr += strlen(op) + 1;
    
            // Is operand?
            if ((strlen(op) == 1) && (op[0] == '+' || op[0] == '-' || op[0] == '*' || op[0] == '/'))
            {
                double y = pop_stack();
                double x = pop_stack();
    
                switch(op[0])
                {
                case '+': push_stack(x + y); break;
                case '-': push_stack(x - y); break;
                case '*': push_stack(x * y); break;
                case '/': push_stack(x / y); break;
                default: break;
                }
            } 
            else 
            {
                push_stack(atof(op));
            }
        }
    
        return pop_stack();
    }
    
    int main()
    {
        char line[MAX_LINE];
    
        fgets(line, MAX_LINE, stdin);
    
        printf("%.4f\n", calculate(line));
    
        getchar();
        return 0;
    }
    
  28. iodiot said
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    const int MAX_LINE = 1024;
    const int MAX_STACK = 1024;
    const int MAX_OP = 10;
    
    double stack[MAX_STACK];
    int stack_ptr = 0;
    
    void push_stack(double x)
    {
    	stack[stack_ptr++] = x;
    }
    
    double pop_stack()
    {
    	return stack[--stack_ptr];
    }
    
    double calculate(char* expr)
    {
    	char op[MAX_OP];
    	char *expr_ptr = expr;
    
    	while (sscanf(expr_ptr, "%s", op) == 1)
    	{
    		expr_ptr += strlen(op) + 1;
    
    		// Is operand?
    		if ((strlen(op) == 1) && (op[0] == '+' || op[0] == '-' || op[0] == '*' || op[0] == '/'))
    		{
    			double y = pop_stack();
    			double x = pop_stack();
    
    			switch(op[0])
    			{
    			case '+': push_stack(x + y); break;
    			case '-': push_stack(x - y); break;
    			case '*': push_stack(x * y); break;
    			case '/': push_stack(x / y); break;
    			default: break;
    			}
    		} 
    		else 
    		{
    			push_stack(atof(op));
    		}
    	}
    
    	return pop_stack();
    }
    
    int main()
    {
    	char line[MAX_LINE];
    
    	fgets(line, MAX_LINE, stdin);
    
    	printf("%.4f\n", calculate(line));
    
    	getchar();
    	return 0;
    }
    
  29. https://github.com/gcapell/ProgrammingPraxis/blob/master/01_rpn_calculator/RPN.go

    Not sure about keeping operators as a map->function (it might be cleaner/simpler just to have a switch).

  30. [...] zadanie to prosty kalkulator do wykonywania podstawowych operacji przy użyciu tzw. odwróconej notacji polskie…, która znakomicie sprawdza się przy traktowaniu danych wejściowych jako stosu (operator [...]

  31. Manoj Senguttuvan said
    <?
    $input=explode(' ',trim(fgets(STDIN)));
    $arr=array();
    for($i=0;$i<count($input);$i++)
    {
            if($input[$i]=='+'||$input[$i]=='-'||$input[$i]=='*'||$input[$i]=='/')
            {
                    $var1=array_pop($arr);
                    $var2=array_pop($arr);
                    if($input[$i]=='+')
                            array_push($arr,$var1+$var2);
                    else if($input[$i]=='-')
                            array_push($arr,$var2-$var1);
                    else if($input[$i]=='*')
                            array_push($arr,$var1*$var2);
                    else
                            array_push($arr,$var2/$var1);
            }
            else
                    array_push($arr,$input[$i]);
    }
    echo $arr[0];
    ?>
    
  32. j0sejuan said

    Golang

    package main
    
    import (
    	"fmt"
    	"strings"
    	"strconv"
    )
    
    type operator func (float64, float64) float64
    
    func rpn(input [] string) float64 {
    	o := map [string] operator {
    		"+": func (a float64, b float64) float64 { return a + b },
    		"-": func (a float64, b float64) float64 { return a - b },
    		"*": func (a float64, b float64) float64 { return a * b },
    		"/": func (a float64, b float64) float64 { return a / b },
    	}
    	i, s := 0, make([] float64, 1000)
    	for _, v := range input {
    		x, e := strconv.ParseFloat(v, 64)
    		if e == nil {
    			s[i] = x
    			i += 1
    		} else {
    			s[i - 2] = o[v](s[i - 2], s[i - 1])
    			i -= 1
    		}
    	}
    	return s[i - 1]
    }
    
    func main() {
    	fmt.Println(rpn(strings.Split("19 2.14 + 4.5 2 4.3 / - *", " ")));
    }
    
  33. Ameya Joshi said

    Here is my C++ solution:

    /*
    * rpn.cpp
    *
    * Created on: Jun 13, 2012
    * Author: amejo
    */

    #include “Stack.h”
    #include
    #include
    #include
    #include

    using namespace std;

    /*Cal function will calulate the answer based on the operands */
    float cal(float a,float b,char op){
    float ans=0;

    switch(op){

    case ‘+': ans = a+b;
    break;

    case ‘*': ans = a*b;
    break;

    case ‘/': ans = a/b;
    break;

    case ‘-‘: ans = a-b;
    break;

    case ‘^':{ans = 1;
    for(int i=1;i<=b;i++)
    ans *= a;
    }
    break;

    default: ans = 0.0;
    break;

    }

    return ans;

    }

    bool not_space(char c){
    return(!isspace(c));
    }

    bool space(char c){
    return(isspace(c));
    }
    /* Splitter will split the string based on spaces and pushed in the string array */
    void splitter(string s,vector &str){

    string::iterator i=s.begin();
    string::iterator j;

    while(i!=s.end()){
    //the below statement will find a character which is not space
    i=find_if(i,s.end(),not_space);
    //this will find the space character
    j = find_if(i,s.end(),space);

    if(i!=s.end()){

    //using string constructor , word (i,j) is formed
    str.push_back(string(i,j));
    }
    i=j;
    }

    return;
    }

    float rpncalculate(Stack &s,string expr){
    /*Loop till the end of the string vector*/
    vector str;
    /* split the string into different strings */
    splitter(expr,str);
    string::iterator iter;
    vector::iterator it=str.begin();
    float op1,op2;//two operands
    float res,ad;//ad will temp hold the operand

    while(it!=str.end()){
    /* Check if its an operand or an operator, if an operand push it in the stack
    * for that another iterator is used to scan through the strings only 1st character needs
    * to be checked if its digit or not*/
    iter = (*it).begin();

    /* if its digit then using istringstream the float value is read from the string and pushed
    * into the stack
    */
    if(isdigit(*iter)){
    istringstream in (*it,ios::in);
    in >> ad;
    s.push(ad);
    }
    else{
    /*If it is an operator , pop the two operands from the stack , perform the operation and put the result in the
    * stack , in the end only the final result will remain */

    op2 = s.pop();
    op1 = s.pop();
    //cout <<"op1= "<<op1<<" op2= "<<op2<<" operator= "<<*it<<endl;
    res = cal(op1,op2,*iter);

    s.push(res);

    }
    iter = (*it).end();
    it++;
    }

    return s.pop();

    }

    int main(){
    cout <<"Enter an expression to be evaluated"<<endl;
    string str;
    getline(cin,str);
    Stack st;

    float ans = rpncalculate(st,str);

    cout << "ans = "<<ans;

    return 0;

    }

  34. Jeff Cope said

    I know I’m a johnny program lately, but here is the guts of my PHP version.

  35. tomtech999 said
    #include <functional>
    #include <map>
    #include <vector>
    #include <algorithm>
    #include <stack>
    
    void main(int argc, char* argv[])
    {
    	if(argc == 1)
    		return;
    	std::vector<std::string> terms(argv + 1, argv + argc);
    
    	std::map<char, std::function<double(double,double)>> op;
    	op.insert(std::make_pair('+', [](double a, double b) { return a + b; }));
    	op.insert(std::make_pair('-', [](double a, double b) { return a - b; }));
    	op.insert(std::make_pair('*', [](double a, double b) { return a * b; }));
    	op.insert(std::make_pair('/', [](double a, double b) { return a / b; }));
    
    	static std::stack<double> st;
    	std::for_each(terms.begin(), terms.end(), [&](const std::string& s)
    	{
    		double val = atof(s.c_str());
    		if(op.find(s[0]) != op.end() && !val)
    		{
    			double a = st.top(); st.pop();
    			double b = st.top(); st.pop();
    			st.push(op[s[0]](b, a)); return;
    		}
    		st.push(val);
    	});
    	printf("%f.3", st.top());
    }
    
  36. tomtech999 said

    Update…

    #include <functional>
    #include <map>
    #include <vector>
    #include <algorithm>
    #include <stack>
    
    void main(int argc, char* argv[])
    {
    	if(argc == 1) return;
    
    	std::map<char, std::function<double(double,double)>> op;
    	op.insert(std::make_pair('+', [](double a, double b) { return a + b; }));
    	op.insert(std::make_pair('-', [](double a, double b) { return a - b; }));
    	op.insert(std::make_pair('*', [](double a, double b) { return a * b; }));
    	op.insert(std::make_pair('/', [](double a, double b) { return a / b; }));
    
    	std::stack<double> st;
    	std::for_each(argv + 1, argv + argc, [&](const char* s)
    	{
    		if(op.find(s[0]) != op.end() && st.size() >= 2)
    		{
    			double a = st.top(); st.pop();
    			double b = st.top(); st.pop();
    			st.push(op[s[0]](b, a)); return;
    		}
    		double val = atof(s);
    		if(val) st.push(val);
    	});
    
    	if(st.size()) printf("%f", st.top());
    }
    
  37. package main

    import (
    "fmt"
    "strings"
    "strconv"
    )

    type Node struct{
    value float64
    next *Node
    }

    type Stack struct{
    top *Node
    }

    func (stack *Stack) push(node *Node){
    if stack.top==nil{
    stack.top=node
    }else{
    node.next=stack.top
    stack.top=node
    }
    }

    func (stack *Stack) pop() *Node{
    if stack.top==nil{
    return nil
    }

    node:=stack.top
    stack.top=node.next
    return node
    }

    func operate(operator string,stack *Stack){
    node1:=stack.pop()
    node2:=stack.pop()
    switch operator{
    case "+":
    stack.push(&Node{node2.value + node1.value,nil})
    case "-":
    stack.push(&Node{node2.value – node1.value,nil})
    case "*":
    stack.push(&Node{node2.value * node1.value,nil})
    case "/":
    stack.push(&Node{node2.value / node1.value,nil})
    }
    }

    func main(){
    str:="19 2.14 + 4.5 2 4.3 / – *"
    tokStr:=strings.Fields(str)

    stack:=Stack{nil}
    for _,v:=range tokStr{
    num,err:=strconv.ParseFloat(v,64)
    if err==nil{
    stack.push(&Node{num,nil})
    }else{
    operate(v,&stack)
    }
    }
    fmt.Println(stack.top.value)
    }

  38. SimpsOff said

    Java Solution:

    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.LinkedList;

    public class Main {

    public static void main(String[] args) {

    LinkedList operands = new LinkedList();

    String acceptedOperators = “+-*/”;

    try {

    BufferedReader rdr = new BufferedReader(new InputStreamReader(
    System.in));
    String inCalcs = rdr.readLine();
    String[] inTokens = inCalcs.split(” “);

    for (String string : inTokens) {
    // try and parse the number and add to operands.
    try {
    Double operand = Double.parseDouble(string);
    operands.push(operand);
    }
    // not a double, try and add it to operators…
    catch (NumberFormatException e) {
    // if string is one character, and is an accepted operator.
    if (string.length() == 1
    && acceptedOperators.contains(string)) {
    Double op2 = operands.pop();
    Double op1 = operands.pop();

    switch (string) {
    case “+”:
    operands.push(op1 + op2);
    break;
    case “-“:
    operands.push(op1 – op2);
    break;
    case “*”:
    operands.push(op1 * op2);
    break;
    case “/”:
    operands.push(op1 / op2);
    break;
    default:
    break;
    }
    System.out.format(“%s %s %s operandQueue: %s\r\n”, op1,
    op2, string, operands);
    }
    }
    // do nothing.
    catch (NullPointerException e) {
    }
    }

    } catch (IOException e) {
    System.out.println(e.toString());
    }
    }
    }

  39. A bit late to the party, but my solution in Java is at http://ianp.org/2013/01/15/programming-praxis/

  40. bar@bar.com said

    # -*- coding: utf-8 -*-

    from __future__ import division

    class Stack(object):
    OPERATORS = {“+” : (lambda x, y : x+y),
    “-” : (lambda x, y : x-y),
    “/” : (lambda x, y : x/y),
    “*” : (lambda x, y : x*y),
    }

    def __init__(self, top=None, value=None):
    self.top = top
    self.x = value
    self.y = None
    self.value = None

    @staticmethod
    def is_num(value):
    try:
    float(value)
    return True
    except ValueError:
    return False

    def push(self, value):
    if self.is_num(value):
    value = float(value)
    if self.x is None:
    self.x = value
    elif self.y is None:
    self.y = value
    else:
    if not isinstance(self.y, Stack):
    self.y = Stack(self, self.y)

    self.y.push(value)

    elif value in self.OPERATORS:
    if isinstance(self.y, Stack):
    self.y.push(value)
    else:
    self.evaluate(value)

    def evaluate(self, operator):
    self.value = self.OPERATORS[operator](self.x, self.y)
    if self.top:
    self.top.pop()
    else:
    self.x = self.value
    self.y = None

    def pop(self):
    self.y = self.y.value

    def __repr__(self):
    def strify(obj):
    return str(obj) if obj is not None else ‘EMPTY’
    return “” %(strify(self.x), strify(self.y))

    if __name__ == “__main__”:
    calc = Stack()
    commands = “19 2.14 + 4.5 2 4.3 / – *”.split()
    for c in commands:
    calc.push(c)
    print calc

    print calc.value

    python 2.7 with simulating stacks for RPN.

  41. G McClure said

    My Python solution, though Michael Wilber’s solution above, using the operator library, is better: https://gist.github.com/gmcclure/5475073

  42. Meenakshi said

    #Programming Praxis – RPN Calculator
    #Solution by Meenakshi Madan

    operators = “+-/%*”
    exp_stack = []

    def is_number(s):
    try:
    float(s)
    return True
    except ValueError:
    return False

    exp = raw_input(“Enter the expression to be calculated\n”).split(‘ ‘)

    for term in exp:
    if is_number(term):
    exp_stack.append(term)
    elif term in operators:
    try:
    op2 = exp_stack.pop()
    op1 = exp_stack.pop()
    exp_stack.append(eval(str(op1) + term + str(op2)))
    except:
    print “Not enough operands. Please check your expression.”
    exit()
    else:
    print “Invalid operators. Please check your expression.”
    exit()

    print exp_stack[0]

  43. Andri Juanda said

    Just join CS class in Udacity.com so my understanding about phyton is very limited, but here is my solution:

    def RPN(string):
    string = string.split()
    operated = []
    index0 = 0 – len(string)

    while index0 < 0:
    if string[index0] == '+':
    operated[-2] += operated[-1]
    operated.pop()
    elif string[index0] == '-':
    operated[-2] -= operated[-1]
    operated.pop()
    elif string[index0] == '*':
    operated[-2] *= operated[-1]
    operated.pop()
    elif string[index0] == '/':
    operated[-2] /= operated[-1]
    operated.pop()
    else:
    # Should have a try block here and
    # return error if this next line fail
    operated.append(float(string[index0]))
    index0 += 1
    return operated[0]

    not sure why operated[-2]+= operated.pop() won't work and I haven't study try block

  44. Colin Williams said

    java:

    import java.util.*;
    import java.io.*;
    
    class RPN {
    	public static void main(String[] args) throws IOException {
    		RPN rpn = new RPN();
    		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    		String line;
    		while ((line = in.readLine()) != null) {
    			line = line.trim();
    			double result = rpn.calc(line);
    			System.out.println(Double.toString(result));
    		}
    	}
    
    	public double calc(String expression) {
    		Stack<Token> operands = operands(expression);
    		return operands.pop().calculate(operands);
    	}
    
    	private Stack<Token> operands(String expression) {
    		Stack<Token> operands = new Stack<Token>();
    
    		for (String token : expression.split(" ")) {
    			operands.push(build_token(token));
    		}
    
    		return operands;
    	}
    
    	public Token build_token(String descriptor) {
    		Token t;
    		switch (descriptor) {
    		case "+": t = new Addition();
    			break;
    		case "-": t = new Subtraction();
    			break;
    		case "*": t = new Multiplication();
    			break;
    		case "/": t = new Division();
    			break;
    		default: t = new Number(descriptor);
    			break;
    		}
    		return t;
    	}
    }
    
    abstract class Token {
    	abstract public double calculate(Stack<Token> operands);
    
    	public boolean isOperator() {
    		return false;
    	}
    }
    
    abstract class Operator extends Token {
    	public double calculate(Stack<Token> operands) {
    		double second = operands.pop().calculate(operands);
    		double first = operands.pop().calculate(operands);;
    		return calculate(first, second);
    	}
    
    	abstract protected double calculate(double first, double second);
    
    	public boolean isOperator() {
    		return true;
    	}
    }
    
    class Addition extends Operator {
    	protected double calculate(double first, double second) {
    		return first + second;
    	}
    }
    
    class Subtraction extends Operator {
    	protected double calculate(double first, double second) {
    		return first - second;
    	}
    }
    
    class Multiplication extends Operator {
    	protected double calculate(double first, double second) {
    		return first * second;
    	}
    }
    
    class Division extends Operator {
    	protected double calculate(double first, double second) {
    		return first / second;
    	}
    }
    
    class Number extends Token {
    	private String value;
    	public Number(String value) {
    		super();
    		this.value = value;
    	}
    
    	public double calculate(Stack<Token> operands) {
    		return Double.parseDouble(value);
    	}
    }

    jUnit tests:

    import static org.junit.Assert.*;
    import org.junit.Test;
    
    public class RPNTest {
    	@Test
    	public void SingleNumber() {
    		RPN rpn = new RPN();
    		assertEquals(0, rpn.calc("0"), 0.1);
    		assertEquals(1, rpn.calc("1"), 0.1);
    	}
    
    	@Test
    	public void Addition() {
    		RPN rpn = new RPN();
    		assertEquals(0, rpn.calc("0 0 +"), 0.1);
    		assertEquals(1, rpn.calc("0 1 +"), 0.1);
    	}
    
    	@Test
    	public void Subtraction() {
    		RPN rpn = new RPN();
    		assertEquals(0, rpn.calc("0 0 -"), 0.1);
    		assertEquals(1, rpn.calc("1 0 -"), 0.1);
    		assertEquals(1, rpn.calc("2 1 -"), 0.1);
    	}
    
    	@Test
    	public void Multiplication() {
    		RPN rpn = new RPN();
    		assertEquals(0, rpn.calc("0 1 *"), 0.1);
    	}
    
    	@Test
    	public void Division() {
    		RPN rpn = new RPN();
    		assertEquals(2, rpn.calc("4 2 /"), 0.1);
    	}
    
    	@Test
    	public void Composite() {
    		RPN rpn = new RPN();
    		assertEquals(5, rpn.calc("1 2 2 + +"), 0.1);
    		assertEquals(85.2974, rpn.calc("19 2.14 + 4.5 2 4.3 / - *"), 0.0001);
    	}
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 630 other followers

%d bloggers like this: