表达式求值C语言实验报告.docx

表达式求值实验报告 李一鹏 P 数学系 实验题目：表达式求值 实验目的：熟悉栈与队列 实验内容： 话说令狐冲只告诉东方不败：“东方姑娘你会永远活在我的心中。”东方姑娘听了那是万念俱灰啊，精通算术的东方姑娘一时想不开，抛给令狐冲一个表达式，说：“这个表达式你要是不能在一秒内给我把值求出来我就要坠入悬崖！”令狐冲一看事态不对，马上发动辟邪剑法之求助观众！ 观众们，你们又不是不知道令狐冲的那个笨，东方姑娘的生命可以说是掌握在你们的手中了，喜欢她就99她吧！ 算法分析： 本算法采用了链表来储存表达式，加入了指数运算和函数还有常数π。由于指数运算是右结合，本算法先全部储存表达式再优先级一个个运算。对于函数和括号，本算法用了递归，遇到右括号即返回，把表达式的直接求解operate（）转化成了无括号无函数表达式的求解calculate（）。 程序清单： #includestdio.h #includestdlib.h #includeprocess.h #includemath.h #define new1 (no*)malloc(sizeof(no)) #define deletenode p2-prec=p1-prec;free(p1);p1=p2-prec;p1-next=p2 #define error1 p1=head;p2=head- next;if(p2){while(p2!=r){free(p1);p1=p2;p2=p2-next;}free(p1);p2-ope=1;return p2;}else{p1-ope=1;return p1;} #define fun(a,b,c) if(!numbegin)if(getchar()==a)if(getchar()==b)if(getchar()==(){p=operate();if(p-ope){r-next=p;r=p;error1;}num2=c(p-num);free(p);numbegin=1;numend=1;}else{error1;}else{error1;}else{error1;} #define datadeal p=new1;p-num=(num1+num2)*minus;isfloat=0;num1=0;num2=0;minus=1;numbegin=0;flength=1;numend=0;r-next=p;p-prec=r;r=p;p-ope=c typedef struct numope{ double num; char ope; struct numope *prec,*next; }no; no *calculate(no *head,no *rear){ no *p1,*p2; p2=rear; p1=rear-prec; while(p1!=head) if(p1-ope==^){ p2-num=pow(p1-num,p2-num); deletenode; }else{ p2=p1; p1=p1-prec; } while(p1!=rear){ p2=p1-next; if(p1-ope==*){ p2-num=p1-num*p2-num; deletenode; } if(p1-ope==/){ p2-num=p1-num/p2-num; deletenode; } p1=p2; } p1=head;p2=head-next; while(p1!=rear){ p2=p1-next; if(p1-ope==+){ p2-num=p1-num+p2-num; deletenode; } if(p1-ope==-){ p2-num=p1-num-p2-num; deletenode; } p1=p2; } free(head); return rear; } no *operate(){ char c,flength,numbegin,numend,isfloat; double num2; int num1,minus; no *head,*p,*r,*p1,*p2; num1=0;num2=0;minus=1;numbegin=0;numend=0;isfloat=0;flength=1;r=head=new1;head-ope=0;head-next=0; c=getchar(); while(c!=)c!=#){ if(c=48c=57){ if(numend){error1;} numbegin=1; if(i