Write a program to evaluate arithmetic expression using stack organized computer with 0-address instructions. X = (A-B) * (((C - D * E) / F) / G)

In a stack organized computer with zero-address instructions, the arithmetic instructions have no address field. They take their operands from the top two items of the stack and push the result back. Only PUSH and POP name a memory address. So we first write the expression in reverse Polish notation (RPN), where each operator comes after its operands.

The expression is $X = (A-B) * (((C - D * E) / F) / G)$. We convert it by taking the innermost bracket first.

$$A - B \rightarrow AB-$$

$$D * E \rightarrow DE*$$

$$C - DE \rightarrow CDE-$$

$$(C-DE)/F \rightarrow CDE-F/$$

$$((C-DE)/F)/G \rightarrow CDE-F/G/$$

The last operation is the product of the two big brackets.

$$AB-;CDE*-F/G/;*$$

I checked this RPN with a small program. Each letter of the string becomes a PUSH, and each operator becomes one instruction. The program is:

PUSH A      ; stack: A
PUSH B      ; stack: A, B
SUB         ; stack: (A-B)
PUSH C      ; stack: (A-B), C
PUSH D      ; stack: (A-B), C, D
PUSH E      ; stack: (A-B), C, D, E
MUL         ; stack: (A-B), C, (D*E)
SUB         ; stack: (A-B), (C-D*E)
PUSH F      ; stack: (A-B), (C-D*E), F
DIV         ; stack: (A-B), ((C-D*E)/F)
PUSH G      ; stack: (A-B), ((C-D*E)/F), G
DIV         ; stack: (A-B), (((C-D*E)/F)/G)
MUL         ; stack: (A-B)*(((C-D*E)/F)/G)
POP X       ; X <- result

Each SUB, DIV and MUL takes the top item as the second operand and the item below it as the first operand. For example, at the first SUB the top is $DE$ and below it is $C$, so the result is $C - DE$ and not the reverse.

Why the order matters

The operands of a subtraction or a division must be pushed in the right order. The first operand goes in first, so that it lies below the second operand. If $F$ were pushed before the bracket $C - DE$ is complete, the division would give $F/(C-DE)$ instead of the intended one. The RPN form takes care of this automatically.

Check with numbers

Let $A=10, B=4, C=20, D=2, E=3, F=7, G=2$. The stack program works as follows.

$$A-B = 10-4 = 6$$

$$DE = 6,\quad C-DE = 20-6 = 14$$

$$14/F = 14/7 = 2,\quad 2/G = 2/2 = 1$$

$$6 \times 1 = 6$$

The direct calculation of $(10-4)(((20-23)/7)/2)$ also gives 6, so the program is right.

The program has 14 instructions, of which 7 are PUSH, one is POP and 6 are arithmetic. The arithmetic instructions are short because they need no address. The stack never holds more than 4 items at once. This is how a stack computer runs an expression without using any general registers.

Therefore the required program is the 14 instruction sequence given above, ending with POP X. Reading it again from the top, the first three lines compute the value of $(A-B)$, the next nine lines compute the big bracket on the right, and the last MUL joins them.