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.
Programming Praxis 
Haskell:
import Control.Applicative.Error import Control.Monad import Data.Map (fromList, (!)) main = getContents >>= mapM_ (print . take 1) . scanl calculate [] . lines calculate :: [Float] -> String -> [Float] calculate stack = foldl process stack . words process :: [Float] -> String -> [Float] process stack word = case maybeRead word of Just x -> x:stack Nothing -> (operators ! word) (stack !! 1) (stack !! 0) : drop 2 stack where operators = fromList [("+", (+)), ("-", (-)), ("*", (*)), ("/", (/))]I’m using problems on this site to learn haskell. Please do let me know if I could have solved this in a better way.
import Data.List (intercalate)
evaluate :: String -> Float
evaluate str = calculate (tokenize str)
tokenize :: String -> [String]
tokenize = words
calculate :: [String] -> Float
calculate exp = rpn_eval exp [0.0]
rpn_eval :: [String] -> [Float] -> Float
rpn_eval [] stack = stack!!0
rpn_eval (x:xs) stack | isOperator x = rpn_eval xs ((eval_expr x (take 2 stack)) : (drop 2 stack))
| otherwise = rpn_eval xs ((read x :: Float) : stack)
isOperator :: String -> Bool
isOperator token = token `elem` [“+”,”-“,”/”,”*”]
eval_expr :: String -> [Float] -> Float
eval_expr “+” [x,y] = x + y
eval_expr “-” [x,y] = y – x
eval_expr “*” [x,y] = x * y
eval_expr “/” [x,y] = y / x
eval_expr _ [x,y] = undefined
calculateExprs :: String -> String
calculateExprs str = intercalate “\n” (map (show . evaluate) (lines str))
main = do interact calculateExprs
A slight redesign of my previous code:
my Ocaml version.
My haskell version, similar to that of FalconNL, although a bit more verbose
parse :: String -> Either Double (Double -> Double -> Double)
parse s = maybe (Left $ read s) Right (lookup s ops)
where ops = zip ["+","-","*","/"] [(+),(-),(*),(/)]
go :: [Double] -> [String] -> [Double]
go stack [] = stack
go stack (w:ws) = case parse w of
Left x -> go (x:stack) ws
Right f -> go (apply f stack) ws
where apply f (x:y:xs) = (f x y:xs)
eval :: [[String]] -> [Double]
eval = map head . tail . scanl go []
main = getContents >>= mapM_ print . eval . map words . lines
Sorry, I didn’t follow the instruction concerning howto paste code. Here is a link to the formatted code : http://codepad.org/x3Ai1SN2
Here’s my Python solution.
def get_input_tokens(msg='> '): """get user input and return it as tokens in a list""" expression = raw_input(msg) return expression.split() def to_float(number): try: return float(number) except: return number def convert_to_expression(tokens): """convert the RPN expression to algebraic notation""" operations = ('^', '*', '/', '+', '-') num_operations = len([item for item in tokens if item in operations]) num_numbers = len(tokens) - num_operations if num_operations + 1 != num_numbers: raise ValueError, "number of operations don't correspond with numerals" # parse the RPN expression expression = '' for token in tokens[:]: if token in operations: i = tokens.index(token) if tokens[i] == '^': tokens[i] = '**' tokens = tokens[:i - 2] +\ ['(' + ' '.join([tokens[i - 2]] +\ [tokens[i]] + [tokens[i - 1]]) + ')']\ + tokens[i + 1:] return tokens[0] if __name__ == '__main__': while True: expression = raw_input('>> ') if expression == 'exit': break if expression[0] in (';', ':', '>'): import os os.system(expression[1:]) print continue expression = expression.split() try: print '=> ' + str(eval(convert_to_expression(expression[:]))) except: print 'Invalid expression.' printI bet that there’s an easier way to do this in Python. But this is what I came up with.
It’s kind of like an interactive shell. Just enter the RPN expression, and it’ll return the value.
Although the expression we’re supposed to use for testing gives me 222149.08271379699 instead of 85.2974.
I have just began learning Erlang so it is probably far from perfect :)
-module(rpn). -export([start/0]). process(Token, Stack)-> case Token of {_,_,Value} -> [Value|Stack]; {Operator,_} -> [X,Y|Tail] = Stack, case Operator of '+' -> [X+Y|Tail]; '-' -> [Y-X|Tail]; '*' -> [Y*X|Tail]; '/' -> [Y/X|Tail] end end. start() -> start([]). start(Stack) -> Line = io:get_line(">"), {ok, Tokens,_} = erl_scan:string(Line), NewStack = lists:foldl(fun process/2,Stack,Tokens), [First|_] = NewStack, io:fwrite("~w~n", [First]), start(NewStack).I’ve just been learning lisp, so I’m giving that a shot first:
(defun split-by-one-space (string)
“Returns a list of substrings of string
divided by ONE space each.
Note: Two consecutive spaces will be seen as
if there were an empty string between them.
Thanks to http://cl-cookbook.sourceforge.net/strings.html”
(loop for i = 0 then (1+ j)
as j = (position #\Space string :start i)
collect (subseq string i j)
while j))
(defun evaluate-rpn(expr)
(loop
with stack = (list)
for token in (split-by-one-space expr)
do (let ((digit (read-from-string token nil))
(*read-eval* nil)) ; By default, read-from-string will evaluate things. Boo!
(cond
((realp digit)
;;Digit is a number
(push digit stack))
(t
;; Gotta pop the two values off the stack
;; and evaluate them, what fun!
(let ((b (pop stack))
(a (pop stack)))
;; If the function is one we can parse, then go ahead and
;; evaluate it
(cond
((find digit ‘(+ – / * mod sin cos atan tan))
(push (funcall digit a b) stack))
(t (format t “Could not parse ~s~%” token)))))))
finally (return (car stack))))
;; Now loop through and actually do it
(loop
(format t “~&> “)
(force-output)
(print (evaluate-rpn (read-line))))
And my undocumented python solution:
#!/usr/bin/env python import math import operator """ Simple RPN evaluator """ operations = { "+": operator.add, "-": operator.sub, "*": operator.mul, "/": operator.div, "sin": math.sin, "cos": math.cos, } def rpn_eval(string): stack = [] for token in string.split(" "): if set(token).issubset(set("0123456789.")): stack.append(float(token)) elif token in operations: b = stack.pop() a = stack.pop() stack.append(operations[token](a, b)) else: print "Unparsable token: \"%s\"" % token return stack.pop() while True: print rpn_eval(raw_input("> "))[…] is a simple calculator that handles Reverse Polish Notation (RPN) caculations. The problem is givenhere , and my solution in Java is given […]
Ruby example:
$stack = [] def solve(ops) while (op = ops.pop) do if '+-*/'.index op raise "Not enough operands" if $stack.length < 2 a,b = $stack.pop(2) case op when '+' then $stack.push(a + b) when '-' then $stack.push(a - b) when '*' then $stack.push(a * b) when '/' then $stack.push(a / b) end else $stack.push(op.to_f) end end end loop { print "RPN > "; STDOUT.flush solve(readline.split(' ').reverse) p $stack }Example output:
RPN > 10 2 *
[20.0]
RPN > 5 +
[25.0]
RPN > 5 /
[5.0]
RPN > 3 –
[2.0]
RPN > 1
[2.0, 1.0]
RPN > +
[3.0]
RPN > 19 2.14 + 4.5 2 4.3 / – *
[3.0, 85.2974418604651]
; programming praxis exercise 1 – RPN Calculator
(defn rpn [stack value]
(let [[s1 s2] stack
v (eval (read-string value))]
(cond
(number? v) (conj stack v)
(fn? v) (conj (rest (rest stack)) (v s2 s1))
:else stack)))
(defn calc [stack line]
(let [newstack (reduce rpn stack (.split line " "))]
(println (first newstack))
newstack))
(defn rpn-repl []
(loop [stack ‘()]
(recur (calc stack (read-line)))))
A straightforward perl example with no error handling
use strict; use warnings; my @stack = (); my %operators = ( '+' => sub { $_[1] + $_[0] }, '-' => sub { $_[1] - $_[0] }, '*' => sub { $_[1] * $_[0] }, '/' => sub { $_[1] / $_[0] }, ); while (my $line = <STDIN>) { chomp $line; my @symbols = split /\s+/, $line; foreach my $s (@symbols) { if (defined $operators{$s}) { push @stack, $operators{$s}->(pop @stack, pop @stack); } else { push @stack, $s; } } if (scalar @stack != 1) { print "Error parsing expression.\n"; } else { print(pop(@stack), "\n"); } }Scheme version, worked to make adding new operations easy:
#lang racket ;; two funcs from (draga utils) ;; asss : string alist -> alist or boolean ;; as assq, but uses string=? for comparisons (define (asss str alist) (cond [(null? alist) #f] [(and (string? (caar alist)) (string=? str (caar alist))) (car alist)] [else (asss str (cdr alist))])) ;; asss/ci : string alist -> alist or boolean ;; as assq, but uses string-ci=? for comparisons (define (asss/ci str alist) (cond [(null? alist) #f] [(and (string? (caar alist)) (string-ci=? str (caar alist))) (car alist)] [else (asss str (cdr alist))])) ;; action : line stack -> stack ;; given an input line and the current stack, take the action requested and return ;; the updated stack (define (action line stack) (cond [(eof-object? line) (newline) (exit)] [(string->number line) => (lambda (n) (cons n stack))] [(asss/ci line action-list) => (lambda (a) ((cdr a) stack))] [else (display "ERROR\n") (exit #f)])) (define (rpn-top stack) (display (car stack)) (newline) stack) (define (rpn-plus stack) (cons (+ (cadr stack) (car stack)) (cddr stack))) (define (rpn-minus stack) (cons (- (cadr stack) (car stack)) (cddr stack))) (define (rpn-times stack) (cons (* (cadr stack) (car stack)) (cddr stack))) (define (rpn-divby stack) (cons (/ (cadr stack) (car stack)) (cddr stack))) (define action-list `( ( "" . ,rpn-top) ( "+" . ,rpn-plus) ( "-" . ,rpn-minus) ( "*" . ,rpn-times) ( "/" . ,rpn-divby) )) (define (rpn) (display "? ") (let ([in (current-input-port)]) (let loop ([l (read-line in)] [s '()]) (let ([new-s (action l s)]) (display "? ") (loop (read-line in) new-s))))) (rpn)Here’s another ruby version, you can see it fully commented at http://steamcode.blogspot.com/2010/07/rpn-calculator.html
class Array alias :peek :last end stack = Array.new while true print ">> " line = gets.chomp while line.size > 0 if line =~ /^\s*([-+]?[0-9]*\.?[0-9]+)\s*/ stack.push $1.to_f elsif line =~ /^\s*([\+\-\*\/])\s*/ then operator = $1 operand_2 = stack.pop operand_1 = stack.pop stack.push case operator when '+' operand_1 + operand_2 when '-' operand_1 - operand_2 when '*' operand_1 * operand_2 when '/' operand_1 / operand_2 end end line.sub!($&, "") end puts "Top of stack = #{stack.peek}" end[…] And that is why in the lines to follow I will share my PHP solution to the RPC calculator challenge. […]
Here’s my own version:
#!/usr/bin/env python from sys import stdout, stdin, exit stack = [] def evaluate_expression(): for token in stdin.readline()[:-1].split(" "): if token != "": if token in ["+", "-", "*", "/"]: y = stack.pop() x = stack.pop() result = { "+": lambda: x + y, "-": lambda: x - y, "*": lambda: x * y, "/": lambda: x / y }[token]() stack.append(result) else: try: stack.append(float(token)) except ValueError: print "%s ain't no number I ever heard of." % token exit(-1) return result def main(): while True: stdout.write(">>> ") stdout.write("%f\n" % evaluate_expression()) if __name__ == "__main__": main()A solution in F#: http://stefanoricciardi.com/2010/10/01/a-rpn-calculator-in-f/
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
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[…] This exercise comes from programming praxis. […]
[…] 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 […]
[…] 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 […]
-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]).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())); }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()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()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
#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; }#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; }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).
[…] 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 […]
<? $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]; ?>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 / - *", " "))); }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;
}
I know I’m a johnny program lately, but here is the guts of my PHP version.
#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()); }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()); }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) }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());
}
}
}
A bit late to the party, but my solution in Java is at http://ianp.org/2013/01/15/programming-praxis/
# -*- 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.
My Python solution, though Michael Wilber’s solution above, using the operator library, is better: https://gist.github.com/gmcclure/5475073
#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]
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
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); } }In Golang: http://xojoc.pw/programming-praxis/rpn-calculator.html
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 / – *”;
}