There is No Full Stop for Learning !!

Showing posts with label Stack. Show all posts

Tuesday, 6 September 2016

Multiple stacks in 1 Dimensional Array

#include<stdio.h>
#include<stdlib.h>
#define MAX 12

int stack[MAX];
int m=MAX, n;
int top[10], boundary[10];

void push(int i, int item )
{
if(top[i] == boundary[i+1])
{
printf("\nStack%d overflow", i);
}
else
{
top[i] = top[i] +1;
stack[top[i]] = item;
}
}
void pop(int i)
{
int item;
if(top[i] == boundary[i])
{
printf("\nStack%d underflow", i);
}
else
{
item = stack[top[i]];
printf("\nItem that got deleted from stack%d is %d", i, item);
top[i] = top[i] - 1;
}
}

void display(int i)
{
int j;
if(top[i] == boundary[i])
{
printf("\nStack%d is empty", i);
return;
}
else
{
printf("\n");
for(j=top[i]; j>=boundary[i]+1; j--)
printf("| %d |\n",stack[j]);
}
}

void main()
{
int ch, stackno, item,i;
printf("\nEnter the number of stacks: ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
top[i] = boundary[i] = (i*(m/n)) - 1;
printf("\ntop[%d] = %d and boundary[%d] = %d",i,top[i], i, boundary[i]);
}
boundary[i] = MAX-1;

while(1)
{
printf("\n\n~~~MENU~~~");
printf("\n1.Push operation");
printf("\n2.Pop operation");
printf("\n3.Display");
printf("\n4.Exit");
printf("\nPlease enter your choice: ");
scanf("%d", &ch);
switch(ch)
{
case 1: printf("\nEnter a item to be pushed: ");
scanf("%d",&item);
printf("\nEnter the stack number: ");
scanf("%d",&stackno);
push(stackno, item);
break;

case 2: printf("\nEnter the stack number: ");
scanf("%d",&stackno);
pop(stackno);
break;

case 3: for(stackno=0;stackno<n;stackno++)
{
printf("\nStack%d contents are: ", stackno);
display(stackno);
}
break;

case 4:exit(0);
default: printf("\nPlease enter a valid choice");
break;
}
}
}

Output:

Enter the number of stacks: 3

top[0] = -1 and boundary[0] = -1
top[1] = 3 and boundary[1] = 3
top[2] = 7 and boundary[2] = 7

~~~MENU~~~
1.Push operation
2.Pop operation
3.Display
4.Exit
Please enter your choice: 1
Enter a item to be pushed: 11
Enter the stack number: 0

~~~MENU~~~
1.Push operation
2.Pop operation
3.Display
4.Exit
Please enter your choice: 1
Enter a item to be pushed: 12
Enter the stack number: 0

~~~MENU~~~
1.Push operation
2.Pop operation
3.Display
4.Exit
Please enter your choice: 1
Enter a item to be pushed: 13
Enter the stack number: 0

~~~MENU~~~
1.Push operation
2.Pop operation
3.Display
4.Exit
Please enter your choice: 1
Enter a item to be pushed: 14
Enter the stack number: 0

~~~MENU~~~
1.Push operation
2.Pop operation
3.Display
4.Exit
Please enter your choice: 1
Enter a item to be pushed: 15
Enter the stack number: 0
Stack0 overflow

~~~MENU~~~
1.Push operation
2.Pop operation
3.Display
4.Exit
Please enter your choice: 1
Enter a item to be pushed: 21
Enter the stack number: 1

~~~MENU~~~
1.Push operation
2.Pop operation
3.Display
4.Exit
Please enter your choice: 1
Enter a item to be pushed: 22
Enter the stack number: 1

~~~MENU~~~
1.Push operation
2.Pop operation
3.Display
4.Exit
Please enter your choice: 1
Enter a item to be pushed: 23
Enter the stack number: 1

