Skip to content

Instantly share code, notes, and snippets.

@cky
Created March 15, 2011 19:41
Show Gist options
  • Save cky/871303 to your computer and use it in GitHub Desktop.
Save cky/871303 to your computer and use it in GitHub Desktop.
RPN calculators in various languages
;; Source: http://codegolf.stackexchange.com/q/222/3
(let loop ((stack '()))
(let ((token (read)))
(cond ((number? token) (loop `(,token ,@stack)))
((assq token `((+ ,+) (- ,-) (* ,*) (/ ,/)))
=> (lambda (ass) (loop `(,((cadr ass) (cadr stack) (car stack))
,@(cddr stack)))))
(else (car stack)))))
// Source: http://stackoverflow.com/q/746653/13
#include <complex>
#include <iostream>
#include <map>
#include <stack>
#include <stdexcept>
#include <string>
namespace {
using std::cin; using std::complex; using std::cout;
using std::invalid_argument; using std::map; using std::stack;
using std::string; using std::underflow_error;
typedef complex<double> complexd;
typedef complexd& (complexd::*complexd_pmf)(complexd const&);
typedef map<char, complexd_pmf> opmap;
template <typename T>
typename T::reference top(T& st) {
if (st.empty())
throw underflow_error("Empty stack");
return st.top();
}
}
int
main()
{
opmap const ops{{'+', &complexd::operator+=},
{'-', &complexd::operator-=},
{'*', &complexd::operator*=},
{'/', &complexd::operator/=}};
char op;
complexd val;
stack<complexd> st;
while (cin >> op) {
opmap::const_iterator opit(ops.find(op));
if (opit != ops.end()) {
complexd rhs(top(st));
st.pop();
complexd& lhs(top(st));
(lhs.*opit->second)(rhs);
cout << lhs << '\n';
} else if (cin.unget() && cin >> val) {
st.push(val);
} else {
throw invalid_argument(string("Unknown operator ") += op);
}
}
}
;;; rpn.lisp---basic RPN calculator
;;; Copyright (c) 2009 Chris K. Jester-Young; GPLv3+
(defmacro defop (ht arity &rest syms)
`(psetf ,@(mapcan
(lambda (sym) `((gethash ',sym ,ht) `(,#',sym ,@,arity)))
syms)))
(defmacro defalias (ht arity &rest aliases)
`(psetf ,@(mapcan
(lambda (alias)
`((gethash ',(car alias) ,ht) `(,#',(cadr alias) ,@,arity)))
aliases)))
;; Define some operators to make available
(defvar *optab* (make-hash-table))
(defop *optab* 2 + - * / mod rem ash expt cis)
(defalias *optab* 2 (** expt) (atan2 atan))
(defop *optab* 1 exp log sqrt sin cos tan asin acos atan)
; Here, have some hyperbolic versions too
(defop *optab* 1 sinh cosh tanh asinh acosh atanh)
(defvar *stack* nil)
(defun pushall (&rest args)
(dolist (arg args)
(push arg *stack*)))
(defun dump ()
(pprint *stack*))
; Special functions (note QUIT is not portable)
(defop *optab* 0 quit dump values)
(defalias *optab* 0 (q quit) (exit quit))
;; Scheme-like READ function that doesn't throw a hissy fit
;; when EOF is encountered.
(defun scheme-read ()
(read *standard-input* nil))
(do ((token (scheme-read) (scheme-read)))
((null token))
(if (numberp token) (pushall token)
(multiple-value-bind (val p)
(gethash token *optab*)
(if p (let ((fun (car val))
(arity (cdr val))
args)
(dotimes (_ arity)
(push (pop *stack*) args))
(multiple-value-call #'pushall (apply fun args))
(unless (null *stack*) (format t "~A~%" (car *stack*))))
(warn "Token unrecognised: ~A" token)))))
require 'dl/import'
module LibM
extend DL::Importer rescue extend DL::Importable
dlload 'libm.so'
extern 'double cbrt(double)'
extern 'double fma(double, double, double)'
end
module Enumerable
def map_into_hash &block
Hash[*zip(map(&block)).flatten(1)]
end
end
class UnboundMethod
def call this, *args
bind(this).call(*args)
end
def bound_arity
arity + 1
end
end
class Stack < Array
def pop n
raise ArgumentError, "Stack underflow" if n > size
super
end
def push x
case x
when NilClass
# nothing
when FalseClass
super 0.0
when TrueClass
super 1.0
when Array
super *x.map(&:to_f)
else
super x.to_f
end
end
def dispatch op
case op
when :dump
puts join(' ')
when :clear
clear
else
arity = op.bound_arity rescue op.arity
push op.call(*pop(arity))
end
end
end
class Evaluator
OPMAP = Math.methods(false).map(&:to_sym).map_into_hash(&Math.method(:method)).merge(
Float.instance_methods(false).map(&:to_sym).map_into_hash(&Float.method(:instance_method)))
# methods created by DL do not have arity; make our own wrappers
OPMAP[:cbrt] = lambda {|x| LibM.cbrt x}
OPMAP[:fma] = lambda {|x, y, z| LibM.fma x, y, z}
# auxiliary operations
OPMAP[:"?"] = lambda {|| puts OPMAP.keys.sort.join(' ')}
OPMAP[:q] = lambda {|| exit}
# operations that are handled directly by the stack's dispatch method
OPMAP[:dump] = :dump
OPMAP[:clear] = :clear
def initialize
@stack = Stack.new
end
def eval str
show = false
str.split.each do |token|
case token
when /^-?\d+(?:\.\d*)?$/
@stack.push token.to_f
else
op = OPMAP[token.to_sym]
raise ArgumentError, "Unknown operator #{token}" unless op
show = @stack.dispatch op
end
end
@stack.last if show
end
end
evaler = Evaluator.new
$stdin.each do |line|
begin
puts evaler.eval(line) || ''
rescue => e
$stderr.puts e.message
end
end
;;; rpn.scm---basic RPN calculator
;;; Copyright (c) 2009 Chris K. Jester-Young; GPLv3+
;;; Requires SRFIs 1 and 26. Uncomment one set of the following:
; (require srfi/1 srfi/26) ; Racket
; (use srfi-1 srfi-26) ; Chicken
; (use-modules (srfi srfi-1) (srfi srfi-26)) ; Guile
(define-syntax dispatch-op
(syntax-rules ()
((dispatch-op call ((sym op)) token)
(and (eq? token sym) (call op)))
((dispatch-op call ((sym op) next ...) token)
(if (eq? token sym) (call op)
(dispatch-op call (next ...) token)))
((dispatch-op call (op next ...) token)
(dispatch-op call (('op op) next ...) token))))
(define (show port . items)
(for-each (cut display <> port) items)
(newline port))
(define print (cut show (current-output-port) <...>))
; CURRENT-ERROR-PORT is not portable :-(
(define warn (cut show (current-error-port) <...>))
(define (print-stack-top stack)
(or (null? stack) (print (car stack)))
stack)
(define (pushall stack . items)
(append! (reverse! items) stack))
(define (call op arity stack)
(call-with-values
(cut split-at! stack arity)
(lambda (args stack)
(call-with-values
(cut apply op (reverse! args))
(cut pushall stack <...>)))))
(define (dispatch token stack)
(define (dump)
(print stack)
(values))
(define (switch call)
(let ((nullary (cut call <> 0))
(unary (cut call <> 1))
(binary (cut call <> 2)))
(dispatch-op binary (+ - * / expt ('** expt) ('atan2 atan)) token)
(dispatch-op unary (exp log sqrt sin cos tan asin acos atan) token)
; Special functions (note EXIT is not portable)
(dispatch-op nullary (exit ('q exit) ('quit exit) dump values) token)
(warn "Unrecognised token: " token)
(call values 0)))
(call-with-values
(cut call/cc switch)
(cut call <> <> stack)))
(define (on-token token stack)
(cond
((eof-object? token) (exit))
((number? token) (cons token stack))
(else (print-stack-top (dispatch token stack)))))
(let loop ((stack '()))
(loop (on-token (read) stack)))
import java.io.IOException;
import java.lang.annotation.Retention;
import java.lang.annotation.RetentionPolicy;
import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;
import java.util.ArrayDeque;
import java.util.Collections;
import java.util.Deque;
import java.util.EmptyStackException;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;
public class Rpn7 {
@Retention(RetentionPolicy.RUNTIME)
private @interface Op {
String value();
}
private static class PrimOps {
@Op("+")
public static double plus(double lhs, double rhs) {
return check(lhs + rhs);
}
@Op("-")
public static double minus(double lhs, double rhs) {
return check(lhs - rhs);
}
@Op("*")
public static double multiplies(double lhs, double rhs) {
return check(lhs * rhs);
}
@Op("/")
public static double divides(double lhs, double rhs) {
return check(lhs / rhs);
}
@Op("%")
public static double modulus(double lhs, double rhs) {
return check(lhs % rhs);
}
private static double check(double result) {
if (Double.isNaN(result) || Double.isInfinite(result))
throw new ArithmeticException();
return result;
}
}
private static final Map<String, Method> MATH_METHODS;
static {
Map<String, Method> methods = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
for (Method method : PrimOps.class.getMethods()) {
Op op = method.getAnnotation(Op.class);
if (op != null)
methods.put(op.value(), method);
}
for (Method method : Math.class.getMethods()) {
if (method.getReturnType() != double.class)
continue;
for (Class<?> type : method.getParameterTypes())
if (type != double.class)
continue;
String name = method.getName();
methods.put(name, methods.containsKey(name) ? null : method);
}
MATH_METHODS = Collections.unmodifiableMap(methods);
}
private final Deque<Double> stack = new ArrayDeque<>();
public static void main(String[] args) throws IOException {
Rpn7 self = new Rpn7();
try (Scanner stdin = new Scanner(System.in)) {
while (stdin.hasNextLine())
self.process(stdin.nextLine());
}
}
public void process(String line) {
try (Scanner scanner = new Scanner(line)) {
while (true) {
if (scanner.hasNextDouble())
stack.push(scanner.nextDouble());
else if (scanner.hasNext())
stack.push(dispatch(scanner.next()));
else
break;
}
if (!stack.isEmpty())
System.out.println(stack.peek());
} catch (IllegalArgumentException | ArithmeticException | EmptyStackException e) {
System.err.println(e);
}
}
private double dispatch(String token) {
Method method = getMethodFor(token);
int arity = method.getParameterTypes().length;
if (stack.size() < arity)
throw new EmptyStackException();
Deque<Double> args = new ArrayDeque<>();
for (int i = 0; i < arity; ++i)
args.push(stack.pop());
boolean succeeded = false;
try {
double result = (Double) method.invoke(null, args.toArray());
succeeded = true;
return result;
} catch (IllegalAccessException e) {
throw new AssertionError(e);
} catch (InvocationTargetException e) {
Throwable cause = e.getCause();
if (cause instanceof RuntimeException)
throw (RuntimeException) cause;
throw new AssertionError(cause);
} finally {
if (!succeeded)
for (Double arg : args)
stack.push(arg);
}
}
private static Method getMethodFor(String token) {
Method method = MATH_METHODS.get(token);
if (method == null)
throw new IllegalArgumentException(token);
return method;
}
}
import java.io.IOException;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.EmptyStackException;
import java.util.Scanner;
import java.util.function.DoubleBinaryOperator;
import java.util.function.DoubleSupplier;
import java.util.function.DoubleUnaryOperator;
public class Rpn8 {
private final Deque<Double> stack = new ArrayDeque<>();
public static void main(String[] args) throws IOException {
Rpn8 self = new Rpn8();
try (Scanner stdin = new Scanner(System.in)) {
while (stdin.hasNextLine()) {
try {
Double value = self.process(stdin.nextLine());
if (value != null)
System.out.println(value);
} catch (IllegalArgumentException | EmptyStackException e) {
System.err.println(e);
}
}
}
}
public Double process(String line) {
try (Scanner scanner = new Scanner(line)) {
while (true) {
if (scanner.hasNextDouble())
stack.push(scanner.nextDouble());
else if (scanner.hasNext())
stack.push(lookup(scanner.next()).getAsDouble());
else
break;
}
}
return stack.peek();
}
private DoubleSupplier lookup(String name) {
switch (name) {
case "+": return wrap((a, b) -> a + b);
case "-": return wrap((a, b) -> a - b);
case "*": return wrap((a, b) -> a * b);
case "/": return wrap((a, b) -> a / b);
case "%": return wrap((a, b) -> a % b);
case "^": return wrap(Math::pow);
case "atan2": return wrap(Math::atan2);
case "rem": return wrap(Math::IEEEremainder);
case "hypot": return wrap(Math::hypot);
case "sin": return wrap(Math::sin);
case "cos": return wrap(Math::cos);
case "tan": return wrap(Math::tan);
case "asin": return wrap(Math::asin);
case "acos": return wrap(Math::acos);
case "atan": return wrap(Math::atan);
case "exp": return wrap(Math::exp);
case "log": return wrap(Math::log);
case "sqrt": return wrap(Math::sqrt);
case "cbrt": return wrap(Math::cbrt);
case "sinh": return wrap(Math::sinh);
case "cosh": return wrap(Math::cosh);
case "tanh": return wrap(Math::tanh);
case "expm1": return wrap(Math::expm1);
case "log1p": return wrap(Math::log1p);
case "random": return Math::random;
case "q": return () -> {throw new ThreadDeath();};
default: throw new IllegalArgumentException("Unknown token " + name);
}
}
private DoubleSupplier wrap(DoubleBinaryOperator binary) {
return () -> {
if (stack.size() < 2)
throw new EmptyStackException();
double r = stack.pop();
return binary.applyAsDouble(stack.pop(), r);
};
}
private DoubleSupplier wrap(DoubleUnaryOperator unary) {
return () -> {
if (stack.isEmpty())
throw new EmptyStackException();
return unary.applyAsDouble(stack.pop());
};
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment