Balanced parentheses problem

Job ID: 35487731

Budget: $10 – $30 USD

Need to write down a Chomsky normal form context free
grammar that will solve the balanced parentheses problem
For this problem you are provided with a cyk code, and you just need to modify the rules, n_rules,
states, and input string.
 If your grammar only works for normal parentheses.
 If your grammar works for both normal and squared parentheses.
 Don’t forget the provided cyk code assumes every variable is an uppercase letter so you are
limited with amount of variables you can have on your grammar.
 If you want to use another cyk implementation you can do that, but your grammar should be
clearly stated in your code.


#include <iostream>
using namespace std;
int s2i(string states, char state)
{
for(int i=0; i<states.size(); i++)
if(states[i] == state)
return i;
return -1;
}
bool cyk(string input, char** rules, int n_rules, string states)
{
int loi=input.size();
int los=states.size();
bool*** table=new bool**[loi];
for(int i=0; i<loi; i++)
{
table[i]=new bool*[loi];
for(int j=0; j<loi; j++)
{
table[i][j]=new bool[los];
for(int k=0; k<los; k++)
table[i][j][k]=false;
}
}
for(int i=0; i<loi; i++)
for(int j=0; j<n_rules; j++)
if(rules[j][2]==input[i])
{
int state_id=s2i(states,rules[j][0]);
table[0][i][state_id]=true;
}
for(int i=1; i<loi; i++)
for(int j=0; j<(loi-i); j++)
for(int p=0; p<i; p++)
for(int k=0; k<n_rules; k++)
{
int state_id1=s2i(states,rules[k][0]);
int state_id2=s2i(states,rules[k][2]);
int state_id3=s2i(states,rules[k][3]);
if(state_id3==-1)
continue;
if(table[p][j][state_id2] and table[i-p-1][j+p+1][state_id3])
table[i][j][state_id1]=true;
}
for(int i=0; i<loi; i++)
{
cout<<"length "<<i<<":"<<endl;
for(int j=0; j<loi; j++)
{
cout<<"start "<<j<<":";
for(int k=0; k<los; k++)
{
if(table[i][j][k])
cout<<states[k]<<',';
}
cout<<" ";
}
cout<<endl;
}
if(table[loi-1][0][0])
return true;
else
return false;

}
int main()
{
string input = "ababa";
char* rules[7]={"S=AB","A=BC","A=a ","B=AC","B=b ","C=a ","C=b "};
int n_rules=7;
string states="SABC";
cout<<cyk(input,rules,n_rules,states);
return 0;
}