什么是它的输出 - plz给我一个例子？ [英] what's its output - plz give me an example?

问题描述

任何人都可以帮我给我一个输出程序的例子......它的Cyk算法实现......我非常感谢能帮助我理解它的代码...



非常感谢



~lida

can anyone help me to give me an example of its output program ... its Cyk Algorithm Implementation ... i''ll be thankful very much to help me to understand its code ...

many thanks

~lida

#include "stdafx.h"
#include <Windows.h>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cassert>
#include<iomanip>
using namespace std;

#define MAX 100
#define for(i,a,b) for(i=a;i<b;i++)
#define ASSERTMSG(TST,MSG) ((TST) ? (void)0 : (cerr<<MSG<<endl,abort()))

string arr[MAX][MAX]; // to store entered grammar
string dpr[MAX];
int p,np; // np -> number of productions

inline string concat(string a, string b)//concatenates unique non-terminals
{
	int i;
	string r=a;
	for(i,0,b.length())
		if(r.find(b[i]) > r.length())
			r += b[i];
	return (r);

}

inline void deconc(string a)//seprates right hand side of entered grammar
{
	int i;
	p=0;

	while(a.length())
	{
		i = a.find("|");
		if ( i > a.length())
		{
			dpr[p++] = a;
			a=" ";
		
		}
		else
		{
			dpr[p++] = a.substr(0,i);
			a = a.substr(i+1,a.length());
		
		}
	
	}

}

inline int lchomsky (string a) //checks if LHS of entered grammar is in CNF
{
	if(a.length() == 1 && a[0] >= 'A' && a[0] <= 'Z')
		return 1;
	return 0;

}

inline int rchomsky (string a)//checks if RHS of grammar is in CNF
{
	if( a.length() == 1 && a[0] >= 'a' && a[0] <= 'z')
		return 1;
	if ( a.length() == 2 && a[0] >= 'A' && a[0] <= 'Z' && a[1] >= 'A' && a[1] <= 'Z')
       return 1;
	return 0;
}

inline string search_prod(string p)//returns a concatenated string of variables which can produce string p
{
	int j,k;
	string r= " ";
	for(j,0,np)
	{
		k=1;
		while(arr[j][k] != " ")
		{
			if (arr[j][k] == p)
			{
				r= concat(r,arr[j][0]);
			
			}
		k++;
		}
	
	}
return r;
}

inline string gen_comb(string a, string b)//creates every combination of variables from a and b . For eg: BA * AB = 
{
	int i,j;
	string pri=a,re=" ";
	for(i,0,a.length())
		for(j,0,b.length())
		{
			pri = " ";
			pri = pri + a[i] + b[j];

			re = re + search_prod(pri);//searches if the generated productions can be created or not
		
		}
		return re;

}

int main()
{
	int i,pt,j,l,k;
	string a,str,r,pr,start;

	cout<<"\n*************************CYK ALGORITHM Implementation**************************\n";
	cout<<"\nEnter the set of start variables ";
	cin>>start;
	cout<<"\nEnter number of productions ";
	cin>> np;

	for(i,0,np)
	{
		cin>>a;
		pt = a.find( " -> ");
		arr[i][0] = a.substr(0,pt);

		ASSERTMSG(lchomsky(dpr[j]),"\nGrammar not in Chomsky Form");
        
		a = a.substr(pt+2 , a.length());
		deconc(a);

		for(j,0,p)
		{
			arr[i][j+1]=dpr[j];
			ASSERTMSG(rchomsky(dpr[j]),"\nnGrammar not in Chomsky Form");

		
		}
	
	}
	string matrix[MAX][MAX],st;
	cout<<"\nEnter string to be checked : ";
cin>>str;

for(i,0,str.length())
{
	r = " ";
	st = " ";
	st += str[i];

	for(j,0,np)
	{
		k = 1;
		while(arr[j][k] != " ")
		{
			if(arr[j][k] == st)
			{
				r=concat(r,arr[j][0]);
		
			}
			k++;
		
		}
		
	
	}

matrix[i][i] = r;

}

int ii,kk;
for( k , 1 , str.length())
{
	for(j,k,str.length())
	{
		r = " ";
		for (l,j-k,j)
		{
			pr = gen_comb(matrix[j-k][l],matrix[l+1][j]);
			r = concat(r,pr);
		
		}
		matrix[j-k][j] = r;

	
	}

}

cout<< " \nMatrix Generated :- " << endl;

for(i,0,str.length())
{
	for(j,0,str.length())
		cout<< setw(5) << matrix[i][j] << " ";

	cout << endl;

}

int f=0;
for(i,0,start.length())
if( matrix[0][str.length()-1].find(start[i]) <= matrix[0][str.length()-1].length())
{
	cout << "String can be generated\n";
	return 0;

}

cout << "String cannot be generated\n";
return 0;
}

推荐答案

小提示你有一个名为理论计算机科学或（TCS）的主题，你的代码正在检查是否你输入的字符串是否采用乔姆斯基普通形式（CNF），并根据结果对其进行进一步处理......

Little hint did you have a subject called Theoretical Computer Science or(TCS),your code is checking whether ur entered string is in Chomsky Normal form (CNF) or not and does further processing on it depending on the outcome...

这篇关于什么是它的输出 - plz给我一个例子？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！