Stack Program #4

-

18. Write a program to convert in-fix notation to pre-fix notation using Stack.

#include<stdio.h>
#include<string.h>
#define N 50
char s[N];
int top=-1;

void push(char);
char pop();
int f(char);
int g(char);
int r(char);

void main()
{
     int i=0,k=0,j=0,rank,c=0,l=0,a=0,m=0;
     char infix1[50],infix[50],next,temp,x,polish[50],polish1[50];
     printf("Enter a infix expression with extra closing bracket:\n");
     scanf("%s",infix1);
     while(infix1[k]!='\0')
     {
          l++; // size getting
          k++; //string increase
     }
     for(j=l-1;j>=0;j--)
     {
           infix[i]=infix1[j];
           i++;
     }
     infix[i]='\0';
     i=0,j=0;
     while(infix[i]!='\0')
     {
          if(infix[i]=='(')
          {
               infix[i]=')';
          }
          else if(infix[i]==')')
          {
               infix[i]='(';
          }
          i++;
      }
     infix[i]=')';
     i++;
     infix[i]='\0';
     i=1;
     top=0;
     s[top]='(';
     polish[50]='\0';
     rank=0;
     next=infix[i];
     while(next!='\0')
     {
          if(top<0)
          {
               printf("Invalid\n");
               return;
          }
          while(g(s[top])>f(next))
          {
               temp=pop();
               polish[j]=temp;
               j++;
               rank=rank+r(temp);
               if(rank<1)
               {
                    printf("Invalid\n");
                    return;
               }
          }
          if(g(s[top])!=f(next))
          {
               push(next);
          }
          else
          {
               pop();
          }
          polish[j]='\0';
          i++;
          next=infix[i];
     }
     j=0;
     while(polish[j]!='\0')
     {
          a++;
          j++;
     }
     for(c=a-1;c>=0;c--)
     {
          polish1[m]=polish[c];
          m++;
     }
     if(top!=-1 || rank!=1)
     {
           printf("Invalid\n");
     }
     else
     {
           printf("Valid\n");
           polish1[m]='\0';
           printf("Prefix of %s is %s \n",infix1,polish1);
     }

}
void push(char x)
{
     if(top>=N-1)
     {

          printf("STACK OVERFLOW\n");
     }
     else
     {
          top++;
          s[top]=x;
     }
}
char pop()
{
     if(top==-1)
     {
          printf("STACK UNDERFLOW\n");
          return('\0');
     }
     else
     {
          top=top-1;
          return(s[top+1]);
     }
}
int f(char t)
{
     if(t=='+' || t=='-')
     {
          return 1;
     }
     if(t=='*' || t=='/')
     {
          return 3;
     }
     if(t=='^' || t=='$')
     {
          return 6;
     }
     if(t>='a' && t<='z' || t>='A' && t<='Z')
     {
          return 7;
     }
     if(t=='(')
     {
          return 9;
     }
     if(t==')')
     {
          return 0;
     }
}
int g(char t)
{
     if(t=='+' || t=='-')
     {
          return 2;
     }
     if(t=='*' || t=='/')
     {
          return 4;
     }
     if(t=='^' || t=='$')
     {
          return 5;
     }
     if(t>='a' && t<='z' || t>='A' && t<='Z')
     {
          return 8;
     }
     if(t=='(')
     {
          return 0;
     }
}
int r(char t)
{
     if(t=='+' || t=='-')
     {
          return -1;
     }
     if(t=='*' || t=='/')
     {
          return -1;
     }
     if(t=='^'|| t=='$')
     {
          return -1;
     }
     if(t>='a' && t<='z' || t>='A' && t<='Z')
     {
          return 1;
     }
}

OR

#include<stdio.h>
#include<string.h>
#define N 50
char s[N];
int top=-1;

void push(char);
char pop();
int f(char);
int g(char);
int r(char);

void main()
{
     int i=0,k=0,j=0,rank,c=0,l=0,a=0,m=0;
     char infix1[50],infix[50],next,temp,x,polish[50],polish1[50];
     printf("Enter a infix expression with extra closing bracket:\n");
     scanf("%s",infix1);
     while(infix1[k]!='\0')
     {
          l++; // size getting
          k++; //string increase
     }
     for(j=l-1;j>=0;j--)
     {
           infix[i]=infix1[j];
           i++;
     }
     infix[i]='\0';
     printf("%s\n",infix);
     i=0,j=0;
     while(infix[i]!='\0')
     {
          if(infix[i]=='(')
          {
               infix[i]=')';
          }
          else if(infix[i]==')')
          {
               infix[i]='(';
          }
          i++;
      }
     infix[i]=')';
     i++;
     infix[i]='\0';
     printf("%s\n",infix);
     i=1;
     top=0;
     s[top]='(';
     polish[50]='\0';
     rank=0;
     next=infix[i];
     while(next!='\0')
     {
          if(top<0)
          {
               printf("Invalid\n");
               return;
          }
          while(g(s[top])>f(next))
          {
               temp=pop();
               polish[j]=temp;
               j++;
               rank=rank+r(temp);
               if(rank<1)
               {
                    printf("Invalid\n");
                    return;
               }
          }
          if(g(s[top])!=f(next))
          {
               push(next);
          }
          else
          {
               pop();
          }
          polish[j]='\0';
          printf("%c\t%s\t%s\t%d\n",infix[i],s,polish,rank);
          i++;
          next=infix[i];
     }
     j=0;
     while(polish[j]!='\0')
     {
          a++;
          j++;
     }
     for(c=a-1;c>=0;c--)
     {
          polish1[m]=polish[c];
          m++;
     }
     if(top!=-1 || rank!=1)
     {
           printf("Invalid\n");
     }
     else
     {
           printf("Valid\n");
           polish1[m]='\0';
           printf("Prefix of %s is %s \n",infix1,polish1);
     }

}
void push(char x)
{
     if(top>=N-1)
     {

          printf("STACK OVERFLOW\n");
     }
     else
     {
          top++;
          s[top]=x;
     }
}
char pop()
{
     if(top==-1)
     {
          printf("STACK UNDERFLOW\n");
          return('\0');
     }
     else
     {
          top=top-1;
          return(s[top+1]);
     }
}
int f(char t)
{
     if(t=='+' || t=='-')
     {
          return 1;
     }
     if(t=='*' || t=='/')
     {
          return 3;
     }
     if(t=='^' || t=='$')
     {
          return 6;
     }
     if(t>='a' && t<='z' || t>='A' && t<='Z')
     {
          return 7;
     }
     if(t=='(')
     {
          return 9;
     }
     if(t==')')
     {
          return 0;
     }
}
int g(char t)
{
     if(t=='+' || t=='-')
     {
          return 2;
     }
     if(t=='*' || t=='/')
     {
          return 4;
     }
     if(t=='^' || t=='$')
     {
          return 5;
     }
     if(t>='a' && t<='z' || t>='A' && t<='Z')
     {
          return 8;
     }
     if(t=='(')
     {
          return 0;
     }
}
int r(char t)
{
     if(t=='+' || t=='-')
     {
          return -1;
     }
     if(t=='*' || t=='/')
     {
          return -1;
     }
     if(t=='^'|| t=='$')
     {
          return -1;
     }
     if(t>='a' && t<='z' || t>='A' && t<='Z')
     {
          return 1;
     }
}

