www.pudn.com > program4.rar > program4.cpp

// program4.cpp : Defines the entry point for the console application. 
// 
/* 程序名称：算符优先分析程序 */ 
/* 
G[E]: 
    E→E+T∣E-T∣     
    T→T*F∣T/F∣F 
    F→(E)∣i 
 
各算符对应的下标如下: 
0  1  2  3  4  5  6  7 
+  -  *  /  (  )  i  # 
该算符优先分析的优先关系矩阵用二维数组表示为： 
int table[8][8]={ 
	{ 1, 1,-1,-1,-1, 1,-1, 1},   
	{ 1, 1,-1,-1,-1, 1,-1, 1},   
	{ 1, 1, 1, 1,-1, 1,-1, 1},   
	{ 1, 1, 1, 1,-1, 1,-1, 1},   
	{-1,-1,-1,-1,-1,-1,-1, 0},   
	{ 1, 1, 1, 1, 0, 1, 0, 1},   
	{ 1, 1, 1, 1, 0, 1, 0, 1},   
	{-1,-1,-1,-1,-1, 0,-1,-1} 
};   
*/ 
#include "stdafx.h" 
#include "stdio.h"   
#include "malloc.h"   
 
char token[100],in[200]; 
int n=0; 
int i=0; 
int flag; 
FILE *fp; 
 
void turn() 
{ 
	char ch; 
	ch =fgetc(fp); 
	while(ch != EOF) 
	{ 
		switch(ch) 
		{ 
		case'\n':break; 
		case' ':break; 
		case'\0':break; 
		default:in[i]=ch;i++;break; 
		} 
		ch =fgetc(fp); 
	} 
	in[i]='\0'; 
	printf("____________输入串为___________\n"); 
	printf("            "); 
	for(i=0;in[i]!='\0';i++) 
	{ 
		if((in[i]=='2' )&& (in[i+1]=='9'))  flag=i+5; 
	} 
	for(i=flag;in[i]!=';';i++) 
	{ 
		if((in[i]=='[')&&(in[i+1]=='2')&&(in[i+2]=='1'))  {token[n]='+';n++;} 
		if((in[i]=='[')&&(in[i+1]=='2')&&(in[i+2]=='2'))  {token[n]='-';n++;} 
        if((in[i]=='[')&&(in[i+1]=='2')&&(in[i+2]=='3'))  {token[n]='*';n++;} 
		if((in[i]=='[')&&(in[i+1]=='2')&&(in[i+2]=='5'))  {token[n]='(';n++;} 
		if((in[i]=='[')&&(in[i+1]=='2')&&(in[i+2]=='6'))  {token[n]=')';n++;} 
        if((in[i]=='[')&&(in[i+1]=='3')&&(in[i+2]=='0'))  {token[n]='/';n++;} 
        if((in[i]=='[')&&(in[i+1]=='3')&&(in[i+2]=='7'))  {token[n]='i';n++;} 
		if((in[i]=='[')&&(in[i+1]=='3')&&(in[i+2]=='8'))  {token[n]='i';n++;} 
	} 
 	token[n]='#'; 
    for(i=0;i<=n;i++) 
	{ 
		printf("%c",token[i]); 
	} 
	printf("\n"); 
	printf("_______________________________\n"); 
//	printf("\n"); 
} 
/*****************************************************************************/ 
 
struct Lchar 
{  
	char char_ch;  
	struct Lchar *next; 
}LLchar,*p,*h,*temp,*top,*base; 
 
int table[8][8]={ 
	{ 1, 1,-1,-1,-1, 1,-1, 1},   
	{ 1, 1,-1,-1,-1, 1,-1, 1},   
	{ 1, 1, 1, 1,-1, 1,-1, 1},   
	{ 1, 1, 1, 1,-1, 1,-1, 1},   
	{-1,-1,-1,-1,-1,-1,-1, 0},   
	{ 1, 1, 1, 1, 0, 1, 0, 1},   
	{ 1, 1, 1, 1, 0, 1, 0, 1},   
	{-1,-1,-1,-1,-1, 0,-1,-1} 
};   
 
char curchar;   
char curcmp;   
int right;  
int j;   
int k;//比较字符在栈的位置 
 
