• 热门专题

数据结构实验KMP算法之Test.ming

作者:  发布日期:2014-10-31 19:22:00
Tag标签:数据结构  算法  
  • 翻译程序
    小明初学C++,已明白了四则运算、关系运算、逻辑运算、赋值运算、输入输出、简单选择和循环结构的用法,但他的英语不太好,记不住太多的保留字,于是他利用汉语拼音做保留字,山寨C++,发明了一种表达自己思想的算法描述规则。
    规则很简单:他将开始程序头部以一个拼音名字标记,C++程序中的"{,}"用拼音“kaishi,jieshu”直观表示;选择和循环只采用一种单一的结构,且保留字也分别用对应的拼音表示,不过在表示选择或循环条件时他去掉了多余的小括号;输入输出也用拼音表示;数据类型只保留了整型(int)和实型(float),并用拼音表示,且按他的习惯变量在前,类型在后。
    现在小明想请熟悉C++的你帮他写一个程序,将用他设计的算法描述规则写成的算法,翻译成C++源码。输入文件扩展名为.ming,输出文件扩展名为.cpp,如下例:

    小明算法(test.ming):
    chengxu1
    kaishi
    i,j zhengxing;
    k shixing;
    i=1;j=0;
    shuru k;
    xunhuan i<10
    kaishi
    j=j+i;
    i++;
    jieshu
    ruguo j>10
    kaishi
    k=j*1.0/i;
    jieshu
    shuchu k,j;
    jieshu

    翻译成的C++源码(test.cpp):
    #include <iostream>
    using namespace std;
    int main()
    {
    int i,j;
    float k;
    i=1;j=0;
    cin>>k;
    while( i<10)
    {
    j=j+i;
    i++;
    }
    if(j>10)
    k=j*1.0/i;
    cout<<k<<j;
    return 0;
    }

    参考代码:

    #include <iostream>
    #include <string>
    #include <fstream>
    #define max_size 30
    #define MaxNum 9
    
    using namespace std;
    
    string Ming[MaxNum]={
    	"chengxu1",//
    		"kaishi",
    		"jieshu",
    		"xunhuan",
    		"shuru",
    		"shuchu",
    		"ruguo",
    		"zhengxing",
    		"shixing"
    };
    string Cpp[MaxNum]={
    	"#include <iostream>
    #include <string>
    using namespace std;
    void main()",
    		"{",
    		"}",
    		"while(",
    		"cin>>",
    		"cout<<",
    		"if(",
    		"int",
    		"float"
    };
    
    void GetNextval(string &line,int nextval[])//对模式串求next[]值
    {
    	int j=0,k=-1;
    	nextval[0]=-1;
    	while(j<line.length())
    	{
    		if(k==-1 || line[j]==line[k])//k为-1或字符相等时
    		{
    			j++;
    			k++;
    			if(line[j]!=line[k])
    				nextval[j]=k;
    			else
    				nextval[j]=nextval[k];
    		}
    		else k=nextval[k];
    	}
    }
    
    int KMP(string &substr,string &line)//kmp算法实现
    {
    	int sl=substr.length();
    	int ll=line.length();
    	int nextval[max_size],i=0,j=0;
    	GetNextval(line,nextval);
    	while(i< sl&& j<ll)
    	{
    		if(j==-1 || substr[i]==line[j])
    		{
    			i++;
    			j++;
    		}
    		else 
    		{
    			j=nextval[j];
    		}
    		sl=substr.length();
    		ll=line.length();
    	}
    	if(j>=line.length())
    		return (i-line.length());//返回匹配模式串的首字符下标
    	else return -1;//返回不匹配标志
    }
    void Read(FILE *pf)
    {
    	
    	FILE *pf2 = fopen("test.txt", "w"); 
    	if(pf2 == NULL) { 
    		printf("文件写入失败!
    "); 
    		fclose(pf); 
    		exit(0); 
    	} 
    	
    	char ch; 
    	while(!feof(pf)) { 
    		ch = fgetc(pf); 
    		putchar(ch); 
    		fputc(ch, pf2);  
    	} 
    	
    	fclose(pf2); 
    	fclose(pf); 
    	
    	cout<<"文件已成功写入!"<<endl;
    	
    }
    
    
    
    int main()
    {
    	ifstream in("test.ming");
    	string line;
    	int next[max_size];
    	ofstream output("test.cpp");//	
    	while(getline(in,line))//传参:文件,每一行
    	{
    		
    		bool fenhao;
    		if(line[line.length()-1]==';')
    			fenhao=true;
    		else fenhao=false;
    		bool go=false;
    		for(int m=0;m<9;m++)
    		{
    			int i;
    			int x=KMP(line,Ming[m]);
    			if(x!=-1)
    			{
    				go=true;
    				if(m==0||m==1)//chengxu1
    				{
    					for(i=0;i<x;i++)//kongge
    					{
    						output<<line[i];
    					}
    					output<<Cpp[m];
    					
    				}
    				/*else if(m==1)//kaishi
    				{
    				output<<Cpp[1];
    				
    			}*/
    				else if(m==3)//xunhuan
    				{
    					for(i=0;i<x;i++)//kongge
    					{
    						output<<line[i];
    					}
    				output<<Cpp[3];
    					for(i=x+7;i<line.length();i++)
    					{
    						output<<line[i];
    					}	
    					output<<")";
    
    					
    					
    					
    				}
    				else if(m==2)//jieshu
    				{
    					for(i=0;i<x;i++)
    					{
    						output<<line[i];
    					}
    					output<<Cpp[2];
    					
    				}
    				else if(m==4)//shuru
    				{
    					for(i=0;i<x;i++)//kongge
    					{
    						output<<line[i];
    					}
    					output<<Cpp[4];
    					for(i=x+5;i<line.length();i++)
    					{
    						if(line[i]==',') output<<">>";
    						else if(line[i]==';') break;
    						else output<<line[i];
    					}
    					
    				}
    				else if(m==5)//shuchu
    				{
    					for(i=0;i<x;i++)//kongge
    					{
    						output<<line[i];
    					}
    					output<<Cpp[5];
    					for(int i=x+6;i<line.length();i++)
    					{
    						if(line[i]==',') output<<"<<";
    						else if(line[i]==';') break;
    						else output<<line[i];
    						
    					}
    					
    				}
    				else if(m==6)//ruguo
    				{
    					for(i=0;i<x;i++)
    					{
    						output<<line[i];
    					}
    					output<<Cpp[6];
    					for(i=x+5;i<line.length();i++)
    					{
    						output<<line[i];
    					}	
    					output<<")";					
    				}
    				else if(m==7)//zhengxing
    				{
    					for(i=0;i<x-4;i++)//kongge
    					{
    						output<<line[i];
    					}
    					output<<Cpp[7];
    					for(i=0;i<x;i++)
    					{
    						output<<line[i];
    					}
    					
    				}
    				else if(m==8)//shixing
    				{
    					for(i=0;i<x-4;i++)//kongge
    					{
    						output<<line[i];
    					}
    					output<<Cpp[8];
    					for(i=0;i<x;i++)
    					{
    						output<<line[i];
    					}
    					
    				}
    				else  cout<<"文件读取错误!"<<endl;
    			}
    		}
    		if(!go) output<<line;
    		if(fenhao&&go) output<<";";
    		output<<endl;
    	}
    	in.close(); 
    	FILE *pf= fopen("test.cpp", "r"); 
    	Read(pf);
    	return 0;
    }
    
    

     

About IT165 - 广告服务 - 隐私声明 - 版权申明 - 免责条款 - 网站地图 - 网友投稿 - 联系方式
本站内容来自于互联网,仅供用于网络技术学习,学习中请遵循相关法律法规