# Reverse Polish Notation

Is there a way to evaluate a string containing RPN in Mathematica?

SE thinks this question is too short, so let me expand on it. Do you know of any function, that provides the following functionality?

EvalRPN["5 4 + 3 /"]


3

Or even symbolically?

EvalRPN["a b + c /"]


(a+b)/c

The thing is, you need to identify what operators should be infix, what should be prefix, what should be postfix, and how many elements from the stack to use. There may be a better way than just listing them, but here I just list them and then use ToExpression to make functions out of them to apply to already-evaluated stack elements (e.g. ToExpression["#1" <> op <> "#2&"]). Anything that's not a listed operator is simply evaluated and put on the stack.

rpninfix = {"+", "-", "*", "\[Times]", "/", "\[Divide]", "^", ".",
"==", "\[Equal]", "!=", "\[NotEqual]", "<", ">", "<=",
"\[LessEqual]", ">=", "\[GreaterEqual]", "&&", "||"};
rpnprefix = {"Sqrt", "CubeRoot", "Log", "Log10", "Log2", "Exp",
"Sin", "Cos", "Tan", "ArcSin", "ArcCos", "ArcTan", "Sinh", "Cosh",
"Tanh", "ArcSinh", "ArcCosh", "ArcTanh", "N", "Abs", "Arg", "Re",
"Im", "Round", "Floor", "Ceiling", "IntegerPart", "FractionalPart",
"Gamma", "Erf", "Erfc", "InverseErf", "InverseErfc"};
ArcTan2[y_, x_] := ArcTan[x, y]
rpnprefix2 = {"Mod", "Quotient", "GCD", "LCM", "Binomial", "Surd",
"ArcTan2"};
rpnprefixall = {"Plus", "Times", "Min", "Max"};
rpnpostfix = {"!"};
rpn::short = "1 ignored -- needs 2 entries on the stack";
rpn[stack_, {op_, rest___}] :=
Which[
MemberQ[rpninfix, op],
If[Length[stack] < 2, Message[rpn::short, op, 2]; rpn[stack, {rest}],
rpn[Append[Drop[stack, -2],
ToExpression["#1" <> op <> "#2&"] @@ Take[stack, -2]], {rest}]],
MemberQ[rpnprefix, op],
If[Length[stack] < 1, Message[rpn::short, op, 1]; rpn[stack, {rest}],
rpn[Append[Drop[stack, -1], ToExpression[op]@stack[[-1]]], {rest}]],
MemberQ[rpnprefix2, op],
If[Length[stack] < 2, Message[rpn::short, op, 2]; rpn[stack, {rest}],
rpn[Append[Drop[stack, -2],
ToExpression[op] @@ Take[stack, -2]], {rest}]],
MemberQ[rpnprefixall, op],
rpn[{ToExpression[op] @@ stack}, {rest}],
MemberQ[rpnpostfix, op],
If[Length[stack] < 1, Message[rpn::short, op, 1]; rpn[stack, {rest}],
rpn[Append[Drop[stack, -1],
ToExpression["#" <> op <> "&"]@stack[[-1]]], {rest}]],
True,
rpn[Append[stack, ToExpression[op]], {rest}]
]
rpneval[str_] := First@rpn[{}, StringSplit[str]]


Just for fun, I threw in some that operate on the entire stack, so Times multiplies the stack elements together, since you already have * to multiply just the bottom two.

You can't have RPN operators with a variable number of arguments (unless the number is implied by the contents of the stack), so I added an ArcTan2 for a two-argument arctangent.

Examples:

rpneval["1 2 + 3 4 + * Exp 10 ! Sqrt 70 42 GCD"]


{E^21, 720 Sqrt[7], 14}

Note that the result has to be a list, since the expression might leave more than one thing on the stack. You can always get the bottom of the stack with Last:

rpneval["a b + c d + * e / n ^"]//Last


(((a + b) (c + d))/e)^n

If speed is important, the function lists could be made into a single association.

rpn[{}, stackipt_: {}] := First@stackipt
rpn[list_, stack_: {}] := Module[{ops = {Plus, Subtract, Times}},
If[MemberQ[ops, First@list],
rpn[Rest@list, Prepend[stack[[3 ;;]], (First@list) @@ stack[[2 ;; 1 ;; -1]]]],
rpn[Rest@list, Prepend[stack, First@list]]]]

