Reverse polish notation

This page is a duplicate of Parsing/RPN calculator algorithm. Its information should be merged with that of its sibling page. Please see the Talk page for details.

Reverse polish notation is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Reverse polish notation, also known as postfix notation, is a way to express mathematical expressions. In RPN the operands come before the operator.

For example:

• 2+3 = 2 3 +
• 2+4*5 = 2 4 5 * +
• (2+4)*5 = 2 4 + 5 *

Given a mathematical expression containing integers and + - * /, compute the value of the expression.

Common Lisp

<lang lisp>(defun rpn (tokens &optional stack)

   (cond
       ((and (not tokens) (not stack)) 0)
       ((not tokens) (car stack))
       ((integerp (car tokens)) 
           (rpn (cdr tokens) (cons (car tokens) stack)))
       (T (let ((arg2 (car stack))
                (arg1 (cadr stack))
                (fun (car tokens)))
           (rpn (cdr tokens) (cons (funcall fun arg1 arg2) (cddr stack)))))))</lang>

D

<lang d>import std.stdio, std.string, std.conv, std.typetuple;

real evalRPN(in string input) {

   real[] stack;
   foreach (immutable tok; input.split) {
       switch (tok) {
           foreach (immutable o; TypeTuple!("+", "-", "*", "/")) {
               case o:
                   mixin("stack[$ - 2] " ~ o ~ "= stack[$ - 1];");
                   stack.length--;
                   break;
           }
           break;
           default:
               stack ~= tok.to!real;
       }
   }
   return stack[0];

}

void main() {

   "2 3 +".evalRPN.writeln;
   "2 4 5 * +".evalRPN.writeln;
   "2 4 + 5 *".evalRPN.writeln;

}</lang>

Output:

5
22
30

Erlang

<lang erlang>-module(rpn). -export([eval/1]).

parse(Expression) ->

   parse(string:tokens(Expression," "),[]).

parse([],Expression) ->

   lists:reverse(Expression);

parse(["+"|Xs],Expression) ->

   parse(Xs,[plus|Expression]);

parse(["-"|Xs],Expression) ->

   parse(Xs,[minus|Expression]);

parse(["*"|Xs],Expression) ->

   parse(Xs,[times|Expression]);

parse(["/"|Xs],Expression) ->

   parse(Xs,[divide|Expression]);

parse([X|Xs],Expression) ->

   {N,_} = string:to_integer(X),
   parse(Xs,[N|Expression]).

%% The expression should be entered as a string of numbers and %% operators separated by spaces. No error handling is included if %% another string format is used. eval(Expression) ->

   eval(parse(Expression),[]).

eval([],[N]) ->

   N;

eval([N|Exp],Stack) when is_number(N) ->

   eval(Exp,[N|Stack]);

eval([plus|Exp],[X,Y|Stack]) ->

   eval(Exp,[X+Y|Stack]);

eval([minus|Exp],[Y,X|Stack]) ->

   eval(Exp,[X-Y|Stack]);

eval([divide|Exp],[Y,X|Stack]) ->

   eval(Exp,[X/Y|Stack]);

eval([times|Exp],[X,Y|Stack]) ->

   eval(Exp,[X*Y|Stack]).</lang>

Output:

<lang erlang>54> rpn:eval("1 2 3 - +"). 0 55> rpn:eval("1 2 3 + +"). 6 56> rpn:eval("1 2 3 + *"). 5 57> rpn:eval("1 2 3 + /"). 5.0 58> rpn:eval("1 2 3 + -"). -4</lang>

Python

<lang python>def isNum(self, i):

 try:
   int(i)
   return True
 except ValueError:
   return False

def evalRPN(self, tokens):

 l=[]
 for i in tokens:
   if isNum(i):
     l.append(int(i))
   else:
     second = l.pop()
     first = l.pop()
     l.append(eval("first" + i + "second"))
 return l[0]</lang>

Tcl

This version assumes that all operators are binary operators. <lang tcl>proc evalRPN args {

   set stack {}
   foreach token $args {

if {[string is int -strict $token]} { lappend stack $token } else { set newval [tcl::mathop::$token {*}[lrange $stack end-1 end]] set stack [lreplace $stack end-1 end $newval] }

   }
   return [lindex $stack 0]

}</lang> Demonstrating: <lang tcl>puts [evalRPN 2 3 +] puts [evalRPN 2 4 5 * +] puts [evalRPN 2 4 + 5 *]</lang>

Output:

5
22
30