A useful feature that is included in the CPU of most computers is a stack or **last in first
out** (LIFO) list. A stack is a storage device that stores information in such a manner that the
item stored last is the first item retrieved. The operation of a stack can be compared to a stack
of trays. The last tray placed on top of the stack is the first to be taken off.

The register that holds the address for the stack is called a stack pointer (SP) because its value always points at the top item in stack.

The two operation of stack are the insertion and deletion of items.

- The operation of insertion is called
**PUSH**. - The operation of deletion is called
**POP.**

### Register Stack :

The stack pointer
register SP contains a binary number whose value is equal to the address of the word that is
currently on top of the stack. In a 64-word stack, the stack pointer contains 6 bits because
2^{6}
=64.

The one bit register **Full** is set to 1 when the stack is full, and the one-bit register **EMTY**
is set to 1 when the stack is empty of items.

The **push** operation is implemented with the following sequence of micro-operation.

SP ←SP + 1 (Increment stack pointer)M(SP) ← DR (Write item on top of the stack)if (sp=0) then (Full ← 1) (Check if stack is full)Emty ← 0 ( Marked the stack not empty)

The **pop** operation is implemented with the following sequence of micro-operation.

DR← M[SP] Read item from the top of stackSP ← SP-1 Decrement stack Pointerif( SP=0) then (Emty ← 1) Check if stack is emptyFULL ← 0 Mark the stack not full

### Reverse Polish Notation (Postfix Notation):

A*B+C*D

that arithmetic expressions can be represented in prefix notation . This representation, often referred to as Polish notation, places the operator before the operands. The postfix notation, referred to as reverse Polish notation (RPN), places the operator after the operands. The following examples demonstrate the three representations:

A+ B Infix notation

+ AB Prefix or Polish notation

AB + Postfix or reverse Polish notation

### Evaluation of Arithmetic Expressions:

Reverse Polish notation, combined with a stack arrangement of registers, is the most efficient way known for evaluating arithmetic expressions.

The following numerical example shows the evaluation of arthematic expressions. Consider the arithmetic expression

(3 * 4) + (5 * 6)

In reverse Polish notation, it is expressed as

34*56*+

Now consider the stack operation. Each box represents one stack operation and the arrow always points to the top of the stack. Scanning the expression from left to right, we encounter two operands. First the number 3 is pushed into the stack, then the number 4. The next symbol is the multiplication operator *. This causes a multiplication of the two topmost items in the stack. The stack is then popped and the product is placed on top of the stack, replacing the two original operands. Next we encounter the two operands 5 and 6, so they are pushed into the stack. The stack operation that results from the next * replaces these two numbers by their product. The last operation causes an arithmetic addition of the two topmost numbers in the stack to produce the final result of 42.

## 0 comments:

## Post a Comment

Note: only a member of this blog may post a comment.