lryouxiansuanfa.cpp

编译原理lr四则运算优先算法

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<string.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define MAXLINE 40

typedef struct{//运算符栈的结构
	char *base;
	char *top;
	int stacksize;
}OpStack;

typedef struct{//运算数栈的结构
	int *base;
	int *top;
	int stacksize;
}NumStack;

char Precede(char c1,char c2){//运算符的优先顺序,返回<,>,=或@(其中@表示c1和c2无比较的关系
	switch(c1){
	case '+'://加号和减号 与其它的运算符的优先顺序相同	
	case '-':	if(c2=='*' || c2=='/' || c2=='(') return '<';
				else return '>';
	case '*'://乘号和除号 与其它的运算符的优先顺序相同
	case '/':	if(c2=='(') return '<';
				else return '>';
	case '(':	if(c2==')' || c2=='#'){
					if(c2==')') return '=';
					else return '@';
				}
				else return '<';
	case ')':	if(c2=='(') return '@';
				else return '>';
	case '#':   if(c2==')' || c2=='#'){
					if(c2=='#') return '=';
					else return '@';
				}
				else return '<';
	default:	return '@';//无法比较,则返回@
	}
}
void Init_OpStack(OpStack &S){//构造一个运算符的空栈S
	S.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char));//分配一个大小为STACK_INIT_SIZE的空间
	if(!S.base) return;//存储分配失败
	S.top=S.base;
	S.stacksize=STACK_INIT_SIZE;
}
void Init_NumStack(NumStack &S){//构造一个运算数的空栈S
	S.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int));
	if(!S.base) return;//存储分配失败
	S.top=S.base;
	S.stacksize=STACK_INIT_SIZE;
}
void Print_OpStack(OpStack S){//若运算符栈不空,则打印栈的内容;否则就不打印
	while(S.base!=S.top)//判断栈是否为空
		printf("%c",*S.base++);
	printf("\t\t");
}

void Print_NumStack(NumStack S){//若运算符数不空,则打印栈的内容;否则就不打印
	while(S.base!=S.top)//判断栈是否为空
		printf("%d ",*S.base++);
	printf("\t\t");
}

void Destroy_OpStack(OpStack &s){//销毁运算符栈S
	free(s.base);
	return;
}

void Destroy_NumStack(NumStack &s){//销毁运算数栈S
	free(s.base);
	return;
}
void Op_Push(OpStack &S,char e){//插入e为新的运算符栈的栈顶元素
	if(S.top-S.base>=S.stacksize){//栈满,追加存储空间
		S.base=(char *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char));
		if(!S.base) return;//存储分配失败
		S.top=S.base+S.stacksize;
		S.stacksize+=STACKINCREMENT;
	}
	*S.top++=e;
}
void Num_Push(NumStack &S,int e){//插入e为新的运算数栈的栈顶元素
	if(S.top-S.base>=S.stacksize){//栈满,追加存储空间
		S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int));
		if(!S.base) return;//存储分配失败
		S.top=S.base+S.stacksize;
		S.stacksize+=STACKINCREMENT;
	}
	*S.top++=e;
}
void Op_Pop(OpStack &S,char &e){//若运算符栈不为空,则删除S的栈顶元素,并用e返回其值;否则不返回.
	if(S.top==S.base) return;
	e=*--S.top;
}
void Num_Pop(NumStack &S,int &e){//若运算数栈不为空,则删除S的栈顶元素,并用e返回其值;否则不返回.
	if(S.top==S.base) return;
	e=*--S.top;
}

void Op_GetTop(OpStack S,char &e){//若运算符栈不为空,则用e返回S的栈顶元素;否则不返回.
	if(S.top==S.base) return;
	e=*(S.top-1);
}
void Num_GetTop(NumStack S,int &e){//若运算数栈不为空,则用e返回S的栈顶元素;否则不返回.
	if(S.top==S.base) return;
	e=*(S.top-1);
}
int Operate(int x,int y,char theta){//把theta转化成相应的运算符号,并返回相应的计算结果.
	switch(theta){
	case '+':	return x+y;
	case '-':	return x-y;
	case '*':	return x*y;
	case '/':	if(y)	return(x/y);//分母y不为0的情况
				else{//分母y为0,则输出计算结果为无穷大,并退出.
					printf("\n计算结果为:无穷大\n");
					fflush(stdin);
					getchar();
					exit(0);
				}
	}
}

int Op(char ch){//判断ch是否为运算符,若是则返回1,否则返回0;
	switch(ch){
	case '+':
	case '-':
	case '*':
	case '/':
	case '(':
	case ')':
	case '#': return 1;
	default:  return 0;
	}
}
void Print(OpStack OPTR,NumStack OPND,char *array,int k){
//参数分别是运算符栈OPTR,运算数栈OPND,是用来输出栈内容的.
//指针array是用来指示输入字符所在位置,k是表示步骤.函数中\t是用来排版用的.
	char c;
	Op_GetTop(OPTR,c);
	printf("%d\t",k);//输出步骤
	Print_OpStack(OPTR);//输出运算符栈内容
	Print_NumStack(OPND);//输出运算数栈内容
	if(strlen(array)>7)	printf("%s\t",array);//若前面OPND栈长度大于7,则跟一个制表符,再输出字符
	else	printf("%s\t\t",array);//否则则先输出两个制表符的长度,再输出字符
	if(Op(*array)){//判断栈OPTR的栈顶元素与当前array所指的运算符的大小关系,若>或=,则不输出主要操作
		if(Precede(c,*array)=='>' || Precede(c,*array)=='=');//否则则输出进OPTR栈的操作,但不输出
		else	printf("PUSH(OPTR,'%c')\n",*array);          //进OPND栈的操作.
	}
}

