RPN vs AOS: a new look into the past?

[Thomas Klemm]

(01-03-2016 12:23 PM)Ángel Martin Wrote:  how about an HP-41C program that RUNS AOS code?

You can implement the shunting-yard algorithm manually using a programmable HP-calculator.
We can use the ordinary stack for the data and the program to register the operations. To simulate the operation-stack we must make sure that new entries are added at the top.

Let's have a look at two examples to see how this works.

Example: 1+2*3

We start with a clear program memory (or just an END in case of the HP-41C).
Then we enter 1.
To enter + we switch to program-mode, enter the operation, switch back and use RTN to make sure, that we're at the begin.
Next step is to enter 2.
We switch back to program-mode, enter * at the begin and switch back. Always make sure to return to begin of the program after you left program-mode.
Last thing is to enter 3.

We end up with this stack:

1 2 3

and this program:

Code:

*
+

Now you can run the program to get: 7

To illustrate the use of parentheses let's have a look at the next example: 3*(4+5)

When we encounter a left parenthesis ( we add a RTN instruction.
However for the a right parenthesis ) we run the program. Then we remove the steps until the first RTN.

Thus we end up with this stack:

3 4 5

and this program:

Code:

+
RTN
*

When we run the program and remove the executed steps we end up with this stack:

3 9

and this program:

Code:

*

If we run the program we end up with: 27

It get's a little more complicated when dealing with operator-precedence and calling functions. I recommend to read the details in the wikipedia article.

The last example is taken from the mentioned TI-brochure: (5/(7-2/9)+4)*3+1

There's nothing new until the first closing parentheses.
We end up with this stack:

5 7 2 9

and this program:

Code:

/
-
RTN
/
RTN

We can now run the program and remove the steps to the first RTN statement.
This is the stack:

5 7-2/9

And this is the program:

Code:

/
RTN

Now since the precedence of the next operator + is lower than that of / we run the program before adding + to the program.
Thus we get this stack:

5/(7-2/9)

and this program:

Code:

+

The next step is to enter 4 to the stack and run the program when we encounter ).
This is what we have now on the stack:

5/(7-2/9)+4

The program register is empty. We add * and 3 and run the program since the precedence of + is lower than that of *.
As a last step we add +, enter 1 and run the program to get:

(5/(7-2/9)+4)*3+1

You may have noticed that I've rearranged the expression a little. Otherwise we would have run into a stack-overflow.

Cheers
Thomas