#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
struct Euqation
{
char
left;
vector<char>
right;
}eq;
vector<Euqation> x, p1,
p2;
vector<char>vn1, vn2, vt,
vt2;
//判断是否是终结符号，是的话返回true
bool isvt(char x) {return !(x >= 'A'
&& x <= 'Z');}
//判断字符tmp是否在集合y中
bool IsIn(char tmp, vector<char>
y)
{
for(int
i = 0; i < y.size(); i++) if (y[i] == tmp) return
true;
return
false;
}
void input()
{
char
str[1024];
while(scanf("%s", str)
&& strcmp(str, "0") != 0)
{
int len = strlen(str);
eq.left = str[0];
eq.right.clear();
for(int i = 2; i
< len; i++)
{
eq.right.push_back(str[i]);
if (isvt(str[i])) vt.push_back(str[i]);
}
x.push_back(eq);
}
}
//算法2.1
void Algorithm1()
{
bool
flag = true;
while(flag)
{
flag = false;
for(int i = 0; i
< x.size(); i++)
{
for(int j = 0; j <
x[i].right.size(); j++)
if
(!(IsIn(x[i].right[j], vn1) || IsIn(x[i].right[j], vt)))
break;
else if (j
== x[i].right.size() - 1 &&
!IsIn(x[i].left, vn1))
vn1.push_back(x[i].left), flag
= true;
}
}
for(int
i = 0; i < x.size(); i++)
{
eq.right.clear();
if (!(IsIn(x[i].left, vn1) ||
IsIn(x[i].left, vt))) continue;
for(int j = 0; j
< x[i].right.size(); j++)
if (!(IsIn(x[i].right[j], vn1) ||
IsIn(x[i].right[j], vt))) break;
else
{
eq.right.push_back(x[i].right[j]);
eq.left =
x[i].left;
if (j ==
x[i].right.size() - 1) p1.push_back(eq);
}
}
}
//算法2.2
bool vst[1024];
void Algorithm2()
{
vn2.push_back('S');
bool
flag = true;
memset(vst, 0, sizeof(vst));
while(flag)
{
flag = false;
for(int i = 0; i
< p1.size(); i++)
if (!vst[i] &&
IsIn(p1[i].left, vn2))
{
vst[i] =
flag = true;
for(int j =
0; j < p1[i].right.size(); j++)
if (isvt(p1[i].right[j]))
vt2.push_back(p1[i].right[j]);
else
vn2.push_back(p1[i].right[j]);
}
}
for(int
i = 0; i < p1.size(); i++)
{
eq.right.clear();
if (!(IsIn(p1[i].left, vn2) ||
IsIn(p1[i].left, vt2))) continue;
for(int j = 0; j
< p1[i].right.size(); j++)
if (!(IsIn(p1[i].right[j], vn2) ||
IsIn(p1[i].right[j], vt2))) break;
else
{
eq.right.push_back(p1[i].right[j]);
if (j ==
p1[i].right.size() - 1)
{
eq.left = p1[i].left;
p2.push_back(eq);
}
}
}
printf("答案 = {\n");
for(int
i = 0; i < p2.size(); i++)
{
printf("%c=",
p2[i].left);
for(int j = 0; j
< p2[i].right.size(); j++) printf("%c",
p2[i].right[j]);
printf("\n");
}
printf("}\n");
}
int main()
{
printf("说明：\n1:默认S为开始符号\n2:一行一个句型\n3:句型格式为：\"A=abc\",没有空格，大小写规定和课本一样\n");
printf("4:最后一行输入一个数字0表示结束\n");
while(true)
{
vt.clear(); x.clear();
vn1.clear();
vn2.clear();
input();
printf("输入结束，开始执行算法2.1:\n");
Algorithm1();
printf("算法2.1结束，开始执行算法2.2:\n");
Algorithm2();
}
return
0;
}
加载中，请稍候......
加载中…
喜欢