Reverse polish notation: Difference between revisions

Content added Content deleted

Inline

Latest revision as of 08:39, 24 March 2014

Redirect to:

Parsing/RPN calculator algorithm

@@ Line 1: / Line 1: @@
+#REDIRECT [[Parsing/RPN_calculator_algorithm]]
-{{Duplicate|Parsing/RPN calculator algorithm}}
-{{draft task}}
-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.
-=={{header|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>
-=={{header|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>
-{{out}}
-<pre>5
-</pre>
-=={{header|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>
-{{out}}
-<lang erlang>54> rpn:eval("1 2 3 - +").
-> rpn:eval("1 2 3 + +").
-> rpn:eval("1 2 3 + *").
-> rpn:eval("1 2 3 + /").
-.0
-> rpn:eval("1 2 3 + -").
--4</lang>
-=={{header|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>
-=={{header|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>
-{{out}}
-<pre>
-</pre>