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

翻译计划

    小明初学者C++,它确定了四个算术、关系运算符、逻辑运算、颂值操作、输入输出、使用简单的选择和循环结构。但他的英语不是很好，记住太多的保留字，他利用汉语拼音的保留字，小屋C++，发明了一种表达自己思想的算法描写叙述规则。

    规则非常easy：他将開始程序头部以一个拼音名字标记，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 9using namespace std;string Ming[MaxNum]={
"chengxu1",//
"kaishi",
"jieshu",
"xunhuan",
"shuru",
"shuchu",
"ruguo",
"zhengxing",
"shixing"
};
string Cpp[MaxNum]={
"#include <iostream>\n#include <string>\nusing namespace std;\nvoid 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("文件写入失败!\n");
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;
}