polynomial.cpp

这个是编译原理课程的词法分析器

// 
// 多项式的定义。
//

#include "stdlib.h"
#include "stdio.h"

/* 
 * 多项式的定义,采用单链表作为存储结构
 * Polynode表示结点，用Polynomial定义链表的头指针
 */
typedef struct node{
	double coef;         //系数
	int exp;             //指数
	struct node *next;
}Polynode,*Polynomial; 

/*
 * 出错时调用Error，显示错误提示信息
 */
void error(char *s){
	fprintf(stderr,"%s\n",s);
	exit(1);
}

/*
 * 创建一个结点p,参数coef和exp是结点代表的相应项的系数和指数
 */
Polynode* createNode(double coef,int exp){
	// 为结点分配空间
	Polynode *p=(Polynode*)malloc(sizeof(Polynode));
	if(!p)
		error("分配失败");
	p->coef=coef;
	p->exp=exp;
	p->next=NULL;  
	return p;
}

/*
 * 插入操作，在链表的末尾插入一个结点newnode
 */
void insertNode(Polynomial p,Polynode *newnode){
	Polynode *q=p;
	//找到链表的末尾,循环结束时,p指向最后一个结点
	while(q->next!=NULL)
		q=q->next;
	q->next=newnode;   
}

/*
 * 按照指数由小到大的次序输入多项式的系数和指数.
 * 根据输入,创建多项式对应的单链表p(带头结点),m为多项式的项数
 * 多项式对应的单链表中结点也按照指数由小到大排列.
 */
Polynomial createPolynomial(int m){
	double coef;
	int exp,i=1;
	Polynode *newnode;
	Polynomial p;	
	// 创建头结点	
	newnode=createNode(0,0);	
	// p指向头结点
	p=newnode;		
	// 依次创建多项式各项对应的结点
	while(i<=m){	
		printf("系数=");scanf("%lf",&coef);
		printf("指数=");scanf("%d",&exp);
		newnode=createNode(coef,exp);
		insertNode(p,newnode);			
		i=i+1;
	}	
	return p;
}

/* 
 * 将currentnode之后的结点复制到p的末尾.
 */ 
void append(Polynomial p,Polynode *currentnode){
	Polynode *newnode,*q;
	// 找到链表p的尾结点q
	q=p;
	while(q->next)
		q=q->next;

	// 复制currentnode指向的每一个结点，链入p的末尾
	while(currentnode){	
		newnode=createNode(currentnode->coef,currentnode->exp);
		q->next=newnode;
		q=q->next;
		currentnode=currentnode->next;
	}
}

/*
 * 按照指数从小到大的次序输出多项式.
 */
void outputPolynomial(Polynomial p){
	Polynode *currentnode;
	currentnode=p->next;
	if(!currentnode)
		error("Polynomial is null");
	// 输出第一项
	printf("%lfx^%d",currentnode->coef,currentnode->exp);
	currentnode=currentnode->next;

	while(currentnode){
		if(currentnode->coef>0)
			printf("+");
		printf("%lfx^%d",currentnode->coef,currentnode->exp);
		currentnode=currentnode->next;
	}	 
	printf("\n");
}

/*
 * 释放链表占用的空间.
 */
void freePolynomial(Polynomial p){
	Polynode *q;  
	while(p){   
		q=p;p=p->next;
		free(q);	   
	}
}

/* 
 * 两个多项式相加
 * pa+pb=pc
 */
Polynomial addPolynomial(Polynomial pa,Polynomial pb){
	Polynomial pc;
	Polynode *currenta,*currentb,*newnode;	
	double coef;
	currenta=pa->next;
	currentb=pb->next;
	newnode=createNode(0,0);	// 创建链表pc的头结点	
	pc=newnode;								//pc指向头结点	
	while(currenta&&currentb){	  
		if(currenta->exp>currentb->exp){	   
			newnode=createNode(currentb->coef,currentb->exp);
			insertNode(pc,newnode);
			currentb=currentb->next;
		}else if(currenta->exp<currentb->exp){
			newnode=createNode(currenta->coef,currenta->exp);
			insertNode(pc,newnode);
			currenta=currenta->next;
		}else{ 
		 	// 代表currenta->exp==currentb->exp	   
			coef=currenta->coef+currentb->coef;
			if(coef!=0){		   
				newnode=createNode(coef,currenta->exp);
				insertNode(pc,newnode);			   
			}
			currenta=currenta->next;currentb=currentb->next;		   
		}
	}
	// 将pa中剩余的节点加入pc中
	if(currenta)
		append(pc,currenta);
	// 将pb中剩余的节点加入pc中
	if(currentb)
		append(pc,currentb);
	return pc;
}
	
/*
 * 对多项式p求导
 */
void derivate(Polynomial p){
	Polynode *currentnode=p->next;
	while(currentnode){	
		currentnode->coef=currentnode->coef*currentnode->exp;
		currentnode->exp=currentnode->exp-1;
		currentnode=currentnode->next;	
	}	
}	

/*
 * 显示菜单内容.
 */
void showMenu(){
	printf("--------------------------\n");
	printf("         1.求和\n");
	printf("         2.求导\n");
	printf("         3.退出\n");
	printf("--------------------------\n");
	printf("请输入要进行的操作[1或2或3]:"); 
}

/*
 * 主程序
 */
void main() {
	Polynomial pa,pb,pc;	
	int choice,num;
	while(true){
		showMenu();			scanf("%d",&choice);		printf("\n");	   
		switch(choice){	   
			// 求和
			case 1:
				printf("请输入多项式1的项数:");	scanf("%d",&num);
				printf("按照指数从小到大的次序，输入多项式1的系数和指数\n");
				pa=createPolynomial(num);			   
				printf("请输入多项式2的项数:");	scanf("%d",&num);
				printf("按照指数从小到大的次序，输入多项式2的系数和指数\n");
				pb=createPolynomial(num);				pc=addPolynomial(pa,pb);
				printf("多项式1:");				outputPolynomial(pa);		
				printf("多项式2:");				outputPolynomial(pb);
				printf("求和的结果:");		outputPolynomial(pc);				
				// 释放空间
				freePolynomial(pa);		freePolynomial(pb);		freePolynomial(pc);
				break;
			// 求导
			case 2:
				printf("请输入多项式的项数:");  scanf("%d",&num);
				printf("按照指数从小到大的次序，输入多项式的系数和指数\n");
				pc=createPolynomial(num);
			  printf("输入的多项式:");  outputPolynomial(pc);
			  derivate(pc);
			  printf("求导的结果:");	  outputPolynomial(pc);
				freePolynomial(pc);
			  break;		   
			// 退出
			case 3:
		 		exit(0);
			// 错误的输入
			default:
				printf("输入错误\n");
				exit(0);
		}    
	}
}