Transcript Steps current symbol intermediate str stack

The Stack
• •Data structure deals with the study of how data is
organized in memory and how efficiently data can be
retrieved and manipulated.
• •Data structures allows programmers to write efficient
programs. data is efficiently retrieved ,manipulated and
organized in memory.
• •Data structures(D.S) can be classified as
1.primitive D.S
2.non primitive D.S
Primitive D.S
• •D.S that are manipulated directly by machine
instructions.
Ex: integers, floating point, characters and pointers.
Non primitive D.S
• •D.S that cannot be manipulated directly by machine
instructions.
ex: arrays, structures, stacks, queues, linked lists, files.
• •They are further classified as
1.linear D.S
D.S that show logical relationship between elements as
sequential/linear fashion.Eg.stacks, queues, linked lists.
2.non linear D.S: ex: trees, graphs, files
• •Pointers are used extensively in implementing data
structures.
The Stack:
• •Special type of D.S where items are inserted at one end
called the top of stack and deleted from the same end.
• •Last item inserted will be on the top of stack.
• •Last item inserted will be the first one to be deleted. Hence
it is called Last In First Out(LIFO) or First In Last Out(FILO).
Various operations on stacks
1. 5.Insert an item into the stack.(Push)
2. 6.Delete an item from the stack.(pop)
3. 7.Display the contents of the stack.
An example with pictorial representation of stack
• •Consider a stack S which is initially empty.
• •Let the maximum size of stack be 8.
• •top points to the top of stack. Since stack is
empty, it is set to -1 initially.
• •Now lets insert A,B,C,D to stack. As an item is
inserted, top is incremented.
top=-1
top
top
top
top
A
After A
B
A
After B
C
B
A
After C
D
C
B
A
After D
Now, lets perform 2 pop operations
• •Pop removes the top item from stack and returns it.
• •After the item is removed, top is decremented.
top
top
C
B
A
After 1st pop
B
A
After 2nd pop
top
L
K
B
A
After inserting K and L
Primitive stack operations
1. 1.push( ):
Increments top and adds item to the stack at top.
push(S,A)– S is the stack and A is the item to be inserted.
Displays message “stack full” when stack is full.i.e In the
previous stack, if we try to insert 9th element.
1. 3.pop( ):
Removes the top item from stack and returns it.
int i=pop(S); decrements top.
Displays message “stack empty” if we try to pop when
there is no element in stack.i.e when top==-1
3. empty( ):
Returns true if stack is empty, false otherwise.
boolean empty(S);
4. display( ):
display contents of stack.
Applications of stack
1.Conversion of expressions
when we write mathematical expressions in a program, we
use infix expressions. This will be converted into
equivalent m/c instructions using stacks.
2. Evaluation of expressions
Arithmetic expressions in the form of either prefix or
postfix can be easily evaluated using stacks.
3.Recursion
stacks are used extensively in recursion.
4.Other applications
Find whether a string is palindrome or not
To check whether a given expression is valid or not.
When fun2() is being called all the information pertained to fun1() (flow, flags, return
address, etc.,) will be pushed into the stack. Similarly, when fun3() is being called
information pertained to the function fun2() will be pushed into the stack. So, when
fun3() returns the information set related to fun2() will be popped out first, then
information pertained to fun1() (when fun2() returns).
Another example is in the case of keeping the history while browsing the internet. When
hyperlink is clicked, information related to current page is pushed onto stack and control
goes to the clicked page. While returning back to previous page, stack is popped and
information of the previous page is obtained
Representing stacks in c
To implement a stack, we need to have
1. 1.An array to hold the elements of stack.
2. 2.An integer variable to indicate the top of stack.
Using these we need to write functions for push, pop and
display.
Stacks can be implemented in c by either
1. 3.Without using structures.
2. 4.Using structures.(most preferred)
• •No matter in what way the stack is implemented, it
should have an array and integer variable.
Implementing stack without structure
#include<stdio.h>
#define STACK_SIZE 5 //max size of stack
Void main()
{
int top; //top of stack;
int s[STACK_SIZE]; //hold stack elements
int item; //item to be inserted
int del_item; //popped item
int choice; //user choice
top=-1; //stack empty initially
for(; ;) //loop until exit
{
printf(“enter your choice”);
printf(“1.push 2.pop 3.display 4.exit”);
scanf(“%d”,&choice);
}
switch(choice)
{
case 1: printf(“enter item to be pushed”);
scanf(“%d”, &item);
push(item,&top,s); //call push function
break;
case 2:del_item=pop(&top, s);
printf(“deleted item is %d”,del_item);
break;
case 3:display(top,s);
break;
default: exit(0);
} //end of switch
} //end of for
} //end of main
/*push function*/
void push(int item, int *top, int s[])
{
if(*top==STACK_SIZE-1)
{
printf(“stack full”);
exit(0);
}
(*top)++; //increment top
s[*top]=item; //insert the item
}
/*pop*/
int pop(int *top, int s[])
{
int del_item;
if(*top==-1)
{
printf(“stack empty”);
return(0);
}
else
{
del_item=s[*top]; //remove top element
(*top)--; //decrement top
return(del_item);
}
}
void display(int top, int s[])
{
int i;
if(top==-1)
{
printf(“stack empty”);
exit(0);
}
printf(“contents is”);
for(i=0;i<=t;i++) //start from bottom to top
printf(“%d”, s[i]);
}
• •In push and pop address of top is passed because top is
local to main and we want to update top when item is
pushed or popped.
• •In display, we aren't changing the top. But its value is used
to traverse the stack from bottom to top.hence address
need not be passed.
Implementing stack using structure
#include<stdio.h>
#define STACK_SIZE 5 //max size of stack
struct stack
{
int top;
int sarray[STACK_SIZE];
};
typedef struct stack STACK;
Void main()
{
int item, choice; //item to be inserted and user choice
STACK s; //stack variable
s.top=-1; //stack empty initially
for(; ;) //loop until exit
{
printf(“enter your choice”);
printf(“1.push 2.pop 3.display 4.exit”);
switch(choice)
{
case 1: printf(“enter item to be pushed”);
scanf(“%d”, &item);
push(item,&s); //call push function
break;
case 2:item=pop(&s);
if(item= = -1)
printf(“empty stack”);
else
printf(“deleted item is %d”,item);
break;
case 3:display(s);
break;
default: exit(0);
} //end of switch
} //end of for
} //end of main
/*push function*/
void push(int item, STACK *stck)
{
if(stck top==STACK_SIZE-1)
{
printf(“stack full”);
exit(0);
}
stck top++; //increment top
stck sarray[stck top]=item; //insert the item
}
/*pop*/
int pop(STACK *stck)
{
int del_item;
if(stck top= =-1)
return(-1);
else
{
del_item=stck sarray[stck top];//remove top element
stck top--; //decrement top
return(del_item);
}
}
void display(STACK stck)
{
int i;
if(stck.top==-1)
{
printf(“stack empty”);
exit(0);
}
printf(“contents is”);
for(i=0;i<=stck.top;i++) //start from bottom to top
printf(“%d”, stck.sarray[i]);
}
• •In push and pop address of stack ‘s’ is passed because ‘s’
is local to main and we want to update top when item is
pushed or popped.
• •In display, we aren't changing the top. But its value is used
to traverse the stack from bottom to top. hence address
need not be passed.
• •Display function can also be implemented by passing
address of structure or stack array because there is no
harm in passing address even if the value is not
changed.
void display(STACK *stck)
{
int i;
if(stck top==-1)
{
printf(“stack empty”);
exit(0);
}
printf(“contents is”);
for(i=0;i<=stck top;i++) //start from bottom to top
printf(“%d”, stck sarray[i]);
}
Checking whether given expression is valid or not using
stack
Checking an expression is nothing but checking
1.Whether there are equal number of right and left
parenthesis.
2.Whether right parenthesis is preceded by a matching left
parenthesis.
If both the above conditions are satisfied, expression is
valid.
Ex: ((A+B) or A+B( are not valid expressions because they
violate condition 1.
)a+b(-c violate condition 2.
(a+b)) violate both the conditions.
(a+b) * (c+d) is a valid expression.
Stacks can be used to check this.
Algorithm for checking expression
1. 1.Scan the expression from left to right.
2. 3.Whenever a scope opener( ‘(‘,’{‘,’[‘ ) is encountered
while scanning the expression, it is pushed to stack.
3. 5.Whenever as scope ender( ‘)’, ‘}’, ‘]’) is encountered,
the stack is examined. If stack is empty, scope ender
does not have a matching opener and hence string is
invalid. If stack is non empty, we pop the stack and
check whether the popped item corresponds to scope
ender. If a match occurs, we continue. If it does not, the
string is invalid.
4. When the end of string is reached, the stack must be
empty; otherwise 1 or more scopes have been opened
which have not been closed and string is invalid.
Ex1:(a+b) * (c+d
Ex2:(a+b)*c+d)
(
(
(
push ‘(‘
(a+b)
Pop ‘(‘ since
there is ‘)’ &
continue
(a+b) *(
Push ‘(‘
(
(a+b) *(c+d
End of string reached but
stack not empty. Hence
invalid
(
(
push ‘(‘
(a+b)
pop‘(‘ and
continue
(a+b)*c+d)
Stack empty when ‘)’
encountered.hence invalid
Ex3: (a+b)*({c*d)
(
(
(
push ‘(‘
{
(
(a+b)*({
push ‘{ and
continue‘
(a+b)
pop‘(‘ and
continue
(a+b)*(
push‘(‘ and
continue
{
(
(a+b)*({c*d)
No match between closing scope ‘)’ and
opening scope ‘{‘. Hence invalid.
Ex4: (a+{b*c}+(c*d))
{
(
(
(
push ‘(‘ and
continue
(
(
(a+{b*c}+(
push ‘( and
continue‘
(a+{
push‘{‘ and
continue
(
(a+{b*c}
pop‘{‘ and
continue
(
(a+{b*c}+(c*d)
Pop ‘(‘
(a+{b*c}+(c*d))
Pop ‘(‘.
End of string and stack
empty. Hence valid
Checking for palindrome
• •Algorithm
• •Scan the string from left to right till the end and push
every char you encounter during the scan to the stack.
• •Rescan the string left to right till end and do the
following for every char you encounter during scan. Pop
one char and compare current char with the popped
one.If no match report immediately non palindrome
other wise proceed to the next char.
Infix, postfix, prefix expressions and stacks
Infix expression:
• •Operators will be between two operands.
ex: a+b*c, a+b*c+d, (a+b)*c, (a+b)*(c+d).
Postfix expressions
• •Operator follows two operands.
ab+, ab*, abc*+
Prefix expressions
• •Operators precedes two operands.
• •These expressions can be converted to other form. i.e
infix to prefix, infix to postfix and so on
Converting infix to postfix
• •infix can be converted to postfix by placing the operator
after two operands while scanning from left to right.
a+b ab+, a*b ab*
• •When there are multiple operators and parentheses,
precedence of operators comes into picture. Operations
with highest precedence is considered first for conversion
and converted part is considered as single unit(operand)
and process is continued.
• •Operations within the parenthesis is considered first for
conversion because parentheses have highest
precedence.
• •For operators, order precedence is given below
1.exponentiation($ or ^)
2.multiplication/division
3.addition
Ex1: a+b*c
Here * is having higher precedence than +. So * is considered
first which gives bc*. Now bc* is considered as a single unit.
i.e a + bc*. Here a and bc* are considered as separate units.
Finally converting the intermediate expression gives abc*+
Ex2:(a+b)*c
operation within parenthesis is considered first which gives ab+
. Now ab+ and c are 2 separate operands
i.e ab+ * c
Converting this intermediate expression will give ab+c*
Ex3: (a+b)*(c+d)
After converting first parenthesis we get ab+ *(c+d).
After converting 2nd parenthesis we get ab+ * cd+.
After converting the the above expression we get ab+cd+*
• •When operators with same precedence are scanned, the
order is assumed to be left to right, except in the case of
exponentiation, where the order is right to left.
Ex1: a+b+c
Here both the operators are + and have same precedence.
Hence considering from left to right we get ab+ + c.
converting this intermediate expression will give us ab+c+
Ex2: a$b$c
Here also $ have same precedence. In case of $, order is from
right to left. Hence considering from right we get
a $ bc$.
Now convert this intermediate expression. Hence we get abc$$
Ex3:a*b/c
* and / have same precedence. Order is from left to right. Hence
we ab* / c.
finally we get ab*c/
Converting infix with multiple operators to postfix
Ex1: a$b*c-d+e/f/(g+h)
1.a$b * c - d + e / f / gh+
ab$*c – d + e / f / gh+
2.ab$c* - d + e / f / gh+
3.ab$c*d- + e / f / gh+
4.ab$c*d- + ef/ / gh+
5.ab$c*d- + ef/ / gh+
6.ab$c*d- + ef/gh+/
7.ab$c*d-ef/gh+/+
Ex2: ((a+(b-c)*d)$e+f)
1.( ( a + bc- * d ) $ e + f )
2.( ( a + bc-d* ) $ e + f )
3.( abc-d*+ $ e + f )
4.abc-d*+e$ + f
5.abc-d*+e$f+
Converting infix to prefix
• •Infix can be converted to prefix by placing the operator
before two operands.
• •Precedence rules is same as in the case infix to postfix.
Ex:a+b +ab
a+b*c +a*bc
(a+b)*c *+ab
a+b-c -+abc
a*b/c /*abc
a$b$c $a$bc
(a+b)*(c+d) *+ab+cd
Converting infix with multiple operators to prefix
Ex1:((a+(b-c)*d)$e+f)
( ( a + -bc * d ) $ e + f )
( ( a + *-bcd ) $ e + f )
( +a*-bcd $ e + f )
( $+a*-bcde + f )
+$+a*-bcdef
Ex2:a-b/(c*d$e)
a - b / ( c * $de )
a - b / *c$de
a - /b*c$de
-a/b*c$de
Another method
a$b*c-d+e/f/(g+h)
1. 1.Put all implicit brackets.(According to precedence and
associativity)
2. 2.((((a$b)*c)-d)+((e/f)/(g+h)))
3. 3.Replace every ) with corresponding operator and
remove (
4. 4.ab$c*d-ef/gh+/+
5. Converting to prefix requires change of roles of ( and )
in step 3.
6. +-*$abcd//ef+gh
Evaluating postfix expression using stack
Steps:
1.Scan the postfix expression from left to right
2.If an operand is encountered, push it on to the stack.
3.If an operator is encountered, pop the top two elements
from the stack, perform the required operation based on
operator and push the result back on stack.
4.Perform this operation until end of expression is
reached.
5.At the end, stack contains the final result.
623+-382/+*2$3+
Symbol op1 op2 op1 operator op2 stack
66
2 6,2
3 6,2,3
+ 2 3 5 6,5
-6511
3 1,3
8 1,3,8
2 1,3,8,2
/ 8 2 4 1,3,4
+ 3 4 7 1,7
*1777
2 7,2
$ 7 2 49 49
3 49,3
+ 49 3 52 52
23+4*
Symbol op1 op2 op1 operator op2 stack
22
3 2,3
+2355
4 5,4
* 5 4 20 20
/*program to evaluate postfix expression*/
#include<stdio.h>
#include<math.h>
#include<string.h>
Struct stack
{
int top;
int items[15];
};
typedef struct stack STACK;
Void main()
{
int op1,op2,I,result;
char postfix[15], symbol;
STACK s;
s.top=-1;
Printf(“enter postfix expression”);
scanf(“%s”,postfix);
for(i=0;i<strlen(postfix);i++)
{
symbol=postfix[i];
if(isdigit(symbol)) // call isdigit function
push(symbol-’0’,&s);
else
{
op2=pop(&s);
op1=pop(&s);
result=op(symbol,op1,op2); //call op function
push(result,&s);
}
}
result =pop(&s);
Printf(“result is %d”,result);
}
/*function op for performing operation on op1 and op2*/
int op(char symbol, int opnd1, int opnd2)
{
switch(symbol)
{
case ‘+’: return(opnd1+opnd2);
break;
case ‘-’: return(opnd1-opnd2);
break;
case ‘*’: return(opnd1*opnd2);
break;
case ‘/’: return(opnd1/opnd2);
break;
case’$’
case ‘^’: return(pow(opnd1,opnd2));
}
}
Void push(int symb, STACK *stk) //push to stack
{
stk top++;
stk items[stk top]=symb;
}
Int pop(STACK *stk) //pop from stack
{
int item;
item=stk items[stk top--];
return item;
}
Int isdigit(char symb) //check symbol is digit or not
{
if(symb>=‘0’ && symb<=‘9’)
return 1;
else
return 0;
}
Converting infix to postfix
Steps: (add ‘(‘ to stack initially)
1.Scan the infix string from left to right.
2.If the symbol is operand, add it to postfix string.
3.Else
1. if current symbol is ‘)’, pop the stack until the first ‘(‘ is
encountered and add the popped elements to postfix string
except ‘(‘.
2.Compare the precedence of current symbol with the top of
stack. If the precedence of current symbol is higher, push it
to stack. Otherwise pop the stack until precedence of
current symbol is greater than the top of stack and add all
popped elements to postfix string and current symbol to
stack.
3.Repeat this process until end of infix string is reached.
4.At the end, pop whatever is remained in stack to postfix
string until ‘(‘.
Ex1: a+(b*c)
Steps current symbol postfix str stack
1aa
2+a+
3 ( a +(
4 b ab +(
5 * ab +(*
6 c abc +(*
7 ) abc* +
End of string
Now pop whatever is remained on top of stack and to
postfix string. Hence final postfix string is abc*+
Ex2:((a-(b+c))*d)$(e+f)
Steps current symbol postfix str stack
1. ( (
2. ( ((
3. a a ((
4. - a ((5. ( a ((-(
6. b ab ((-(
7. + ab ((-(+
8. c abc ((-(+
9. ) abc+ ((10. ) abc+- (
11. * abc+- (*
12. d abc+-d (*
Steps current symbol postfix str stack
13. ) abc+-d*
14. $ abc+-d* $
15. ( abc+-d* $(
16. e abc+-d*e $(
17. + abc+-d*e $(+
18. f abc+-d*ef $(+
19. ) abc+-d*ef+ $
End of string
Pop whatever is remained on stack and add to postfix
string.
abc+-d*ef+$
a*b+c*d+e*f
Steps current symbol postfix str stack
1. a a
2. * a *
3. b ab *
4. + ab* +
5. c ab*c +
6. * ab*c +*
7. d ab*cd +*
8. + ab*cd*+ +
9. e ab*cd*+e +
10. * ab*cd*+e +*
11. f ab*cd*+ef +*
End of string
Pop * and + from stack and add to postfix string :
ab*cd*+ef*+
Converting infix to prefix:
• •Reverse the given infix expression.
• •Convert the reversed expression to an intermediate form
using stack.( algorithm in the next slide)
• •Reverse the intermediate expression. This is the prefix of
the given infix expression.
Converting reversed infix expression to intermediate form:
Steps: (add ‘)’ to stack initially)
1.Scan the reversed infix string from left to right.
2.If the symbol is operand, add it to intermediate string.
3.Else
1. if current symbol is ‘(’, pop the stack until the first ‘)‘ is
encountered and add the popped elements to intermediate string
except ‘)‘.
4.if current symbol is an operator, compare the
precedence of current symbol with the top of stack. If the
precedence of current symbol is higher than or equal to,
push it to stack. Otherwise pop the stack until precedence
of current symbol is greater than top of stack and add all
popped elements to intermediate string and current
symbol to stack.
5.Repeat this process until end of reversed infix string is
reached.
6.At the end, pop whatever is remained in stack to
intermediate string until ‘)’.
Ex1:((a+(b-c)*d)$e+f)
Reversed infix expression: )f+e$)d*)c-b(+a((
Steps current symbol intermediate str stack
1. ) )
2. f f )
3. + f )+
4. e fe )+
5. $ fe )+$
6. ) fe )+$)
7. d fed )+$)
8. * fed )+$)*
1. 9. ) fed )+$)*)
2. 10. c fedc )+$)*)
3. 11. - fedc )+$)*)4. 12. b fedcb )+$)*)-
Steps current symbol intermediate str stack
13. ( fedcb- )+$)*
14. + fedcb- * )+$)+
15. a fedcb-*a )+$)+
16. ( fedcb-*a+ )+$
1. 17. ( fedcb-*a+$+
2. 18.End of string
• •Pop whatever is remained on stack and add to
intermediate string fedcb-*a+$+
• •After reversing the intermediate string, we get
+$+a*-bcdef , which is the prefix.
Ex2: a$b*c-d+e/f/(g+h)
Reversed infix expression: )h+g(/f/e+d-c*b$a
Steps current symbol intermediate str stack
1. ) )
2. h h )
3. + h )+
4. ( hg+
5. / hg+ /
6. f hg+f /
7. / hg+f //
8. e hg+fe //
1. 9. + hg+fe// +
2. 10. d hg+fe//d +
3. 11. - hg+fe//d +4. 12. c hg+fe//dc +-
Steps current symbol intermediate str stack
13. * hg+fe//dc +-*
14. b hg+fe//dcb +-*
15. $ hg+fe//dcb +-*$
1. 16. a hg+fe//dcba +-*$
2. 17.End of string
• •Pop whatever is remained on stack and add to
intermediate string hg+fe//dcba$*-+
• •After reversing the intermediate string, we get
+-*$abcd//ef+gh , which is the prefix.
Ex3: a-b/(c*d$e)
Reversed infix expression: )e$d*c(/b-a
Steps current symbol intermediate str stack
1. ) )
2. e e )
3. $ e )$
4. d ed )$
5. * ed$ )*
6. c ed$c )*
7. ( ed$c*
8. / ed$c* /
1. 9. b ed$c*b /
2. 10. - ed$c*b/ 3. 11. a ed$c*b/a 4. 12. end of string
Pop whatever is remained on stack to intermediate
string ed$c*b/aAfter reversing the intermediate string, we get
-a/b*c$de, which is the prefix expression