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 😉

2 thoughts 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
  2. exemplification definition

    The broad pectrum of dances includes contemporary,
    classical, ballroom, street, jazz, hip-hop, muaical theatre and all of their sub-genres.
    Ouija Boards have been about for ages, yet they may be strill
    beig confused for som a sort of portala communication devise
    that alows uss to communicate with our passed family members or spirits we don. The theater was built by Torbay Council as part
    of its complete redevelopment of Princess Gardens annd Princess Pier.

    Reply

Leave a Reply

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