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(n^{2}) for recursion.

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

Continue reading