int EvaluateExpression(OpStack &OPTR,NumStack &OPND,char *str){
//算术表达式求值的算符优先函数.OPTR和OPND分别为运算符和运算数栈,str为输入字符的数组.
//打印运算符栈,运算数栈,输入字符和主要操作的内容,并返回表达式计算的结果.
	char e,theta,*p,*q;
	int temp,n,a,b,i,k,flag=0;//flag是且来控制输出界面
	k=0;	p=str;			//k是用来表示步骤
	Op_Push(OPTR,'#');		//先把#压入OPTR栈底
	Print(OPTR,OPND,p,++k);	//输出步骤1的信息.
	Op_GetTop(OPTR,e);
	while(*p!='#' || e!='#'){
		if(*p!='\0'){//p始终指向有字符的地方
			if(!Op(*p)){//不是运算符,则进运算数栈
				n=*p-48;//把字符输化成相应的整数
				q=p+1;i=1;//用q,i来控制是否为连续字符'0'~'9'.用q来指向当前p所指向的下一个元素
				while(!Op(*q) && *q!='\0'){
					n=n*10+*q-48;//把连续的字符转化成相应的整数
					q++;i++;
				}
				Num_Push(OPND,n);//压入运算数栈
				printf("PUSH(OPND,'%d')\n",n);//输出OPND栈的内容
				p+=i;//p往后移i个位置
				Print(OPTR,OPND,p,++k);//输出步骤k+1的内容
				flag=0;
			}
			else
				switch(Precede(e,*p)){//接收到的字符为运算符,则和运算符栈的栈顶元素相比
										//看是否作计算,还是作进栈,或者出栈操作
					case '<':	Op_Push(OPTR,*p);//栈顶元素优先权低,则直接进运算符栈
								p++;//指针往后移一个位置
								Print(OPTR,OPND,p,++k);
								flag=0;
								break;
					case '=':	Op_Pop(OPTR,theta);//脱括号并接收下一个字符
								p++;//下面的都为控制输出程序段
								if(flag && strlen(p)<7) printf("\t\tPOP(OPTR){消去一对括号}\n");
								else printf("\tPOP(OPTR){消去一对括号}\n");
								printf("%d\t",++k);
								Print_OpStack(OPTR);
								Print_NumStack(OPND);
								printf("%s",p);
								if(Op(*p) && *p!='#'){
									printf("\t\tPUSH(OPTR,'%c')\n",*p);
									flag=0;
								}
								else flag=1;
								break;
					case '>':	Op_Pop(OPTR,theta);//栈顶元素优先权高,则退栈并将运算结果入栈
								Num_Pop(OPND,b);Num_Pop(OPND,a);
								temp=Operate(a,b,theta);//计算结果暂存入temp中
								Num_Push(OPND,temp);
								if(!flag)printf("Operate('%d','%c','%d')\n",a,theta,b);
								else	printf("\t\tOperate('%d','%c','%d')\n",a,theta,b);
								printf("%d\t",++k);
								Print_OpStack(OPTR);
								Print_NumStack(OPND);
								printf("%s",p);
								if(*p!='#' && *p!=')') {
									printf("\t\tPUSH(OPTR,'%c')\n",*p);
									flag=0;
								}
								else flag=1;
								break;
					case '@':	printf("ERROR!");exit(0);//不能计算则输出出错信息,并退出.
			}
			Op_GetTop(OPTR,e);
		}
	}
	if(flag)	printf("\t\tRETURN(GETTOP(OPND))\n");
	else printf("RETURN(GETTOP(OPND))\n");
	Num_GetTop(OPND,temp);//把最后的运算结果压入OPND栈中,成为栈顶元素.
	return temp;
}

void main(){
	OpStack OPTR;
	NumStack OPND;
	int result,i;
	char c,str[MAXLINE];
	do{
		Init_OpStack(OPTR);//创建空栈
		Init_NumStack(OPND);//创建空栈
		printf("请输入算术表达式并与#结束：");
		scanf("%s",str);//把全部的输入字符保存在数组str中
		for(i=0;str[i]!='\0';i++);
		if(str[i-1]!='#'){//判断最后一个字符是否为#,不为#刚输出出错信息.
			printf("ERROR!要以#结束.\n");
			printf("是否继续[Y/N]:");
			fflush(stdin);//清空缓冲器的内容.
			continue;
		}
		printf("-------------------------------------------------------------------------\n");
		printf("步骤\tOPTR栈\t\tOPND栈\t\t输入字符\t主要操作\n");
		printf("-------------------------------------------------------------------------\n");
		result=EvaluateExpression(OPTR,OPND,str);
		printf("-------------------------------------------------------------------------\n");
		printf("计算结果是:%d\n",result);
		Destroy_OpStack(OPTR);//销毁栈
		Destroy_NumStack(OPND);//销毁栈
		printf("是否继续[Y/N]:");
		fflush(stdin);//清空缓冲器的内容.
	}while((c=getchar())=='Y' || c=='y');//接收字符并保存入c中,来作来循环的条件.
}