[Java] Evaluate reverse polish notation in constant space

Yes it is possible, yes it took me one full day research included, but the RPN can be evaluated in O(N) time and O(1) space, sacrificing the input in the process.

There are some key points to this but let's start with the general idea. To get the algorithm down from O(N) space (the stack) to O(1) we cannot use additional costly structures; luckily our input is all we need, if we are allowed to destroy it while processing. This is often the case with this type of optimization, an in place algorithm.

Consider the following expression corresponding to 3 - (4 x 5): 3 4 5 x -

For RPN reading from left to right, the operator always follows the two operands it should work on and once we evaluated an expression, we no longer need the original data but only the result, so 3 4 5 x - can be rewritten as 3 20 -

We can therefore recycle the processed space (always 3 elements, two operands and an operator) in the input structure to somehow track which elements should we process next. This means we need to point to the next unprocessed element in the sequence, so that the next operator can retrieve its two operands as if they were adjacent.

3 4 5 x - should become 3 goto:0 20 null - so that when we process the minus operator, we know 20 is the second operand and the item in position 0 is the first operand.

Where and how do we store this information? To keep life easy, we can replace the processed operator with the result of the operation, so the next operator can retrieve its second operand (RPN left to right!) quickly as it will always be there at the index before the operator.
The first operand instead will either be at two indexes before the operator or at the position designated by the pointer found there, something like:

3 null goto:0 20 -

Now, how do we know if we have a pointer? We place at the index preceding it a special marker (eg a null value), so that we know whatever element follows it is not a value but a pointer to a value.

Some ideas here:
- We could put both marker and pointer together as a string, but then we would need to perform a substring operation to retrieve the pointer index, and although on the overall complexity this should not have a big impact, it will still make the algorithm run slower O(N x M) where M is the cost of the substring operation; if M << N, it could be considered negligible.
- Actually, the first version I tried had the marker following the pointer:

3 0 goto 20 -

But I could not make it work having issues with the correct handling of pointer operations and out of bounds checks, so I was stuck there until I remembered Google exists and I found this awesome post that explained the same algorithm BUT the marker is BEFORE the pointer! And now life smiles :) I still think it should work the other way as well, but I have to finish testing.

Last thing to note, we cannot afford the need to follow multiple pointers, otherwise the time would increase to O(N^2) territory because we might need to follow many pointers in a row to find the information we need. To keep this in check, when we update the values to maintain the new pointers, if we determine that we would be pointing to a pointer, we point directly to its value instead. We therefore create a single jump that keeps the retrieval operation in constant time. Eg a situation like:

3 goto0 goto1 20 -

With two pointer jumps, has to be instead:

3 goto0 goto0 20 - 

With a single pointer jump. You can't really miss this because the multiple pointer jump forces you to use a loop in the code, and a loop inside a loop is always a warning for potential square time complexity.

tl;dr, we can now process the input in one pass with no extra space. Everytime we encounter an operator, we:
1) retrieve second operand at the index before
2) retrieve first operand at two indexes before OR at the index specified by the pointer at that location
3) store the result of the operation in place of the operator
4) update the pointers

To update the pointers:

- if we were not a pointer (no null preceding us), set us as marker and point to the element before us (set the next element to us - 1). This could be a value or a pointer, but in either case we are fine. Do this if we are the very first element as well, otherwise we will end up with an IndexOutOfBounds exception when we try to access the item at index -1. This means we create a useless pointer but luckily we will never access it if the expression is well formed
- if we were a pointer, retrieve the value at the location and check the element before us. If the item preceding it (us - 2) is a pointer, copy the pointer value, otherwise if it is not a pointer, point to it

Now in the main function that parses the input one item at a time, the main difference is the order and way of retrieving the operands. Always go with the SECOND operand first, this can always be retrieved directly at index - 1. Then get the FIRST operand, this need to call the helper function to retrieve the correct value and update the pointers too; no need to use this function twice.

You can check the implementation on my Gist for evaluateRPNinPlace along with some test cases in RPNJTests.

You can find here the code to convert an expression to reverse polish notation.