write a recursive program that matches a string of the form

write a recursive program that matches a string of the form A^nB^(3n).

If the input string AABBBBBB then return true. A\'s and B\'s should be in above manner. ABABBBBB will not return true.

Solution

#include<iostream>
#include<string>
using namespace std;
int countA=0,countB=0,n=0,A=0,B=0;
//Recursion
void Iscorrect(string s,int i,int j)
{
if(j==s.length())
return;//termination condition for recursion
if(s[i]==\'A\' && countA<=n && A==0)//here we take A=0 so that if any B occurs it should not be counted
countA++;
else A++;
if(s[j]==\'B\'&&countB<=s.length()-n && B==0)//same reason as for A
countB++;
else B++;
return Iscorrect(s,i+1,j+1);//recursion so that we can count A and B
}
// Driver Program
int main(){
string s;
cin>>s;
/*here we first check that is string length modulo 4 is not zero then it should never be correct because it is given that string has 4n characters*/
n=s.length()/4;
if(s.length()%4!=0)
cout<<\"false\"<<endl;
else{
Iscorrect(s,0,n);//here we sending the index of starting position of A & B
if(countA+countB!=s.length())
cout<<\"false\"<<endl;
else cout<<\"true\"<<endl;
}
return 0;
}