Data Structures: Lesson 4 Alaa Aljanaby

Data Structures: Lesson 4 Alaa Aljanaby

Stacks

Data: special type of list in which all data processing activity occurs at one end called top. Data processed as LIFO.

Operation: Push, Pop, IsEmty, IsFull // (arrays)

Implementation

Array Implementation

One pointer: top

Empty → top =-1

Full → top = max-1

#define max 100

class stack {

private:

int s[max];

int top;

public:

stack(){top = -1};

void push(int item);

void pop();

bool isempty();

bool isfull();

};

Push:

Top++; if not full;

S[top] =item;

Pop:

Return S[top]; if not empty

Top--;

Linked list Implementation

Empty → top = null

Add(push) and delete(pop) from the beginning.

top

top

top

class stack{

private:

node*top;

public:

stack(){top = null;}

void push(int item);

int pop();

void print();

bool isempty();

};

push:

node* x=new node(item);

x->setnext(top);

top=x;

pop:

int x=0;

if ( ! isempty() )

{

x=top->getdata();

node* p=top;

top = top->getnext();

delete p;

}

return x;

main()

{ stack s;

s.push(1);

s.push(2);

s.pop();

s.pop();

}

Parsing & Evaluating Arithmetic Expression

Parsing

The process of checking the syntax

Infix, Postfix, & Prefix Notion:

Infix: usual algebraic expression is often termed using infix notation, which may require ( ) specifying the desired order of operations.

Postfix: the operator is placed directly after the two operands to which it applies. ( no need to parauthesis)

Ex:

A/B+C → A B / C +

A/(B+C) → ABC+/

Algorithm for Human

1. Completely parenthesis the infix exp to specify the order of all operations.
2. Move each operator to the space held by its corresponding right parenthesis.
3. Remove all parenthesis.

Ex: A / B^C + D * E – A * C

1 ((A / ( B^C ) ) + ( D * E ) -( A * C ) )

2 A B C ^ / D E * + A C * -

Ex: A / B ^ C - ( D * E – A * C )

1 ((A / (B^C)) – ((D*E)-(A*C)))

2 A B C ^ / D E * A C * - -

The Prefix

The operator is placed directly before the two operands to which it applies.

Ex:

A/B+C → +/ ABC

A/(B+C) → /A+BC

Algorithm for Human

Same as for postfix, but move each operator to the corresponding left parenthesis.

Ex: A / B^C + D * E – A * C

3 ((A / ( B^C ) ) + ( D * E ) -( A * C ) )

4 - + / A ^B C * D E * A C

Ex: A / B ^ C - ( D * E – A * C )

The importance of postfix & prefix is that they are completely free of parenthesis

Converting Infix Exp. To postfix

• Infix expression is stored in a queue
• Result (postfix) exp. is stored in a queue
• Any infix expression contains operands, operator, and parenthesis and special endtoken, which delimit the end of the infix exp.
• Stack the push the operators, ( ), and #
• Define priority function, which return the precedence.

Token *, /,+,-,(,),#

Precedence 2,2,1,1,3,undef,0

Algorithm

1. Initialize the stack by pushing #

2. Dequeue the next token from the infix queue

3. Test the token

3.1 if the token is one operand, enqueue it on the postfix exp.

3.2 if the token is left hand parenthesis, push it on the stack.

3.3 if the token is right hand parenthesis, pop all entries from operator stack and enqueue them on postfix queue until left hand paranthesis is poped.

3.4 if the token is end token, pop all entries and enqueue them on the postfix exp.

3.5 otherwise, pop from the stack, and enqueue on the postfix queue all operators whose priorty >= the priority of the token and then push the token.

4. Repeat 2, 3 until token = endtoken.

Ex: A* B + ( C – D ) / E #

Evaluate the postfix Exp:

1. Repatedly get token from postfix expression(queue)
2. If the token is an operand : Push the value to the stack
3. If it is an operator : Pop 2 values, evalute, push the result.

Ex : AB*CD-E/+ A=5, B=3, C=8, D=6, E=2

1

Lesson 4: Stacks