Output

  1. Enter a infix expression with extra closing bracket:
    A$B-C*D+E$F/G)
    Valid
    Prefix of A$B-C*D+E$F/G) is -$AB+*CD/$EFG  

OR

Output

  1.  Enter a infix expression with extra closing bracket:
    A$B-C*D+E$F/G)
    )G/F$E+D*C-B$A
    (G/F$E+D*C-B$A)
    G    (G                                           0
    /      (/           G                               1
    F     (/F         G                               1
    $     (/$         GF                             2
    E     (/$E       GF                            2
    +     (+$E     GFE$/                       1
    D     (+DE    GFE$/                        1
    *      (+*E     GFE$/D                     2
    C     (+*C     GFE$/D                     2
    -      (-*C       GFE$/DC*+               1
    B     (-BC      GFE$/DC*+               1
    $     (-$C       GFE$/DC*+B            2
    A     (-$A      GFE$/DC*+B             2
    )                   GFE$/DC*+BA$-        1
    Valid
    Prefix of A$B-C*D+E$F/G) is -$AB+*CD/$EFG


For download this program please check the link ➡➡ Download OR Download

Comments

Post a Comment

Popular

Basic Program #3

-
Image
3.Read any number and find factorial of a number. (Using Recursion) #include <stdio.h> long long int factorial(int n); int main() {     int n;    long long int f;     printf("Enter an integer to find it's factorial: ");     scanf("%d", &n);      // show error if the user enters a negative integer     if (n < 0)     {         printf("Error! Factorial of a negative number doesn't exist.\n");     }     else     {              f=factorial(n);             printf("Factorial of %d = %llu\n", n, f);     } } long long int factorial(int n) {     if (n>=1)     {         return n*factorial(n-1);  ...
Read more

Pointer Program #1

-
Image
10. Read n numbers in an array and print them using pointer. #include<stdio.h> void main () {      int n,i,*p,array[100];      p=array;      printf("Enter size of array:\n");      scanf("%d",&n);      printf("Enter elements of array:\n");      for(i=0;i<n;i++)      {           scanf("%d",p+i);      }      printf("The array using pointer is:\n");      for(i=0;i<n;i++)      {           printf("%d\n",*(p+i));      } } Output Enter size of array: 5 Enter elements of array : 12 13 14 15 16 The array using pointer is: 12 13 14 15 16 Note: The above method uses array notation to print elements. You can also use poi...
Read more

Array Program #4

-
Image
7. Read n numbers in an array, read two different numbers, search the first number in an array and replace it with another number in an array and print its index and final array. #include <stdio.h> int main() {     int array[100], x,y, i, n, count = 0;               printf("Enter the number of elements in array\n");      scanf("%d", &n);            printf("Enter %d numbers\n", n);            for (i = 0; i < n; i++)         scanf("%d", &array[i]);             printf("Enter n number by which you want to replace?\n");      scanf("%d",&x);          printf(" By which number?\n");      scanf("%d",&y);   ...
Read more

Singly Linked List program #1

-
Image
23. Implement a program to create a node for singly linked list. Read the data for a node, print the node and release the memory of the node. #include<stdio.h> #include<stdlib.h> struct node {      int info;      struct node * link; }; // typeded struct node Node means using struct node replace with Node bellow void main() {      int x;      struct node * new;      new=(struct node * )malloc(sizeof(struct node));      if(new=='\0')      {           printf("Memory is not available\n");           return;      }      else      {           printf("Enter data which you want to add\n");       ...
Read more

Basic program #2

-
Image
2. Read any number and find factorial of a number. (Using Loop) #include <stdio.h> int main() {     int n, i;     unsigned long long factorial = 1;     printf("Enter an integer to find it's factorial: ");     scanf("%d",&n);      // show error if the user enters a negative integer     if (n < 0)         printf("Error! Factorial of a negative number doesn't exist.");     else     {            i=1;         while(i<=n)         {             factorial *= i;              // factorial = factorial*i;             i++; ...
Read more