pattern 15

**********
**** *****
***     ****
**          **
*              *

#include<stdio.h>
#include<conio.h>
void main()
{
int size,i,j;
for(size=5;size>=1;size--)
{
for(i=1;i<=size;i++)
{
printf("*");
}
for(j=s;j>1;j--)
{
printf("*");
}
printf("\n");
s++;
}
getch();
}

******
******
******
******
******


#include<stdio.h>
#include<conio.h>
void main()
{
      int i,j;
clrscr();
for(i=1;i<=5;i++)
{
for(j=1;j<=5;j++)
{
printf("*");
.
}
printf("\n");
}
getch();
}

C Program to construct a DFA from a regular expression.

#include<conio.h>
#include<strings.h>

void main()
{
int table[2][2],i,j,l,status=0,success;
char input[100];
printf("Program for implmenting DFA of language (a+aa*b)*\n\n\nEnter Input String \n");
table[0][0]=1;
table[0][1]=-1;
table[1][0]=1;
table[1][1]=0;
scanf("%s",input);
l=strlen(input);

for(i=0;i<l;i++)
{
if(input[i]!='a'&&input[i]!='b')
{
printf("Value entered is wrong");
getch();
exit(0);
}
if(input[i]=='a')
status=table[status][0];
else
status=table[status][1];

if(status==-1)
{
printf("String not Accepted by this Language");
break;
}
}
if(i==l)
printf("String Accepted");
getch();
}

C Program to eliminate left recursion from the grammar

.

#include<stdio.h>
  #include<string.h>
  #define SIZE 10
  int main () {
       char non_terminal;
       char beta,alpha;
       int num;
       int i;
       char production[10][SIZE];
       int index=3; /* starting of the string following "->" */
       printf("Enter Number of Production : ");
       scanf("%d",&num);
       printf("Enter the grammar as E->E-A :\n");
       for(i=0;i<num;i++){
            scanf("%s",production[i]);
       }
       for(i=0;i<num;i++){
            printf("\nGRAMMAR : : : %s",production[i]);
            non_terminal=production[i][0];
            if(non_terminal==production[i][index]) {
                 alpha=production[i][index+1];
                 printf(" is left recursive.\n");
                 while(production[i][index]!=0 && production[i][index]!='|')  {
           index++;  }
                 if(production[i][index]!=0)  {
                      beta=production[i][index+1];
                      printf("Grammar without left recursion:\n");
                      printf("%c->%c%c\'",non_terminal,beta,non_terminal);
                      printf("\n%c\'->%c%c\'|^\n",non_terminal,alpha,non_terminal);
                  }
                 else
                      printf(" can't be reduced\n");
            }
            else
                 printf(" is not left recursive.\n");
            index=3;
       }
  getche();
  }  