~~~MENU~~~
1.Push operation
2.Pop operation
3.Display
4.Exit
Please enter your choice: 1
Enter a item to be pushed: 31
Enter the stack number: 2

~~~MENU~~~
1.Push operation
2.Pop operation
3.Display
4.Exit
Please enter your choice: 1
Enter a item to be pushed: 32
Enter the stack number: 2

~~~MENU~~~
1.Push operation
2.Pop operation
3.Display
4.Exit
Please enter your choice: 1
Enter a item to be pushed: 33
Enter the stack number: 2

~~~MENU~~~
1.Push operation
2.Pop operation
3.Display
4.Exit
Please enter your choice: 3
Stack0 contents are:
| 14 |
| 13 |
| 12 |
| 11 |

Stack1 contents are:
| 23 |
| 22 |
| 21 |

Stack2 contents are:
| 33 |
| 32 |
| 31 |

~~~MENU~~~
1.Push operation
2.Pop operation
3.Display
4.Exit
Please enter your choice: 2
Enter the stack number: 1
Item that got deleted from stack1 is 23

~~~MENU~~~
1.Push operation
2.Pop operation
3.Display
4.Exit
Please enter your choice: 3

Stack0 contents are:
| 14 |
| 13 |
| 12 |
| 11 |

Stack1 contents are:
| 22 |
| 21 |

Stack2 contents are:
| 33 |
| 32 |
| 31 |

~~~MENU~~~
1.Push operation
2.Pop operation
3.Display
4.Exit
Please enter your choice: 2
Enter the stack number: 1
Item that got deleted from stack1 is 22

~~~MENU~~~
1.Push operation
2.Pop operation
3.Display
4.Exit
Please enter your choice: 2
Enter the stack number: 1
Item that got deleted from stack1 is 21

~~~MENU~~~
1.Push operation
2.Pop operation
3.Display
4.Exit
Please enter your choice: 2
Enter the stack number: 1
Stack1 underflow

~~~MENU~~~
1.Push operation
2.Pop operation
3.Display
4.Exit
Please enter your choice: 3

Stack0 contents are:
| 14 |
| 13 |
| 12 |
| 11 |

Stack1 contents are:
Stack1 is empty

Stack2 contents are:
| 33 |
| 32 |
| 31 |

~~~MENU~~~
1.Push operation
2.Pop operation
3.Display
4.Exit
Please enter your choice: 4

Monday, 5 September 2016

A Mazing Problem

#include<stdio.h>
#include<stdlib.h>

typedef struct
{
short int vert;
short int horiz;
}Offsets;

Offsets move[8];

typedef struct
{
short int row;
short int col;
short int dir;
}Element;

Element Stack[50];
int maze[10][10];
int mark[10][10];
int top=-1;
int exit_row,exit_col;

void readMaze()
{
int r, c;
int i, j;

printf("\nEnter the no of rows in the matrix: ");
scanf("%d", &r);

printf("\nEnter the no of cols in the matrix: ");
scanf("%d",&c);

printf("\nEnter the elements of the matrix: ");
for(i=0;i<r;i++)
{
for(j=0;j<c;j++)
{
scanf("%d",&maze[i][j]);
}
}
exit_row = r-2;
exit_col = c-2;
}

void setMoveTable()
{
move[0].vert = -1, move[0].horiz = 0;
move[1].vert = -1, move[1].horiz = 1;
move[2].vert = 0, move[2].horiz = 1;
move[3].vert = 1, move[3].horiz = 1;
move[4].vert = 1, move[4].horiz = 0;
move[5].vert = 1, move[5].horiz = -1;
move[6].vert = 0, move[6].horiz = -1;
move[7].vert = -1, move[7].horiz = -1;
}

void push(Element ele)
{
top = top+1;
Stack[top].row = ele.row;
Stack[top].col = ele.col;
Stack[top].dir = ele.dir;
return;
}

Element pop()
{
Element delItem;
delItem.row = Stack[top].row;
delItem.col = Stack[top].col;
delItem.dir = Stack[top].dir;
top = top-1;
return delItem;
}

