Friday 9 October 2015

Convert Infix expression into Postfix expression

#include<stdio.h>
#include<conio.h>
void main(){
char inf[30];
char post[30]="\0";
char stack[30];
int top=0;
int i=0;
int pcount=-1;
char ch;
int j=0;
clrscr();
printf("\nEnter the expression : ");
scanf("%s",inf);
ch=inf[0];
stack[top]='#';
while(ch!='\0'){
switch(ch){
case '^' : top++;
           stack[top]=ch;
           break;
case '*':
case '/':
           if(stack[top]=='^'){
           pcount++;
           post[pcount]=stack[top];
           top--;
           pcount++;
           top++;
           stack[top]=ch;
           }
           else if(stack[top]=='*' && (ch=='/'|| ch=='*')){
             pcount++;
             post[pcount]=stack[top];
             top--;
             top++;
             stack[top]=ch;
           }
           else if(stack[top]=='/' && (ch=='/'|| ch=='*')){
             pcount++;
             post[pcount]=stack[top];
             top--;
             top++;
             stack[top]=ch;
           }
           else{
           top++;
           stack[top]=ch;
           }
           break;
case '+' :
case '-' :
           if(stack[top]=='^'){
           pcount++;
           post[pcount]=stack[top];
           top--;
           pcount++;
           top++;
           stack[top]=ch;
           }
           else if(stack[top]=='*'|| stack[top]=='/'){
           pcount++;
           post[pcount]=stack[top];
           top--;
           pcount++;
           top++;
           stack[top]=ch;
           }

           else if(stack[top]=='+' && (ch=='+'|| ch=='-')){
             pcount++;
             post[pcount]=stack[top];
             top--;
             top++;
             stack[top]=ch;
           }
           else if(stack[top]=='-' && (ch=='+'|| ch=='-')){
             pcount++;
             post[pcount]=stack[top];
             top--;
             top++;
             stack[top]=ch;
           }
           else{
           top++;
           stack[top]=ch;
           }
           break;
case '(' : top++;
           stack[top]=ch;
           break;
case ')' : while(stack[top]!='('){
            pcount++;
            post[pcount]=stack[top];
            top--;
            }
            top--;
            break;
default :
            pcount++;
            post[pcount]=ch;
            break;

}
j++;
ch=inf[j];

}
while(stack[top]!='#'){
pcount++;
post[pcount]=stack[top];
top--;
j++;
}
printf("\nPostfix : ");
for(i=0;i<30;i++){
printf("%c",post[i]);
}
getch();

}

Monday 7 September 2015

Program in c for acceptance of string ((a|b)*abb) using dfa

#include<stdio.h>
void main(){
int state=0;
int prev=0;
int next =0;
int arr[4][2]={{1,0},{1,2},{1,3},{1,0}};
char str[20];
char ch;
int i=0;
  printf("\nEnter the string");
  fgets(str,20,stdin);
 while(1){
    ch=str[i];
    if(ch=='a'){
    next = arr[prev][0];
    printf("\nPrev =  %d and next = %d",prev,next);
    prev= next;
    state = next;
    }
    else if(ch=='b'){
    next = arr[prev][1];
    printf("\nPrev =  %d and next = %d",prev,next);
    prev= next;
    state = next;
    }
    else if(ch=='$'){
    if(state==3){
    state =4;
    next = state;
    printf("\nPrev =  %d and next = %d",prev,next);   
    }
    break;
    }
    else if(ch=='\0'){
    printf("\nString is not terminated... Enter $ to terminate it...");
    break;
    }
    else if(ch==' '){
    printf("\nPlease do not enter blank spaces");
    break;
    }
   i++;

 }
 if(state ==4){
    printf("\nString is accepted");
 }
 else{
    printf("\nString is not accepted");
 }
}

Monday 31 August 2015

