Stack Organization, Reverse Polish Notation, and Instruction Formats

What is a Stack? (In Simple Words)

A Stack is a storage structure that follows the LIFO (Last-In, First-Out) rule.

• The last item placed on top is always the first item removed!
• A CPU register called the Stack Pointer (SP) keeps track of the memory address of the topmost item.

💡 Real-Life Indian Student Analogy:
Think of a stack of steel plates (thaalis) at a wedding dinner:

• The caterer puts clean plates on top of the stack.
• Guests pick plates from the top.
• You cannot pull a plate out from the bottom without knocking the pile down! That is LIFO.

1. Register Stack Organization and PUSH / POP

A 64-word hardware stack uses a 6-bit Stack Pointer (SP) (since 2⁶ = 64) and two status flags: FULL and EMPTY.

2. Reverse Polish Notation (RPN / Postfix)

Humans write math formulas in Infix notation (operators between numbers).

• Infix: (A + B) × (C + D)
• Computers must evaluate brackets and operator precedence (BODMAS), which slows them down.
• In Postfix (Reverse Polish Notation), operators come after the numbers:
  A B + C D + ×
• In Postfix, brackets are completely eliminated!

How the CPU Evaluates RPN Using a Stack:

1. Read the expression from left to right.
2. If you see a number/variable (A, B, C, D) → PUSH it onto the stack.
3. If you see an operator (+, ×) → POP the top two items, perform the math, and PUSH the result back onto the stack!

3. Four Instruction Formats

How many memory addresses can fit inside a single instruction? Computers are classified into 4 instruction types based on this:

Let’s evaluate: X = (A + B) × (C + D) using all 4 formats:

1. Three-Address Instructions

Specifies two source operands and one destination register.

ADD  R1, A, B     ; R1 ← M[A] + M[B]
ADD  R2, C, D     ; R2 ← M[C] + M[D]
MUL  X,  R1, R2   ; M[X] ← R1 * R2

• Advantage: Program is very short (only 3 instructions).
• Disadvantage: Each instruction needs many bits to store 3 full addresses.

2. Two-Address Instructions

One address serves as both an input and the final answer holder.

MOV  R1, A        ; R1 ← M[A]
ADD  R1, B        ; R1 ← R1 + M[B]
MOV  R2, C        ; R2 ← M[C]
ADD  R2, D        ; R2 ← R2 + M[D]
MUL  R1, R2       ; R1 ← R1 * R2
MOV  X,  R1       ; M[X] ← R1

3. One-Address Instructions (Accumulator Architecture)

All math automatically uses the CPU Accumulator (AC) register.

LOAD  A           ; AC ← M[A]
ADD   B           ; AC ← AC + M[B]
STORE T           ; Save temporary answer in RAM T
LOAD  C           ; AC ← M[C]
ADD   D           ; AC ← AC + M[D]
MUL   T           ; AC ← AC * M[T]
STORE X           ; M[X] ← AC

4. Zero-Address Instructions (Stack Architecture)

Numbers are popped directly from the stack, and the result is pushed back. No address field is needed in arithmetic instructions!

PUSH  A           ; Top of Stack ← M[A]
PUSH  B           ; Top of Stack ← M[B]
ADD               ; Pops A & B, pushes (A + B)
PUSH  C           ; Top of Stack ← M[C]
PUSH  D           ; Top of Stack ← M[D]
ADD               ; Pops C & D, pushes (C + D)
MUL               ; Pops both sums, pushes product
POP   X           ; M[X] ← Top of Stack

💡 DAVV Exam Preparation Tips

5-Mark Question: “Convert the infix expression (A + B × C) / (D - E) into Reverse Polish Notation (RPN) and show stack steps.”

• Follow BODMAS precedence: B × C happens first, then + A.
• Correct Postfix (RPN): A B C × + D E - /
• Show the stack status after each step (pushing variables and popping on operators).

10-Mark Question: “Evaluate the arithmetic statement X = (A × B) + (C × D) using: (a) Three-Address, (b) Two-Address, (c) One-Address, and (d) Zero-Address instructions.”

• Write out the assembly program for each of the 4 formats clearly.
• Explain the trade-off: 3-address has fewer instructions but larger word sizes, while 0-address instructions are tiny but need more PUSH/POP steps.