void findpath()
/* function to search for path in the maze */
{
int i,row,col,nextRow,nextCol,dir,found=0;
Element position;
mark[1][1] = 1,top=0;
Stack[0].row = 1;
Stack[0].col = 1;
Stack[0].dir = 0;

while(top>-1 && !found)
{
position = pop();

row = position.row;
col = position.col;
dir = position.dir;

while(dir<8 && !found)
{
nextRow = row + move[dir].vert;
nextCol = col + move[dir].horiz;

if(nextRow == exit_row && nextCol == exit_col)
found = 1;

else if(!maze[nextRow][nextCol] && !mark[nextRow][nextCol])
{
mark[nextRow][nextCol] = 1;
position.row = row;
position.col = col;
position.dir = ++dir;
push(position);
row = nextRow;
col = nextCol;
dir = 0;
}
else
++dir;
}
}
if(found)
{
printf("\nThe path is:\n");
printf("row \t col \n");
for(i=0;i<=top;i++)
printf("%2d%5d \n",Stack[i].row,Stack[i].col);

printf("%2d%5d\n",row,col);
printf("%2d%5d\n",exit_row,exit_col);
}
else
printf("\nThe given maze does not have a path");
}

void main()
{
readMaze();
setMoveTable();
findpath();
return;
}

Output:

just put 1s for indicating border/wall (blue color)

Enter the no of rows in the matrix: 11

Enter the no of cols in the matrix: 8

Enter the elements of the matrix:
1 1 1 1 1 1 1 1
1 0 0 0 0 0 1 1
1 1 1 1 1 1 0 1
1 1 0 0 0 0 1 1
1 0 1 1 1 1 1 1
1 1 0 0 0 0 1 1
1 1 1 1 1 1 0 1
1 1 0 0 0 0 1 1
1 0 1 1 1 1 1 1
1 1 0 0 0 0 0 1
1 1 1 1 1 1 1 1

The path is:
row col
1 1
1 2
1 3
1 4
1 5
2 6
3 5
3 4
3 3
3 2
4 1
5 2
5 3
5 4
5 5
6 6
7 5
7 4
7 3
7 2
8 1
9 2
9 3
9 4
9 5
9 6

Credits,
Manoj T

Wednesday, 31 August 2016

Two Stacks in a Single Array

#include<stdio.h>
#define MAX 5
int s[MAX];
int top1 = -1, top2 = MAX;

void push(int stackno, int item)
{
if(stackno==1)
{
if(top1+1==top2)
{
printf("\nStack is full");
}
else
{
top1 = top1+1;
s[top1] = item;
}
}
else if(stackno==2)
{
if(top2-1== top1)
{
printf("\nStack is full");
}
else
{
top2 = top2-1;
s[top2] = item;
}
}
}

void pop(int stackno)
{
int item;
if(stackno == 1)
{
if(top1 == -1)
{
printf("\nStack1 is empty");
}
else
{
item = s[top1];
top1 = top1-1;
printf("\nItem that got deleted from stack1 is %d", item);
}
}
else if(stackno == 2)
{
if(top2 == MAX)
{
printf("\nStack2 is empty");
}
else
{
item = s[top2];
top2 = top2+1;
printf("\nItem that got deleted from stack2 is %d", item);
}
}
}

void display()
{
int i;
if(top1 == -1)
{
printf("\nStack 1 is empty");
}
else
{
printf("\nStack 1 contents are:\n");
for(i=top1;i>=0;i--)
printf("| %d |\n", s[i]);
}
if(top2==MAX)
{
printf("\nStack 2 is empty");
}
else
{
printf("\nStack 2 contents are:\n");
for(i=top2;i<MAX;i++)
printf("| %d |\n", s[i]);
}
}

