Showing posts with label Stack. Show all posts
Showing posts with label Stack. Show all posts

Tuesday 6 September 2016

Multiple stacks in 1 Dimensional Array

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

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

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
[0]
[1]
[2]
[3]
[4]

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+-D*E
17
+
$
(
+



ABC+-D*E
18
F
$
(
+



ABC+-D*EF
19
)
$





ABC+-D*EF+
20


ABC+-D*EF+$




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