C Program to implement SR Parser on the Pre-assumed grammar.

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<string.h>
char ip_sym[15],stack[15];
int ip_ptr=0,st_ptr=0,len,i;
char temp[2],temp2[2];
char act[15];
void check();
void main()
{
//clrscr();
printf("\n\t\t SHIFT REDUCE PARSER\n");
printf("\n GRAMMER\n");
printf("\n E->E+E\n E->E/E");
printf("\n E->E*E\n E->a/b");
printf("\n enter the input symbol:\t");
gets(ip_sym);
printf("\n\t stack implementation table");
printf("\n stack\t\t input symbol\t\t action");
printf("\n______\t\t ____________\t\t ______\n");
printf("\n $\t\t%s$\t\t\t--",ip_sym);
strcpy(act,"shift  ");
temp[0]=ip_sym[ip_ptr];
temp[1]='\0';
strcat(act,temp);
len=strlen(ip_sym);
for(i=0;i<=len-1;i++)
{
stack[st_ptr]=ip_sym[ip_ptr];
stack[st_ptr+1]='\0';
ip_sym[ip_ptr]=' ';
ip_ptr++;
printf("\n $%s\t\t%s$\t\t\t%s",stack,ip_sym,act);
strcpy(act,"shift ");
temp[0]=ip_sym[ip_ptr];
temp[1]='\0';
strcat(act,temp);
check();
st_ptr++;
}
st_ptr++;
check();
}
void check()
{
int flag=0;
temp2[0]=stack[st_ptr];
temp2[1]='\0';
if((!strcmpi(temp2,"a"))||(!strcmpi(temp2,"b")))
{
stack[st_ptr]='E';
if(!strcmpi(temp2,"a"))
printf("\n $%s\t\t%s$\t\t\tE->a",stack, ip_sym);
else
printf("\n $%s\t\t%s$\t\t\tE->b",stack,ip_sym);
flag=1;
}
if((!strcmpi(temp2,"+"))||(strcmpi(temp2,"*"))||(!strcmpi(temp2,"/")))
{
flag=1;
}
if((!strcmpi(stack,"E+E"))||(!strcmpi(stack,"E\E"))||(!strcmpi(stack,"E*E")))
{
strcpy(stack,"E");
st_ptr=0;
if(!strcmpi(stack,"E+E"))
printf("\n $%s\t\t%s$\t\t\tE->E+E",stack,ip_sym);
else
if(!strcmpi(stack,"E\E"))
printf("\n $%s\t\t %s$\t\t\tE->E\E",stack,ip_sym);
else
printf("\n $%s\t\t%s$\t\t\tE->E*E",stack,ip_sym);
flag=1;
}

if(!strcmpi(stack,"E")&&ip_ptr==len)
{
 printf("\n $%s\t\t%s$\t\t\tACCEPT",stack,ip_sym);
getche();
}if(flag==0){
 printf("\n%s\t\t\t%s\t\t reject",stack,ip_sym);
}
getche();
}

C Program to check whether the given string is a valid identifier or not.

C Program to check whether the given string is a valid identifier or not.

#include <stdio.h>
#include <string.h>
#include <conio.h>
main (){
char string [50];
printf ("Enter value to be identified: ");
scanf ("%s", string);
int length = strlen (string) - 1;
bool alpha_string = false;
if ( string [0] >= 'A' && string [0] <= 'Z' )
alpha_string = true;
if ( string [0] >= 'a' && string [0] <= 'z' )
alpha_string = true;
bool underScore = true;
if ( string [length] == '_' )
underScore = false;
int num = 0;
for ( int i = 1; i <= length; i++ ) {
if ( string [i] == '_' )
num++;
else
num = 0;
if ( num == 2 ) {
underScore = false;
break;
}}
if ( alpha_string && underScore)
printf ("Answer: %s is a valid identifier\n", string);
else
printf ("Answer: %s is not a valid identifier\n", string);
getche();
}

rb tree insertion

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

//A Red-Black tree node structure
struct node
{
    int data;     // for data part
    char color;  // for color property

    //links for left, right children and parent
    struct node *left, *right, *parent;
};


// Left Rotation
void LeftRotate(struct node **root,struct node *x)
{
    //y stored pointer of right child of x
    struct node *y = x->right;

    //store y's left subtree's pointer as x's right child
    x->right = y->left;

    //update parent pointer of x's right
    if (x->right != NULL)
        x->right->parent = x;

    //update y's parent pointer
    y->parent = x->parent;

    // if x's parent is null make y as root of tree
    if (x->parent == NULL)
        (*root) = y;

    // store y at the place of x
    else if (x == x->parent->left)
        x->parent->left = y;
    else    x->parent->right = y;

    // make x as left child of y
    y->left = x;

    //update parent pointer of x
    x->parent = y;
}


// Right Rotation (Similar to LeftRotate)
void rightRotate(struct node **root,struct node *y)
{
    struct node *x = y->left;
    y->left = x->right;
    if (x->right != NULL)
        x->right->parent = y;
    x->parent =y->parent;
    if (x->parent == NULL)
        (*root) = x;
    else if (y == y->parent->left)
        y->parent->left = x;
    else y->parent->right = x;
    x->right = y;
    y->parent = x;
}

