Javascript RPN Calculator

RPN (Reverse Polish Notation) is a mathematical notation wherein every operator follows all of its operands, which was designed to reduce computer memory access and utilize the stack to evaluate expressions.

The syntax looks like:

rpn("3 3 +"); // => 3 + 3 => 6
rpn("2 2 + 3 *"); // => (2 + 2) * 3 => 12
rpn("2 2 3 + *"); // => (2 + 3) * 2 => 10 
rpn("2 2 3 3 / * /"); // => ((3 / 3) * 2) / 2 => 1;

A typical interview question would be to implement a RPN calculator since it is simple enough to resolve in less than an hour and it tests our ability to notice a problem that cries out for a stack based solution.
It also tests our absence from the “Introduction to Algorithms” course in college.

Obviously there are other algorithms to implement RPN, such as recursion, but using a stack will be more efficient: a stack will take O(n) times rather than O(n2) for recursion.

Of course, this has very little to do with UI programing, but we are dealing with interview questions.

The way to implement it is to iterate over our expression, add each member to a stack, and when the member is an operation, calculate the previous 2 members with that operator.

A javascript implementation can look like:

function rpn( input ) {
  var ar = input.split( /\s+/ ), st = [], token;
  while( token = ar.shift() ) { 
    if ( token == +token ) { // numeric
      st.push( token );
    } else {
      var n2 = st.pop(), n1 = st.pop();
      st.push( eval( n1 + token + ' ' + n2 ) );
    }
  }
  return st.pop();
}

We can later add validation, so our final version looks like:

function rpn( input ) {
  var ar = input.split( /\s+/ ), st = [], token;
  while( token = ar.shift() ) { 
    if ( token == +token ) {
      st.push( token );
    } else {
      var n2 = st.pop(), n1 = st.pop();
      var re = /^[\+\-\/\*]$/;
      if( n1 != +n1 || n2 != +n2 || !re.test( token ) ) {
        throw new Error( 'Invalid expression: ' + input );
      }
      st.push( eval( n1 + token + ' ' + n2 ) );
    }
  }
  if( st.length !== 1 ) {
    throw new Error( 'Invalid expression: ' + input );
  }
  return st.pop();
}

This post is for self reference 😉

Lead UI Engineer and a Software Architect.
Over 12 years of professional experience, writing complex web applications, and still learning something new every day.
Currently working for Okta in San Francisco

Twitter LinkedIn Google+ 

One thought on “Javascript RPN Calculator

  1. Brahmi Sonia

    Hi Uzi,
    Thanks for the post, Is there any reason why you’re adding a string with a space at that line? :

    st.push( eval( n1 + token + ‘ ‘ + n2 ) );

    I tried removing it for a single simple use case and it didn’t seem to break the code, am I missing something?

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *