Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
RPN

RPN

Evaluates well-formed reverse polish notation expressions (http://en.wikipedia.org/wiki/Reverse_Polish_notation).

Input

Strings with tokens separated by single spaces. Tokens are operators or operands. Operators are +, -, * or /. Operands are integers or floats (e.g. 7, 3.23, -1e9).

Output

The value of the evaluated expression.

Examples

"1 1 +" -> 2

"5 8 -" -> -3

"2 3 7 + -" -> -8

"5 3 * 5 +" -> 20

function(a, // The input string
b) { // Placeholder var that will become the stack
return (b = [])[ // Create an empty stack, and later return its 0th element (*)
a.replace(/\S+/g, // For each token (everything that does not
// contain spaces) in the string,
function(c) { // inspect and act on it:
b.push( // Something will always be pushed to the stack:
+c || // If it is a number (an operand), push the number itself.
eval( // Else it is an operator.
b.pop(a = b.pop()) + // Pop the topmost element and save it in a.
// Then pop the next element and
c + // apply the operator together with the
a)) // previously saved element.
}),
0] // (*) After going through all tokens, index the 0th element
// of the stack. This is the result of the expression.
}
function(a,b){return(b=[])[a.replace(/\S+/g,function(c){b.push(+c==c?c:eval(b.pop(a=b.pop())+c+a))}),0]}
DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
Version 2, December 2004
Copyright (C) 2011 YOUR_NAME_HERE <YOUR_URL_HERE>
Everyone is permitted to copy and distribute verbatim or modified
copies of this license document, and changing it is allowed as long
as the name is changed.
DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION
0. You just DO WHAT THE FUCK YOU WANT TO.
{
"name": "rpn",
"description": "Reverse Polish Notation expression evaluator",
"keywords": [
"expression",
"parser",
"rpn",
"evaluator"
]
}
<!DOCTYPE html>
<title>RPN</title>
<div>Expected value: <b>3, -4, -8, 14</b></div>
<div>Actual value: <b id="ret"></b></div>
<script>
// write a small example that shows off the API for your example
// and tests it in one fell swoop.
var myFunction = function(a,b){return(b=[])[a.replace(/\S+/g,function(c){b.push(+c==c?c:eval(b.pop(a=b.pop())+c+a))}),0]}
document.getElementById( "ret" ).innerHTML = [myFunction('1 2 +'), myFunction('2 6 -'), myFunction('2 3 7 + -'), myFunction('5 1 2 + 4 * + 3 -')].join(', ');
</script>
@peterjaric

This comment has been minimized.

Copy link
Owner Author

peterjaric commented Oct 11, 2011

Current size is 240 bytes. If we use eval, we can cut it down to 164 bytes:

function(i,s,t,j,e){i=i.split(' ');t=[];t.o=t.pop;t.u=t.push;for(j=0;j<i.length;j++){e=i[j];/[\d]+/.test(e)?t.u(e*1):eval('s=t.o(),t.u(t.o()'+e+'s)')};return t[0];}

I'll quote @140bytes on eval: "avoid it if you can, but sometimes ya gotta do what ya gotta do."

Is it possible to remove 100 bytes, or should we aim for the extra 24 bytes in the eval version?

@pvdz

This comment has been minimized.

Copy link

pvdz commented Oct 11, 2011

Maybe start with removing useless parenthesis, semi-colons and apply other common tricks...

@peterjaric

This comment has been minimized.

Copy link
Owner Author

peterjaric commented Oct 11, 2011

Please do! I honestly thought I had to keep those semi-colons at least...

Edit: Ah, there's was one at the end.

@peterjaric

This comment has been minimized.

Copy link
Owner Author

peterjaric commented Oct 11, 2011

But I see I left a space by mistake. I'll remove that one.

@floriancargoet

This comment has been minimized.

Copy link

floriancargoet commented Oct 11, 2011

In each case you pop 2 values from the stack. I guess you could cut some bits doing it only once at the beginning of the loop. A while(j--) loop could be shorter (but reversed). There's a lot of extra parenthesis and some semi-colons. The ternary operator (?:) is shorter than &&||.
Have fun!

@tobytailor

This comment has been minimized.

Copy link

tobytailor commented Oct 11, 2011

function(i,s,t,j,e){i=i.split(' ');t=[];t.o=t.pop;t.u=t.push;for(j=0;e=i[j++];)+e==e?t.u(e*1):eval('s=t.o(),t.u(t.o()'+e+'s)');return t[0]}

@subzey

This comment has been minimized.

Copy link

subzey commented Oct 11, 2011

function(a,b){b=[];a.replace(/\S+/g,function(c){b.push(+c==c?c:eval((a=b.pop(),b.pop())+c+a))});return b[0]}

Optional illustrative image

@pvdz

This comment has been minimized.

Copy link

pvdz commented Oct 11, 2011

That's more like it. Well done :)

@peterjaric

This comment has been minimized.

Copy link
Owner Author

peterjaric commented Oct 11, 2011

Yay! @tobeytailor got it to just under tweet-size! Then @subzey cut it down/reimplemented it to 108 bytes! I'll be updating.

@tsaniel

This comment has been minimized.

Copy link

tsaniel commented Oct 11, 2011

Save some bytes.

function(a,b){return(b=[])[a.replace(/\S+/g,function(c){b.push(+c==c?c:eval(b.pop(a=b.pop())+c+a))}),0]}
@peterjaric

This comment has been minimized.

Copy link
Owner Author

peterjaric commented Oct 11, 2011

Great! I will update later. (Edit: done)

If 0 wasn't allowed as an operand, we could shorten it to

function(a,b){return(b=[])[a.replace(/\S+/g,function(c){b.push(+c||eval(b.pop(a=b.pop())+c+a))}),0]}

But it is...

@peterjaric

This comment has been minimized.

Copy link
Owner Author

peterjaric commented Oct 12, 2011

Using the ideas outlined above, the eval-less version now is under 140 bytes too (138 bytes):

function(a,b){return(b=[])[a.replace(/\S+/g,function(c,d){b.push(+c==c?+c:(d=b.pop(a=b.pop()),c=='+'?d+a:c=='-'?d-a:c=='*'?d*a:d/a))}),0]}

Thanks everyone.

@tsaniel

This comment has been minimized.

Copy link

tsaniel commented Oct 12, 2011

Save 2 bytes.

function(a,b){return(b=[])[a.replace(/\S+/g,function(c,d){b.push(+c==c?+c:{'+':(d=b.pop(a=b.pop()))+a,'-':d-a,'*':d*a,'/':d/a}[c])}),0]}

or this

function(a,b){return(b=[])[a.replace(/\S+/g,function(c,d){b.push(+c==c?+c:[(d=b.pop(a=b.pop()))+a,d-a,d*a,d/a]['+-*/'.indexOf(c)])}),0]}
@peterjaric

This comment has been minimized.

Copy link
Owner Author

peterjaric commented Oct 12, 2011

I'm learning something in every comment. Great work, @tsaniel!

@jimmywarting

This comment has been minimized.

Copy link

jimmywarting commented Apr 14, 2019

With ES6 you can

  • Lift d variable to the top so you can ignore one (, )
    With the use of => function you can also remove all return and make one liner by omitting {} that makes it return the first thing
(a,b,d)=>(b=[])[a.replace(/\S+/g,c=>b.push(+c==c?+c:{'+':(d=b.pop(a=b.pop()))+a,'-':d-a,'*':d*a,'/':d/a}[c])),0]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.