## RPN Calculator

### February 19, 2009

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.

Pages: 1 2

### 48 Responses to “RPN Calculator”

1. FalconNL said

```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 = 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:]

if __name__ == '__main__':
while True:
expression = raw_input('>> ')
if expression == 'exit':
break
if expression 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))
(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)

And my undocumented python solution:

```#!/usr/bin/env python

import math
import operator
""" Simple RPN evaluator """

operations = {
"-": 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
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
(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 ‘()]

12. ardnew said

A straightforward perl example with no error handling

```use strict;
use warnings;

my @stack = ();
my %operators = (
'+' => sub { \$_ + \$_ },
'-' => sub { \$_ - \$_ },
'*' => sub { \$_ * \$_ },
'/' => sub { \$_ / \$_ },
);

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)])
[s '()])
(let ([new-s (action l s)])
(display "? ")

(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():
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()
{
},
{
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();
}
```
24. ftt said

My Python version is somewhat clumsy.

```#!/usr/bin/env python

import operator
import sys
from numbers import Number

_OPERATORS = {
'-': 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:
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

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__’:

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 == '+' || op == '-' || op == '*' || op == '/'))
{
double y = pop_stack();
double x = pop_stack();

switch(op)
{
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 == '+' || op == '-' || op == '*' || op == '/'))
{
double y = pop_stack();
double x = pop_stack();

switch(op)
{
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;
?>
```
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

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);
}
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) != op.end() && !val)
{
double a = st.top(); st.pop();
double b = st.top(); st.pop();
st.push(op[s](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) != op.end() && st.size() >= 2)
{
double a = st.top(); st.pop();
double b = st.top(); st.pop();
st.push(op[s](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.IOException;

public class Main {

public static void main(String[] args) {

String acceptedOperators = “+-*/”;

try {

System.in));
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

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:
exit()
else:
exit()

print exp_stack

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

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

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
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);
}
}```
45. George Leake said

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

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

}