rpn[{3, 2, 5, Plus, Times}]
(* 21 *)

rpn[{a, b, c, d, Plus, Times, Plus}]
(* a + b (c + d) *)

• The OP wants to evaluate a string. – Mark Adler Dec 29 '15 at 5:07
• @MarkAdler Yep, well, I don't think s/he should – Dr. belisarius Dec 29 '15 at 5:16

A rule based option:

Clear[rpn]
$InfixOperators = Plus | Subtract | Times | Divide;$PrefixOperators = Cos | Sin | Sqrt;
operand = Except@Join[$InfixOperators,$PrefixOperators];

rpn[{a : operand ..., b : operand, c : operand, op : $InfixOperators, d___}] := rpn[{a, op[b, c], d}] rpn[{a : operand ..., b : operand, op :$PrefixOperators, c___}] := rpn[{a, op[b], c}]
rpn[{res_}] := res


Examples:

rpn[{a, b, c, d, Plus, Times, Plus}]


a + b (c + d)

rpn[{a, b, Plus, c, Divide}]


(a + b)/c

rpn[{4, Sqrt, 5, Plus}]


7

To evaluate strings:

$OperatorNotations = {"+" -> Plus, "-" -> Subtract, "*" -> Times, "/" -> Divide}; EvalRPN[str_] := rpn[StringSplit[str] /.$OperatorNotations // ToExpression]


This will take a few seconds to run the first time in a session that an operator is used since it needs to download the "WolframLanguageSymbol" Entity for that operator. After that subsequent calls in the session with the entity will be fast since it is in the cache.

getMathOperation takes the short notation of the operator and returns the symbol.

getMathOperation[op_String] :=
ToExpression[
CanonicalName@
First@EntityList@
Entity["WolframLanguageSymbol", {EntityProperty[
"WolframLanguageSymbol", "ShortNotations"] -> op}]]


evalRPN evaluates a reverse polish notation string and makes use of getMathOperation.

evalRPN[expr_String] :=
With[{s = StringSplit[expr]},
Fold[
Function[{running, next},
getMathOperation[Last@next][(running), ToExpression@First@next]],
getMathOperation[s[[3]]][Sequence @@ ToExpression /@ s[[1 ;; 2]]],
Partition[s[[4 ;;]], 2]]
]


Testing it out.

evalRPN["a b + c /"]
(* (a + b)/c *)

evalRPN["a b + c / e - f ^ g *"]
(* ((a + b)/c - e)^f g *)


Hope this helps.

• If you're going to use ToExpression anyway, then you can just evaluate the operator directly with having to convert it to the symbol for that function. – Mark Adler Dec 29 '15 at 4:58
• Doesn't work on evalRPN["2 3 + 4 5 + *"]. – Mark Adler Dec 29 '15 at 5:01

You can find this approach easier,

l={"a", "b", "+", "c", "/"}

Polish[q_List] :=
ReplaceRepeated[
q, {s___, a_, b_, c_String,
d___} /; (c == "+" || c == "/" || c == "*" ||
c == "/") :> {s, {a, c, b}, d}] //. {a___, {b_String, c_,
d_String}, e___} :> {a, b <> c <> d, e}

Polish[l] =>{"a+b/c"}
Polish[{"2", "3", "+", "4", "5", "+", "*"}]=> {"2+3*4+5"}


You can convert it into expression by using ToExpression if you want.

• Fails on "a b + c d + *". Gives "a+b*c+d". I'm seeing this simple case fail on many of the answers here. Am I the only one who uses an HP calculator? – Mark Adler Dec 29 '15 at 5:16
• @MarkAdler : I think its invalid expression. {a,b,+} on stack, poped as a+b, a+b in stack, push c, then push d, then pop c+d, push c+d over a+b, but there is no more operand for these two !! – Rorschach Dec 29 '15 at 5:22
• Ok, clearly you don't use an HP calculator. a b + leaves a+b on the stack. Then c d + leaves c+d on the stack, under a+b. Then * multiplies the two things on the stack, giving (a+b)(c+d). There is no pushing something "over" something else. – Mark Adler Dec 29 '15 at 5:26