Program in c for removing spaces from the string
#include<stdio.h>
#include<string.h>
void main(){
char str[20];
int i,j,n,t,nl;
int k=0;
int l=0;
printf("\nEnter the string");
fgets(str,20,stdin);

n= strlen(str);
while(str[l]!='\0'){
k=0;
nl=0;
t=0;
for(i=l;i<n;i++){

if(str[i]=='\n'){
nl++;
}
else if(str[i]=='\t'){
t++;
}
else if(str[i] ==' '){
k++;
}

else
break;
}
if(nl>0){
for(j=l;j<n;j++){
str[j]=str[j+nl];
}
n=n-nl;
}
else if(t>0){
for(j=l;j<n;j++){
str[j]=str[j+t];
}
n=n-t;
}
else if(k>0){
for(j=l;j<n;j++){
str[j]=str[j+k];
}
n=n-k;
}
l++;
}

for(i=0;i<n;i++)
printf("%c",str[i]);
}

Tuesday 11 August 2015

Milk Man and His Bottles


A Milkman serves milk in packaged bottles of varied sizes. The possible size of the bottles are {1, 5, 7 and 10} litres. He wants to supply desired quantity using as less bottles as possible irrespective of the size. Your objective is to help him find the minimum number of bottles required to supply the given demand of milk.
Input Format:

First line contains number of test cases N
Next N lines, each contain a positive integer Li which corresponds to the demand of milk.
Output Format:

For each input Li, print the minimum number of bottles required to fulfill the demand
Constraints:
1 <= N <= 1000
Li > 0
1 <= i <= N
Sample Input and Output

SNo.InputOutput
1
2
17
65

2
7

Explanation:

Number of test cases is 2 



  1. In first test case, demand of milk is 17 litres which can be supplied using minimum of 2 bottles as follows
    • 1 x 10 litres and
    • 1 x 7 litres
  2. In second test case, demand of milk is 65 litres which can be supplied using minimum of 7 bottles as follows
    • 6 x 10 litres and
    • 1 x 5 litres

Answer to the programming question "Find My Friend" :-

import java.util.Scanner;
class Sub {
    public static void main(String args[] ) throws Exception {
    Scanner in = new Scanner(System.in);
    int max= in.nextInt();
    int cnt=0;
    int flag=0;
    int frnd=0;
    int no = in.nextInt();
    int arr[] = new int[no];
    int div[] = new int[1000];
    for(int i=0;i<no;i++)
    arr[i]=in.nextInt();
    int n=2;
    int k=0;
   
    while(max!=1){
    if(max % n == 0){
    div[k]=n;
   
    k++;
    cnt++;
    max=max/n;    
    }
   
    n++;
    }
    for(int i=0;i<no;i++){
    for(int j=0;j<cnt;j++){
    if(arr[i] % div[j]==0){
    flag=1;
    break;
    }
    else{
    flag=0;
    }
    }
    if(flag==1){
    frnd++;
    }
    }
    System.out.println(frnd);
       }
}

Monday 3 August 2015

Find My Friend

Max feels lonely after shifting to a new locality, as he does not have any friend there. So his parents bought him a new number from the Integers SuperMarket! Every child in the locality has bought a number from the same market.
He takes the number to go play with other children in the locality. But to his surprise, there is a rule in the locality, two people A and B can only be considered friends if numbers with A and B are not Coprime, i.e they have a common factor other than 1.
You are given the number that Max bought and the numbers of other children in the locality. Can you find how many friends he can have?
Input:
First line contains an integer A, the number that Max has.
Second line contains N, the count of children in the locality.
Third line contains N space-separated integers, where Xi is the integer with the ith child.
Output:
Output the maximum number of friends that Max can make.
Constraints:
1 ≤ A ≤ 103
1 ≤ N ≤ 103
1 ≤ Xi ≤ 103
Sample Input

6
3
4 7 12
Sample Output
2
Explanation
Puchi can become friends with First and Third child.