// Utility function to fixup the Red-Black tree after standard BST insertion
void insertFixUp(struct node **root,struct node *z)
{
    // iterate until z is not the root and z's parent color is red
    while (z != *root && z->parent->color == 'R')
    {
        struct node *y;

        // Find uncle and store uncle in y
        if (z->parent == z->parent->parent->left)
            y = z->parent->parent->right;
        else
            y = z->parent->parent->left;

        // If uncle is RED, do following
        // (i)  Change color of parent and uncle as BLACK
        // (ii) Change color of grandparent as RED
        // (iii) Move z to grandparent
        if (y->color == 'R')
        {
            y->color = 'B';
            z->parent->color = 'B';
            z->parent->parent->color = 'R';
            z = z->parent->parent;
        }

        // Uncle is BLACK, there are four cases (LL, LR, RL and RR)
        else
        {
            // Left-Left (LL) case, do following
            // (i)  Swap color of parent and grandparent
            // (ii) Right Rotate Grandparent
            if (z->parent == z->parent->parent->left &&
                z == z->parent->left)
            {
                char ch = z->parent->color ;
                z->parent->color = z->parent->parent->color;
                z->parent->parent->color = ch;
                rightRotate(root,z->parent->parent);
            }

            // Left-Right (LR) case, do following
            // (i)  Swap color of current node  and grandparent
            // (ii) Left Rotate Parent
            // (iii) Right Rotate Grand Parent
            if (z->parent == z->parent->parent->left &&
                z == z->parent->right)
            {
                char ch = z->color ;
                z->color = z->parent->parent->color;
                z->parent->parent->color = ch;
                LeftRotate(root,z->parent);
                rightRotate(root,z->parent->parent);
            }

            // Right-Right (RR) case, do following
            // (i)  Swap color of parent and grandparent
            // (ii) Left Rotate Grandparent
            if (z->parent == z->parent->parent->right &&
                z == z->parent->right)
            {
                char ch = z->parent->color ;
                z->parent->color = z->parent->parent->color;
                z->parent->parent->color = ch;
                LeftRotate(root,z->parent->parent);
            }

            // Right-Left (RL) case, do following
            // (i)  Swap color of current node  and grandparent
            // (ii) Right Rotate Parent
            // (iii) Left Rotate Grand Parent
            if (z->parent == z->parent->parent->right &&
                z == z->parent->left)
            {
                char ch = z->color ;
                z->color = z->parent->parent->color;
                z->parent->parent->color = ch;
                rightRotate(root,z->parent);
                LeftRotate(root,z->parent->parent);
            }
        }
    }
    (*root)->color = 'B'; //keep root always black
}

// Utility function to insert newly node in RedBlack tree
void insert(struct node **root, int data)
{
    // Allocate memory for new node
    struct node *z = (struct node*)malloc(sizeof(struct node));
    z->data = data;
    z->left = z->right = z->parent = NULL;

     //if root is null make z as root
    if (*root == NULL)
    {
        z->color = 'B';
        (*root) = z;
    }
    else
    {
        struct node *y = NULL;
        struct node *x = (*root);

        // Follow standard BST insert steps to first insert the node
        while (x != NULL)
        {
            y = x;
            if (z->data < x->data)
                x = x->left;
            else
                x = x->right;
        }
        z->parent = y;
        if (z->data > y->data)
            y->right = z;
        else
            y->left = z;
        z->color = 'R';

        // call insertFixUp to fix reb-black tree's property if it
        // is voilated due to insertion.
        insertFixUp(root,z);
    }
}

// A utility function to traverse Red-Black tree in inorder fashion
void inorder(struct node *root)
{
    if (root == NULL)
        return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

/* Drier program to test above function*/
int main()
{
    struct node *root = NULL;
    insert(&root,5);
    insert(&root,3);
    insert(&root,7);
    insert(&root,2);
    insert(&root,4);
    insert(&root,6);
    insert(&root,8);
    insert(&root,11);
    printf("inorder Traversal Is : ");
    inorder(root);

    return 0;
}