题目：
已知文法G： 试编写一个程序， 判断文法G所能接受的串。
Z->aAcB | Bd
A->cD
D->aBD | d
B->bC
C->BcA | e
以下为stack.h的内容：
#include<iostream.h>
#define maxsize 40
#define increasesize 5
/*****************************************************
建一个栈类
*****************************************************/
class stack
{
int top;
int base;
public:
stack();
~stack();
void push(char);
char pop();
};
以下为stack.cpp的内容：
#include"stack.h"
int Stasize;
char *StaArr;
/*****************************************************
栈的构造函数的实现
*****************************************************/
stack::stack()
{
Stasize = maxsize;
StaArr = new char[Stasize];
top=base=0;
cout<<"stack initialized\n";
}
/*****************************************************
压栈函数的实现
*****************************************************/
void stack::push(char i)
{
if(top-base>=Stasize)
{
Stasize = Stasize + increasesize;
StaArr = new char[Stasize];
}
StaArr[top]=i;
top++;
}
/*****************************************************
弹栈函数的实现
*****************************************************/
char stack::pop()
{
if(top==base)
{
cout<<"stack is empty\n";
}
--top;
int i=top;
char e=StaArr[top];
return e;
}
/*****************************************************
栈的析构函数的实现
*****************************************************/
stack::~stack()
{
delete(StaArr);
}
以下为main.cpp的内容：
#include<string.h>
#include<iostream.h>
#include"stack.h"
stack s;
#define ch_a 0
#define ch_b 1
#define ch_c 2
#define ch_d 3
#define ch_z 4
#define ch_A 0
#define ch_B 1
#define ch_C 2
#define ch_D 3
#define ch_Z 4
char *cha[5][5] = {{ "!" , "!" , "cD" , "!" , "!" }
,{ "!" , "bC" , "!" , "!" , "!" }
,{ "@" , "BcA" , "@" , "@" , "@" }
,{ "aBD" , "!" , "!" , "d" , "!" }
,{"aAcB" , "Bd" , "!" , "!" , "!" }};
int len =0 ;
/*****************************************************
输入字符串列已确定跟字符指针数组的行进行比较的函数实现
*****************************************************/
void Run(int tempint , char ch , char stacha )
{
int j ;
if(stacha == 'Z')
{
char *ArrTemp;
int c = strlen(cha[ch_Z][tempint]);
ArrTemp = new char[c];
strcpy(ArrTemp,cha[ch_Z][tempint]);
j = c -1 ;
while(j >= 0)
{
s.push(ArrTemp[j]);
j--;
}
}
else if(stacha == 'A')
{
char *ArrTemp;
int c = strlen(cha[ch_A][tempint]);
ArrTemp = new char[c];
strcpy(ArrTemp,cha[ch_A][tempint]);
j = c -1 ;
while(j >= 0)
{
s.push(ArrTemp[j]);
j--;
}
}
else if(stacha == 'B')
{
char *ArrTemp;
int c = strlen(cha[ch_B][tempint]);
ArrTemp = new char[c];
strcpy(ArrTemp,cha[ch_B][tempint]);
j = c -1 ;
while(j >= 0)
{
s.push(ArrTemp[j]);
j--;
}
}
else if(stacha == 'C')
{
char *ArrTemp;
int c = strlen(cha[ch_C][tempint]);
ArrTemp = new char[c];
strcpy(ArrTemp,cha[ch_C][tempint]);
j = c -1 ;
while(j >= 0)
{
s.push(ArrTemp[j]);
j--;
}
}
else if(stacha == 'D')
{
char *ArrTemp;
int c = strlen(cha[ch_D][tempint]);
ArrTemp = new char[c];
strcpy(ArrTemp,cha[ch_D][tempint]);
j = c -1 ;
while(j >= 0)
{
s.push(ArrTemp[j]);
j--;
}
}
else if(stacha == '@' )
{
return ;
}
else if(stacha == ch )
{
len++;
return ;
}
}
/*****************************************************
输入字符串跟字符指针数组的列进行比较的函数实现
*****************************************************/
bool Compare(char *bStr , int strsize)
{
char ch , stacha ;
stacha = s.pop();
while(stacha != '#')
{
switch(bStr[len])
{
case'a':
ch = 'a' ;
Run(ch_a , ch , stacha );
break;
case'b':
ch = 'b' ;
Run(ch_b , ch , stacha );
break;
case'c':
ch = 'c' ;
Run(ch_c , ch , stacha );
break;
case'd':
ch = 'd' ;
Run(ch_d , ch , stacha );
break;
case'#':
ch = '#' ;
Run(ch_z , ch , stacha );
break;
default:
break;
}
if(stacha == '!' )
return false;
stacha = s.pop();
}
if(bStr[len] == '#' )
return true;
else
return false;
}
/*****************************************************
主函数的实现
*****************************************************/
void main( )
{
char str[20];
char *bStr;
s.push('#');
s.push('Z');
int strsize;
cout<<"请输入一串字符,字符只能为a,b,c,d中的:"<<"\n";
cin>>str;
strsize = strlen(str);
bStr = new char[strsize+1];
strcpy(bStr , str);
bStr[strsize] = '#';
if(Compare(bStr , strsize))
cout<<"此句子满足文法\n";
else
cout<<"此句子不满足文法\n";
}
