Balanced parentheses problem
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;
}
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;
}