Friday, September 20, 2013

STACKS IN DS

                              Stacks:

A stack is a basic data structure, where insertion and deletion of items takes place at one end called top of the stack. The basic concept can be illustrated by thinking of your data as a stack of plates or books where you can only take the top item off the stack in order to remove things from it.

A stack is also called a LIFO (Last In First Out) to demonstrate the way it accesses data. There are basically three operations that can be performed on stacks . They are 1) inserting an item into a stack (push). 2) deleting an item from the stack (pop). 3) displaying the contents of the stack(pip).

Algo for push and pop:

Push:

PUSH(STACK,TOP,MAXSTK,ITEM)
1: If TOP=MAXSTK,then print OVERFLOW and return.

2:Set TOP=TOP+1
3:Set STACK

[TOP]=ITEM. 

4:Return

Pop:

POP(STACK,TOP,ITEM)
1:If TOP=0 then print UNDERFLOW and return.
2:Set ITEM=STACK[TOP].
3:Set TOP=TOP-1.
4:Retun

NOTATIONS IN STACK:

Firstly, we deal with expressions in infix notation


2 + 5
where the operators (e.g. +, *) are written between the operands (e.q, 2 and 5). Writing the operators after the operands gives a postfix expression 2 and 5 are called operands, and the '+' is operator. The above arithmetic expression is called infix, since the operator is in between operands. The expression
2 5 +

Writing the operators before the operands gives a prefix expression

+2 5

Transforming Infix expressions into Postfix expression:

1. Print operands as they arrive.
2. If the stack is empty or contains a left parenthesis on top, push the incoming operator onto the stack.
3. If the incoming symbol is a left parenthesis, push it on the stack.
4. If the incoming symbol is a right parenthesis, pop the stack and print the operators until you see a left parenthesis. Discard the pair of parentheses.
5. If the incoming symbol has higher precedence than the top of the stack, push it on the stack.
6. If the incoming symbol has equal precedence with the top of the stack, use association. If the association is left to right, pop and print the top of the stack and then push the incoming operator. If the association is right to left, push the incoming operator.
7. If the incoming symbol has lower precedence than the symbol on the top of the stack, pop the stack and print the top operator. Then test the incoming operator against the new top of stack.
8. At the end of the expression, pop and print all operators on the stack. (No parentheses should remain.)
EXAMPLE:
A * (B + C) becomes A B C + *
A subexpression in parentheses must be done before the rest of the expression.

current symboloperator stackpostfix string
1
AA
2
**A
3
(* (A B
4
B* (A B
5
+* ( +A B
6
C* ( +A B C
7
)*A B C +
8
A B C + *

0 comments:

Post a Comment