void push(char pchar)//模拟进栈，链表尾部为栈底元素 
{   
	temp=(Lchar*)malloc(sizeof(LLchar));   
	temp->char_ch=pchar;   
	temp->next=top;   
	top=temp;   
}   
 
void pop()//模拟出栈 
{   
	if(top->char_ch!='#')   
		top=top->next;   
}   
 
int changchartoint(char ch)//将字符转为数字，以得到算符优先值   
{   
	int t;   
	switch(ch)   
	{   
	case '+':t=0;break;   
	case '-':t=1;break;   
	case '*':t=2;break;   
	case '/':t=3;break;   
	case '(':t=4;break;   
	case ')':t=5;break;   
	case 'i':t=6;break;   
	case '#':t=7;   
	}   
	return t;   
}   
 
void dosome()   
{   
	k=1;   
	for(;;)   
	{   
		curchar=h->char_ch;   
		temp=top; 
		for(;;)   
		{   
			if(temp->char_ch=='N')   
			{   
				temp=temp->next;   
				k++;   
			}   
			else   
			{   
				curcmp=temp->char_ch; 
				break;   
			}   
		}  
		printf("\n"); 
		temp=top;   
	    n=0; 
		for(;;)//打印分析栈中字符 
		{   
			in[n]=temp->char_ch;n++; 
			if(temp->char_ch=='#')   
				break;   
			else   
				temp=temp->next;   
		}   
		for(i=n-1;i>=0;i--) 
		{ 
			printf("%c",in[i]); 
		} 
		printf("\t");   
		temp=h;   
		for(;;)//打印输入串中剩余字符  
		{   
			printf("%c",temp->char_ch);   
 
			if(temp->char_ch=='#')   
				break;   
			else   
				temp=temp->next;   
		}   
		i=changchartoint(curcmp);   
		j=changchartoint(curchar);   
		if(table[i][j]==0)//算符优先关系为空,即对应数组元素为0 
		{   
     		printf("\n%c\t%c\tERROR!\n----算符优先关系为空",curcmp,curchar);   
			right=0;   
			break;   
		}   
		else//算符优先关系不为空 
		{   
			if(table[i][j]<0)//算符优先值为-1，准备移进 
			{   
				if(curchar=='#')//剩余字符串为空 
				{   
					if(k==2)//当前比较字符在栈的位置为两个元素   
						break;   
					else 
					{   
 						printf("\n%c\t%c\tERROR!\n----未规约到N",curcmp,curchar);   
						right=0;   
						break;   
					}   
				}   
				push(curchar);   
				k=1;   
				curcmp=curchar;   
				h=h->next;   
			}   
			else//算符优先值为1，归约   
			{   
				if(curcmp=='i')//当前比较为i,出栈一次   
					pop();   
				else					 
				{ 
					if(top->char_ch!='N'&&curchar=='#') 
					{ 
						printf("\n%c\t%c\tERROR!\n----未规约到N",curcmp,curchar);   
						right=0;   
						break; 
					} 
					pop();   
					pop();   
					pop();   
				}   
				push('N');//归约到N 
				k=1;   
			}   
		}   
	}   
}   
 
void scanner() 
{ 
	char ch;   
	right=1;   
	base=(Lchar*)malloc(sizeof(LLchar));   
	base->next=NULL;   
	base->char_ch='#';   
	top=base;   
	h=(Lchar*)malloc(sizeof(LLchar));   
	h->next=NULL; 
	p=h; 
	for(i=0;i<=n;i++) 
	{ 
		ch=token[i]; 
        if(ch=='i'||ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#') 
		{ 
			temp=(struct Lchar *)malloc(sizeof(Lchar)); 
            temp->next=NULL; 
            temp->char_ch=ch; 
            h->next=temp; 
            h=h->next; 
		} 
		else 
		{ 
			temp=p->next; 
			printf("输入串错误!\n"); 
		} 
	} 
	p=p->next; 
	h=p; 
	dosome(); 
	if(right)   printf("\n此输入串是该文法定义的算术表达式!\n\n"); 
	else	printf("\n此输入串不是该文法定义的算术表达式!\n\n"); 
} 
 
int main(int argc, char* argv[]) 
{ 
	fp=fopen("test.txt", "r"); 
	turn(); 
	scanner(); 
	return 0; 
}