void main()
{
int stackno, ch, item;
while(1)
{
printf("\n\n~~~Menu~~~");
printf("\n1.Push operation");
printf("\n2.Pop operation");
printf("\n3.Display");
printf("\n4.exit");
printf("\nEnter your choice: ");
scanf("%d",&ch);
switch(ch)
{
case 1: printf("\nEnter the stack number: ");
scanf("%d",&stackno);
printf("\nEnter the item: ");
scanf("%d", &item);
push(stackno, item);
display();
break;
case 2: printf("\nEnter the stack number: ");
scanf("%d", &stackno);
pop(stackno);
display();
break;
case 3: display();
break;
case 4:exit(0);
default: printf("\nPlease enter a valid choice: ");

}
}
}

Output:
~~~Menu~~~
1.Push operation
2.Pop operation
3.Display
4.exit
Enter your choice: 1

Enter the stack number: 1
Enter the item: 11

Stack 1 contents are:
| 11 |

Stack 2 is empty

~~~Menu~~~
1.Push operation
2.Pop operation
3.Display
4.exit
Enter your choice: 1

Enter the stack number: 1
Enter the item: 12

Stack 1 contents are:
| 12 |
| 11 |

Stack 2 is empty

~~~Menu~~~
1.Push operation
2.Pop operation
3.Display
4.exit
Enter your choice: 1

Enter the stack number: 1
Enter the item: 13

Stack 1 contents are:
| 13 |
| 12 |
| 11 |

Stack 2 is empty

~~~Menu~~~
1.Push operation
2.Pop operation
3.Display
4.exit
Enter your choice: 1

Enter the stack number: 2
Enter the item: 21

Stack 1 contents are:
| 13 |
| 12 |
| 11 |

Stack 2 contents are:
| 21 |

~~~Menu~~~
1.Push operation
2.Pop operation
3.Display
4.exit
Enter your choice: 1

Enter the stack number: 2
Enter the item: 22

Stack 1 contents are:
| 13 |
| 12 |
| 11 |

Stack 2 contents are:
| 22 |
| 21 |

~~~Menu~~~
1.Push operation
2.Pop operation
3.Display
4.exit
Enter your choice: 1

Enter the stack number: 2
Enter the item: 23

Stack is full

Stack 1 contents are:
| 13 |
| 12 |
| 11 |

Stack 2 contents are:
| 22 |
| 21 |

~~~Menu~~~
1.Push operation
2.Pop operation
3.Display
4.exit
Enter your choice: 2

Enter the stack number: 2
Item that got deleted from stack2 is 22

Stack 1 contents are:
| 13 |
| 12 |
| 11 |

Stack 2 contents are:
| 21 |

~~~Menu~~~
1.Push operation
2.Pop operation
3.Display
4.exit
Enter your choice: 2

Enter the stack number: 1
Item that got deleted from stack1 is 13

Stack 1 contents are:
| 12 |
| 11 |

Stack 2 contents are:
| 21 |

~~~Menu~~~
1.Push operation
2.Pop operation
3.Display
4.exit
Enter your choice: 3

Stack 1 contents are:
| 12 |
| 11 |

Stack 2 contents are:
| 21 |

~~~Menu~~~
1.Push operation
2.Pop operation
3.Display
4.exit
Enter your choice: 4

Friday, 19 August 2016

Conversion of Infix expression to Postfix expression Example 3

Conversion of Infix expression to Postfix expression

Example 3:

Given Infix Expression: ( ( A – ( B + C ) ) * D ) $ ( E+ F )

	Symbol	Operator Stack					Postfix String
	Symbol	[0]	[1]	[2]	[3]	[4]	Postfix String
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
13	)						ABC+-D*
14	$	$					ABC+-D*
15	(	$	(				ABC+-D*
16	E	$	(				*ABC+-DE**
17	+	$	(	+			*ABC+-DE**
18	F	$	(	+			*ABC+-DEF**
19	)	$					*ABC+-DEF+**
20							*ABC+-DEF+$**

So the corresponding Postfix expression is ABC+-D*EF+$