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 ;)