Programming Praxis

RPN Calculator

February 19, 2009 3:05 PM

The only difficulty is handling the newline, which the Scheme reader treats as whitespace. The (op token) function converts token from a symbol returned by the reader to an operator that can be used to perform arithmetic. The format of the first line of the program is specific to Chez Scheme, but most Scheme systems provide something similar.

#! /usr/bin/scheme –script (define (next) (cond ((eof-object? (peek-char)) (exit)) ((char=? (peek-char) #\space) (read-char) (next)) ((char=? (peek-char) #\newline) (read-char) ‘nl) (else (read))))

(define (op token) (case token ((+) +) ((-) -) ((*) *) ((/) /)))

(let rpn ((token (next)) (stack ‘())) (cond ((eq? ‘nl token) (display (car stack)) (newline) (rpn (next) (cdr stack))) ((number? token) (rpn (next) (cons token stack))) (else (rpn (next) (cons ((op token) (cadr stack) (car stack)) (cddr stack))))))

Although it can’t be run, this program is available as a paste at http://programmingpraxis.codepad.org/fjzlC50x. This exercise was inspired by a web page of Fredrik Arnerup at http://www.stacken.kth.se/~foo/rpn.

Posted by programmingpraxis

Categories: Exercises

Tags:

Newer »

48 Responses to “RPN Calculator”

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

By FalconNL on March 11, 2009 at 12:39 AM

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

By snowbeard on April 6, 2009 at 3:48 PM

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

By FalconNL on April 6, 2009 at 9:56 PM

my Ocaml version.

By ksson on June 19, 2009 at 8:42 PM
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

By Paul on July 31, 2009 at 5:00 PM
Sorry, I didn’t follow the instruction concerning howto paste code. Here is a link to the formatted code : http://codepad.org/x3Ai1SN2

By Paul on July 31, 2009 at 5:04 PM

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.

By ygd-coder on August 13, 2009 at 6:16 PM

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

By ucho on August 13, 2009 at 7:28 PM

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("> "))
```
By Michael Wilber on August 14, 2009 at 6:06 AM
[…] is a simple calculator that handles Reverse Polish Notation (RPN) caculations. The problem is givenhere , and my solution in Java is given […]

By Codenumb » Blog Archive » Programming Praxis – RPN Calculator on September 5, 2009 at 11:02 PM

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]

By Borland on October 18, 2009 at 1:58 PM

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

By gg on November 8, 2009 at 9:14 PM

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

By ardnew on June 1, 2010 at 8:25 PM

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)

By Jim Wise on June 15, 2010 at 7:06 PM

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

By slabounty on July 9, 2010 at 10:28 PM

[…] And that is why in the lines to follow I will share my PHP solution to the RPC calculator challenge. […]

By RPN Calculator in PHP on July 30, 2010 at 1:19 AM

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

By Bogdan Popa on August 18, 2010 at 8:30 AM

A solution in F#: http://stefanoricciardi.com/2010/10/01/a-rpn-calculator-in-f/

By Stefano Ricciardi on October 1, 2010 at 12:59 PM
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

By Alexandre Abreu on October 12, 2010 at 4:20 PM

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

By Michael Lilley on November 19, 2010 at 5:09 PM

[…] This exercise comes from programming praxis. […]

By my RPN calculator « e^{pi i} + 1 = 0 on December 15, 2010 at 1:31 AM
[…] 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 […]

By RPN Calculator (using Scala, python and Java) « andreINC.net on January 3, 2011 at 10:39 PM
[…] 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 […]

By RPN Calculator (using Haskell) « andreINC.net on January 12, 2011 at 12:00 AM

-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]).

By Matthew on January 12, 2011 at 2:02 AM

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

By with-love-from-siberia on January 18, 2011 at 7:00 PM

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

By ftt on June 19, 2011 at 9:28 AM

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

By dmitru on August 12, 2011 at 7:30 PM

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

By mlieb on September 29, 2011 at 5:03 AM

#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;
}

By Ignat Grob (@iodiot) on October 24, 2011 at 1:57 PM

#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;
}

By iodiot on October 24, 2011 at 2:03 PM

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

By gary capell on February 11, 2012 at 9:48 AM
[…] 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 […]

By Na dobry początek… » Maksymilian Węcławski on February 20, 2012 at 2:32 PM

<?
$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];
?>

By Manoj Senguttuvan on February 26, 2012 at 6:33 AM

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 / - *", " ")));
}

By j0sejuan on April 7, 2012 at 4:52 PM

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;

}

By Ameya Joshi on June 16, 2012 at 2:33 AM
I know I’m a johnny program lately, but here is the guts of my PHP version.

By Jeff Cope on September 12, 2012 at 3:49 AM

#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());
}

By tomtech999 on September 27, 2012 at 6:18 PM

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

By tomtech999 on October 7, 2012 at 8:13 PM

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

By Kapil Ratnani (@kapilratnani) on December 17, 2012 at 5:32 PM

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

By SimpsOff on January 6, 2013 at 7:33 PM
A bit late to the party, but my solution in Java is at http://ianp.org/2013/01/15/programming-praxis/

By Ian Phillips on January 15, 2013 at 1:55 PM
# -*- 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.

By bar@bar.com on April 24, 2013 at 7:52 PM
My Python solution, though Michael Wilber’s solution above, using the operator library, is better: https://gist.github.com/gmcclure/5475073

By G McClure on April 27, 2013 at 11:12 PM
#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]

By Meenakshi on May 31, 2013 at 3:02 PM
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

By Andri Juanda on June 5, 2013 at 11:25 AM

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

By Colin Williams on July 18, 2013 at 2:01 AM

In Golang: http://xojoc.pw/programming-praxis/rpn-calculator.html

By xojoc on January 28, 2015 at 4:21 PM

using System;
using System.Collections.Generic;

namespace RPN
{
internal class Program
{
private static Stack stack = new Stack();
private static string data = “19 2.14 + 4.5 2 4.3 / – *”;

    private static void Main(string[] args)
    {
        string[] s = data.Split(' ');
        double result = Process(s);
        Console.WriteLine("\nInput string: {0}, \nResult = {1}", data, result);
        Console.ReadKey();
    }

    private static double Process(string[] str)
    {           
        foreach (string s in str)
        {
            if (!IsOperator(s))
                stack.Push(s);      //is value
            else                        // is operator
            {   
                string val = Execute(s);
                stack.Push(val);
            }
        }
        return double.Parse(stack.Pop());
    }

    private static string Execute(string s)
    {
        double v2 = double.Parse(stack.Pop()); //last arg
        double v1 = double.Parse(stack.Pop());

        double result = 0;

        switch (s)
        {
            case "+":
                result = v1 + v2;
                break;

            case "-":
                result = v1 - v2;
                break;

            case "*":
                result = v1 * v2;
                break;

            case "/":
                result = v1 / v2;
                break;
            default:
                break;
        }
        return result.ToString();
    }

    private static bool IsOperator(string s)
    {
        string operators = "+-/*";
        return operators.Contains(s);
    }
}

}

By George Leake on October 31, 2017 at 9:18 AM

Mobile Site | Full Site

Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.

Programming Praxis

RPN Calculator

Share this:

Related

48 Responses to “RPN Calculator”

Leave a Reply