pda.cpp

实现下推自动机功能 实际上此程序为半自动机

#include<iostream.h>
#include<string.h>
char state;
char stack[10]={'S'};
char ch[10
];
char choice;
int top=0,base=-1; //top, base相当于计数器

void TranFunc(char t,char a,char x)
{
	int j=0;
	
	if(t=='q' && a=='1' && x=='S') 
	{   
		state='q';
		top--;   
	    //cout<<"the choices are :"<<endl;
		
		cout<<"如果选择'1',则将SA压入栈."<<endl;
		cout<<"如果选择'2',则将A压入栈."<<endl;
		cout<<"如果选择'3',则将AS压入栈."<<endl;
		cout<<"Your choice:";
		cin>>choice;
		if(choice=='1') 
			
			{
			  top++;
			 stack[top]='A';
		      top++;
		     stack[top]='S';


		     }    //将SA压入栈
			else if(choice=='2')
			{	 
				
				top++;
				stack[top]='A';

		
			}
			else if(choice=='3')
			{  
			   top++;
				stack[top]='S';
		       top++;
		        stack[top]='A';
		     }    
			
	
        cout<<"the elements of stack are:";//输出每一步中栈内的元素
        while(j<=top) 
		{cout<<stack[j];
		  j++;
		}
		cout<<endl;
	}
	if(t=='q' && a=='0' && x=='S') 
	{
		state='q';
		top--;    //将S弹出栈
		//cout<<"the choices are :"<<endl;
		cout<<"如果选择'1',则将SB压入栈."<<endl;
		cout<<"如果选择'2',则将B压入栈."<<endl;
		cout<<"如果选择'3',则将BS压入栈."<<endl;
		cout<<"Your choice:"<<endl;
		cin>>choice;
		if(choice=='1') 
			
			{
			  top++;
			 stack[top]='B';
		      top++;
		     stack[top]='S';


		     }    //将SA压入栈
			else if(choice=='2')
			{	 
				
				top++;
				stack[top]='B';

		
			}
			else if(choice=='3')
			{  
			   top++;
				stack[top]='S';
		       top++;
		        stack[top]='B';
		     }    
			
		cout<<"the elements of stack are:";
        while(j<=top) 
		{cout<<stack[j];
		  j++;
		}
		cout<<endl;
	}

	if(t=='q' && a=='1' && x=='B') 
	{
		state='q';
		top--;
	
		cout<<"the elements of stack are:";
        while(j<=top) 
		{cout<<stack[j];
		  j++;
		}
		cout<<endl;
	}   

    	if(t=='q' && a=='0' && x=='A') 
	{
		state='q';
		top--;
		       cout<<"the elements of stack are:";
		
        for(int j=0;j<=top;j++) 
		{
			cout<<stack[j];
		  
		}
	   
		cout<<endl;
       
       		
	}

  

}  //构造PDA 

void main()
{
	int i,len;
	cout<<"含有相同个数的0和1组成的所有的0,1串"<<endl;
	cout<<"其文法为S->1S|0S|1S0|0S1|01S|10S"<<endl;
	cout<<"化为格雷巴赫范式为:"<<endl;
	cout<<"S->1A|1AS|1SA"<<endl;
	cout<<"S->0B|0BS|0SB"<<endl;
	cout<<"A->0"<<endl;
	cout<<"B->1"<<endl;

	cout<<"Please input the string you want to test :"<<endl;
	i=0;
	
	
		cin>>ch;
	
		
	//输入字符串，并以"?"结束道

        
	
	len=strlen(ch);  //字符串的长度

	i=0;
    
	state='q';
	while(i<len)
	{
		TranFunc(state,ch[i],stack[top]);
		i++;
	}
   if (top==base) //空栈接收
	   cout<<"the string you input can be accepted by this PDA!"<<endl;
	else
		cout<<"the string you input can't be accepted by this PDA!"<<endl;
}