Code golf: Reverse Polish notation (postfix) evaluator

Question

After having had code-golf contests on ordinary mathematical expressions, I just thought it would also be quite interesting how short an evaluation function for postfix notation (RPN) can be.

Examples for RPN:

1 2 + == 3
1 2 + 3 * == 9
0 1 2 3 + + - 2 6 * + 3 / 1 - == 1
3 2 / 2.0 + == 3.5

To make things shorter, only +, -, * and /, all just in their binary version, must be supported. Operators/Operands are delimited by one space, divsions by zero don't have to be handled.

The resulting code should be a function that takes the postfix string as input and returns the resulting number.

Answer 1

Python 3

111 chars

Reads statement from stdin:

$ echo "3 2 / 2.0 +" | python3 q.py
3.5

L=[]
p=L.pop
a=L.append
for w in input().split():a(str(eval("1.*"+p(-2)+w+p()))if w in"-*+/"else w)
print(p())

Python 2.X

114 chars

L=[]
p=L.pop
a=L.append
for w in raw_input().split():a(str(eval("1.*"+p(-2)+w+p()))if w in"-*+/"else w)
print p()

Answer 2

Scheme

(define (rpn . args)
  (define (p s a)
    (if (procedure? a)
        (cons (a (cadr s) (car s)) (cddr s))
        (cons a s)))
  (car (fold-left p '() args)))

Usage

(rpn 1 2 + 3 +) ;=> 6

Answer 3

From Wikipedia / Haskell,

calc = foldl f [] . words
  where 
    f (x:y:zs) "+" = (y + x):zs
    f (x:y:zs) "-" = (y - x):zs
    f (x:y:zs) "*" = (y * x):zs
    f (x:y:zs) "/" = (y / x):zs
    f xs y = read y : xs

can be shortened to 108 characters.

c=foldl(&)[].words where(x:y:z)&"+"=y+x:z;(x:y:z)&"-"=y-x:z;(x:y:z)&"*"=y*x:z;(x:y:z)&"/"=y/x:z;z&y=read y:z

Of course, one could always "cheat" with Perl: 83 characters

sub c{local($_)=@_;1while+s#(-?[\d.]+) (-?[\d.]+) ([-+/*])(?!\S)#eval"$1$3$2"#e;$_}

Answer 4

Perl, 73 characters, corrected

sub r{push @_,m{^[-+*/]$}?
eval"pop(\@_)$_".pop:$_ for split" ",shift;pop}

Linebreak is for clarity only.

Answer 5

Perl 115 char

Without eval.

sub Y{push@s,@_}sub Z{pop@s}$_=<>;for(split){/-/&&Y-&Z+Z;/\+/&&Y&Z+Z;
y@/@*@&&Y 1/Z;/\*/&&Y&Z*Z;/\d/&&Y$_}print&Z,$/

Maintains a stack of operands in @s. When an operator + - * / is encountered, pop two elements of the stack, perform the operation, and push them back onto the stack. Pops and prints the top of the stack when we run out of input.

/ is a special case:

y@/@*@ && push @s,1/(pop @s)

When / is encountered, replace the top of the stack with its reciprocal and change the operation to *. We could do something similar with +/-, but it would cost a character.

Answer 6

Python 2.6 - 89 chars with newlines

Reads expression from first line of STDIN. Only works with integers.

E=[]
P=E.pop
for t in raw_input().split():E+=[t>"/"and t or`eval(P(-2)+t+P())`]
print P()

Answer 7

dc

4 chars

Yes, this is a very cheap approach:

$ cat rpn
9k?p
$ echo "3 2 / 2.0 +" | dc -f rpn
3.500000000
$ echo "1 2 + 3 *" | dc -f rpn
9

9k sets the floating precision to 9 spots after the decimal; ? reads a line from stdin and immediately evaluates it; p prints the top number on the stack. dc -f rpn executes the file named rpn.

Answer 8

Clojure - 193 chars.

I really like the Scheme answer, as it's short and simple. This is made complicated by taking in a string as an argument.

Golf'd (remaining whitespace is important):

(def f first)(def $
#(if(>(count%)0)(let[o{"*"*"/"/"+"+"-"-}](if(o(f%))(recur(next%)(cons((o(f%))(second%2)(f%2))(nnext%2)))(recur(next%)(cons(Float.(f%))%2))))(f%2)))(def
r #($(.split%" ")[]))

Call like so: (r "1 2 +").

Ungolf'd:

(defn rpn
  ([stmt] (rpn (.split stmt " ") [])) ;split the string by spaces, use an empty vector as a stack
  ([in stack]
    (if (> (count in) 0)              ;if there's something to process '
      (let [ops {"*" *                ;here, we map strings to their respective functions
                 "/" /
                 "+" +
                 "-" -}]
        (if (ops (first in))          ;check if the next item to process is an operator
          (recur 
            (next in) 
            (cons                     ;stick the result of the operation at the head of the stack
              ((ops (first in))  ;execute the operation on...
                (second stack)   ; the second item in the stack and...
                (first stack))   ; the first item in the stack
              (nnext stack)))  ;we've consumed the first two items, so disregard them '
          (recur
            (next in)
            (cons 
              (Float. (first in))     ;convert the string to a float, and stick it in the stack
              stack))))
      (first stack))))                ;return the head of the stack.  should also be the only item in the stack

In order to make the short version... shorter, first is redefined as just f. Doing that to any other func would cost more chars than would be slimmed down, or would be a no-win game. Other than that no fancy tricks were used.

Answer 9

Perl - 87 chars

.

sub e{$_=$_[0];0while s/(-?\d+(\.\d+)?) (-?\d+(\.\d+)?) ([-+*\/])/eval("$1$5$3")/ge;$_}

Or in a more readable fashion:

sub e{
    $_ = $_[0];
    0 while (s/(-?\d+(\.\d+)?) (-?\d+(\.\d+)?) ([-+*\/])/eval("$1$5$3")/ge)
    $_
}

Call:

print e("1 2.0 + 3 *")

Answer 10

Ruby, 80, RE, eval

Really, it should be stated whether eval is permitted. (I suggest no.) Anyway, run each with ruby -a -p rpn.rb

s=[]
$F.each { |e|
  s << if /\d/===e
    e.to_f
  else
    a,b = s.pop 2
    eval "a %s b" % e
  end
}
$_ = s.pop

Ruby, 107, RE, no eval

s=[]
$F.each { |e|
  s << if e=~/\d/ 
    e.to_f
  else
    a,b = s.pop 2
    { ?+ => a+b, ?* => a*b, ?- => a-b, ?/ => a/b }[e[0]]
  end
}
$_ = s.pop

Ruby, 109, no RE, no eval

s=[]
$F.each { |e|
  s << if '*+/-'[e]
    a,b = s.pop 2
    {'+' => a + b, '-' => a - b, '*' => a * b, '/' => a / b}[e]
  else
    e.to_f
  end
}
$_ = s.pop

Answer 11

Python - 157 (without using eval)

the try/except is indented with tabs

def f(s):
 E=s.split();i=0
 while len(E)>1:
    try:a,b=map(float,E[i:i+2]);c=E[i+2];E[i:i+3]=[[a+b,a-b,a*b,a/b]["+-*/".index(c)]];i=0
    except:i+=1
 return E[0]

Answer 12

Python - 171 (without using eval)

hobbs idea to replace the [--9] with \S

import re
def g(x):a,b,c=x.groups();a,b=map(float,[a,b]);return "%s"%[a-b,a*b,a/b,a+b]["-*/".find(c)]
f=lambda s:s.count(' ')and f(re.sub("(\S+) (\S+) ([*-/])",g,s,1))or s

Python - 177 (without using eval)

This is slightly longer than my other Python solution, but
How often do you get to use [--9] in a regexp?

import re
def g(x):a,b,c=x.groups();a,b=map(float,[a,b]);return "%s"%[a-b,a*b,a/b,a+b]["-*/".find(c)] 
f=lambda s:s.count(' ')and f(re.sub("([--9]+) ([--9]+) ([*-/])",g,s,1))or s

Answer 13

C, 142 chars

Whitespace added for your sanity.

s[99],*t=s,y;
e(char*x)
{
  while(y=*x)
    y & 16 ?
      *++t = strtol(x,&x,10)
    :
      (y+1 & 4 ?
        (t[-1] += y&2 ? *t : -*t)
      :
        y & 2 ?
          y & 1 ?
            (t[-1] /= *t)
          :
            (t[-1] *= *t)
        :
          t++,
          t--,
          x++);
  return *t;
}

Answer 14

PostScript - 114 (no eval) 113 (with eval)

No eval, except on individual tokens, which isn't really eval.

{[/+{add}/-{sub}/*{mul}/{div}/D{dup()ne{token pop dup where{pop load}if exch D}if}>>begin[exch D pop]{exec}forall}

Usage:

(0 1 2 3 + + - 2 6 * + 3 / 1 -)
{[/+{add}/-{sub}/*{mul}/{div}/D{dup()ne{token pop dup where{pop load}if exch D}if}>>begin[exch D pop]{exec}forall}
exec ==

-> 1.0

Note that this is the standard way of executing an unnamed procedure and that the procedure itself does not print the output value (though it takes in a string and returns a value, as specified in the instructions).

Replacing operators with PS ones, then executing (that is, eval), for one byte less:

{[{+ add - sub * mul/ div D{dup()ne{token pop dup where{pop load}if exch D}if}}aload/>>begin[exch D pop]cvx exec}

This version would have been 46 characters, but unfortunately '/' is a special character in PS so any expressions with division would fail. Here's the 46-character version, with 'd' substituting for '/'.

{cvx[/+{add}/-{sub}/*{mul}/d{div}>>begin exec}

Answer 15

F#: 196 chars

Minimized code:

let rpn input=String.split[' ']input|>Seq.fold (fun xs x->match((["*",(*);"+",(+);"-",(-);"/",(/)]|>Map.of_list).TryFind x),xs with|Some f,x::y::rest->f x y::rest|None,xs->xs@[float x])[]|>List.hd

Readable code:

let rpn input =
    String.split [' '] input
    |> Seq.fold (fun xs x ->
        let lookup = ["*", (*); "+", (+); "-", (-); "/" ,(/)] |> Map.of_list
        match lookup.TryFind x, xs with
        | Some f, x::y::rest -> f x y::rest
        | None, xs -> xs @ [float x]) []
    |> List.hd

Explanation: I have a lookup table which maps strings to functions. If we find a function f in the lookup table, we replace the first two values on our eval queue -- which is really a stack -- with f(pop first two values off stack). If we don't find our function, we append the value to end of our queue. Finally, we return the first value from the top of our queue.

Guaranteed to be very inefficient, would probably get you fired from your job if implemented like this in practice.

Here's the function in fsi:

val rpn : string -> float

> rpn "1 2 +";;
val it : float = 3.0
> rpn "1 2 + 3 *";;
val it : float = 9.0
> rpn "0 1 2 3 + + - 2 6 * + 3 / 1 -";;
val it : float = 1.0
> rpn "3 2 / 2.0 +";;
val it : float = 3.5

Answer 16

Lua, 186 characters

function f(v)s,r={},table.remove for x in v:gmatch("[^%s]+")do n=x=="+"and r(s)+r(s)or x=="-"and -r(s)+r(s)or x=="*"and r(s)*r(s)or x=="/"and 1/r(s)*r(s)or x s[#s+1]=n end return s[1]end

Or, using loadstring() (similar to eval), 150 characters.

function f(v)s,r={},table.remove for x in v:gmatch("[^%s]+")do n=tonumber(x)or loadstring("return "..r(s,#s-1)..x..r(s))()s[#s+1]=n end return s[1]end

Answer 17

JavaScript

With Eval: 141 Characters

function Z(o){o=o.split(' ');s=[];for(i in o)if(o[i].match(/^[0-9.]+$/))
s.push(o[i]);else{f=s.pop();s.push(eval(s.pop()+o[i]+f))}return s[0]}

Without Eval: 171 Characters

function Z(o){o=o.split(' ');s=[];for(i in o)if(o[i].match(/^[0-9.]+$/))
s.push(+o[i]);else{f=s.pop();p=s.pop();
s.push([p+f,p-f,p*f,p/f]['+-*/'.indexOf(o[i])])}return s[0]}

(New lines are all for readability)

Answer 18

Scala 171 Characters

def e(s: String)=(List[Int]()/:s.split(" ")){case(x::y::t,"+")=>x+y::t case(x::y::t,"-")=>x-y::t case(x::y::t,"*")=>x*y::t case(x::y::t,"/")=>x/y::t case(t,n)=>n.toInt::t}

Ungolfed

def eval(s: String) = s.split(" ").foldLeft(List[Int]()) {
  case (x :: y :: tail, "+") => x + y :: tail
  case (x :: y :: tail, "-") => x - y :: tail
  case (x :: y :: tail, "*") => x * y :: tail
  case (x :: y :: tail, "/") => x / y :: tail
  case (tail, n) => n.toInt :: tail
}

Pretty close to the Haskell version, actually. The main difference is that Scala is substantially more verbose that Haskell (and not just in type annotations).

Answer 19

FORTH 42 characters

This is the answer in ciforth:

[1]: ciforth

You force me to reimplement evaluate? fine!

: == . ;
: E 1 ARG[] SET-SRC INTERPRET ;

This illustrates the assignment is silly. Adapt evaluate but if you have it you can't use it. So I just reimplement EVALUATE. As there is no restriction in using the factors of evaluate the reimplementation is very short in a highly factored language.

Usage : after lina -c e.frt

e '78 8 * == '

gives the expected 624

The statically linked executable for the ``e'' program is 30Kbyte (linux 32) Without even looking I know that no language here comes close. (Other Forths migh, like 4th).

Answer 20

Perl 63 chars

function :

sub r{$_=pop;1while(s!(\S+) (\S+) ([*/+-])!eval"$1$3$2"!eg);$_}

call :

print r("12 3 / 6 6 + *"),"\n";

result :

48