C语言_算数表达式求值_课程设计报告.doc

目 录一概述2二总体方案设计3三详细设计4四程序的调试与运行结果说明5五课程设计总结6参考文献7附录.8 一 概述一、课程设计的目的与要求本课程设计是为了配合数据结构课程的开设,通过设计一个完整的程序,使学生掌握数据结构的应用,算法的编写,类C语言的算法转换成C程序并用Turbo C2.0或Visual C+6.0上机调试的基本方法。要求如下: 1.要充分认识课程设计对自己的重要性,认真做好课程设计前的各项准备工作。 2.既要虚心接受老师的指导,又要充分发挥主观能动性.结合课题,独立思考,努力钻研,勤于实践,勇于创新。 3.独立按时完成规定的工作任务,不得弄虚作假,不准抄袭他人内容,否则成绩以不及格计。 4.课程设计期间,无故缺席按旷课处理;缺席时间达四分之一以上者,其成绩按不及格处理。 5.在设计过程中,要严格要求自己,树立严肃,严密,严谨的科学态度,必须按时,按质,按量完成课程设计。 6.小组成员之间,分工明确,但要保持联系畅通,密切合作,培养良好的互相帮助和团队协作精神。二、需求分析本课程设计的课题为表达式求值，要求：1.用户将表达式原样输入（在表达式结尾加上#），能得出结果（为减小难度，运算结果的10进制形式的值，不超过longdouble的存储范围）；2.输入的数可以为小数（为减小难度，小数的整数与小数部分均不超过10位），负数（如果负数前有运算符，则应将负数括起来），以及2进制，8进制，10进制，16进制的数（为减小难度，数出的结果都以10进制形式表示）；3.运算符号包括（）、+、*、/；括号可以多重；二 总体方案设计1.使用双链表的数据结构表示数据的存储，将用户输入的表达式以字符形式存入双链表中。2.对以负数开头、以括号开头、左括号后紧跟负数的特殊情况作处理。3.将数与运算符分开；4.依次找到表达式最内层括号，次内层括号.每次找到括号内的表达式，便将其进行只有 加减乘除运算的计算。结构体类型：/用来存储字符的结点类型typedef struct CharNodechar c;struct CharNode *next;CharNode;/用来存储数的结点类型typedef struct IntNodelong double i;struct IntNode *next;IntNode;/用来存储数的结点类型typedef struct Nodelong double n;struct Node_ys_char *next;Node;/用来存储运算符的结点类型typedef struct Node_ys_charchar c;struct Node_ys_char *next_c;struct Node *next;Node_ys_char;三 详细设计我任务是整个程序的算法设计，以及部分子函数的编写，经过其他组员编写的子函数的处理，将表达式变为一个普通的表达式，其中数与运算符已经分开，将这个表达式的头指针传递到我所编写函数中，运算思想为：找到最内层的一对括号，计算括号间的表达式的值，得到值之后，用这个值替换掉原始位置上的一对括号，以及其中的表达式。例如（6.5-2*2.25）*2-6）/2+1.5）+3#，第一次替换后为（2*2-6）/2+1.5）+3#，第二次替换后为（-2/2+1.5）+3#，第三次替换后为0.5+3#，当没有括号时调用四则运算函数直接计算。如果一开始输入的表达式中没有括号，则直接调用四则运算函数进行计算。整个程序的算法思想见流程图。函数的功能如下：char Precede(char x,char y) 运算符优先级判断CharNode *CreatRegister()输入表达式，并对特殊情况做处理Node *StackChange(CharNode *top,int m)将数与运算符分开，并将其他进制转化为10进制Node *Compute(Node *p)作只有加减乘除运算的表达式求值Node *GetOutcome(Node *head)求用户输入表达式的值main（）主函数主要部分的详细流程图）开始输入表达式特殊情况处理将数与运算符分开找到最内层一堆括号将括号内表达式用指针带出将括号内表达式用指针带出进行只有加减乘除运算表达式求值用表达式值替换掉括号及括号间表达式取当前表达式首指针进行只有加减乘除运算表达式求值得出结果否是循环四 程序的调试与运行结果说明在编写只有加减乘除的表达式求值的表达式求值时，原始思想是用两个指针分别指向相邻的两个运算符，若后者大，则进行后面运算符的运算，然后指针继续后移，当再次遇到的两个运算符，前者与后者相等，则进行前面运算符的运算；此算法思想错误，导致计算6+2*3+1#结果正确，而当计算6-2*3+1#时，却得出-1的错误结果，正确结果为+1；这是因为先计算2*3得到6；表达式变为6-6+1#；接着进行6+1的运算，得到7；当前计算循序错误，导致结果错误。后来将程序改为先进行优先级高的运算符的运算，当优先级相等时，不计算。指针后移，当遇到表达式结束标志时，便将指针移到表达式的头位置，此时，判断是否进行运算的条件发生变化，当前后运算符的优先级相等时，进行前面运算符的运算；使得第一次将乘除运算符运算完，第二进行只有加减运算符的运算五 课程设计总结进过调试程序能得出大多数表达式的正确结果，虽然经过了一些特殊情况表达式的输入，得出了正确结果，但不排除还有某些漏洞使得一些特殊情况的表达式不能得出正确结果，还有待进一步的测试。特点：本程序能进行小数、以及2进制、8进制、16进制的运算。不足：结果都以10进制形式表示，用户不能改变；结果的10进制形式不能超出longdouble型数据能存储的数的范围；进一步的设想：将数分段存储，内存动态分配，使其能进行天文数字运算；录入其他的运算符例如指数运算，开方运算，取余运算，解一元一次方程，解二元一次方程组。附录：源代码：/用来存储字符的结点类型typedef struct CharNodechar c;struct CharNode *next;CharNode;/用来存储数的结点类型typedef struct IntNodelong double i;struct IntNode *next;IntNode;/用来存储数的结点类型typedef struct Nodelong double n;struct Node_ys_char *next;Node;/用来存储运算符的结点类型typedef struct Node_ys_charchar c;struct Node_ys_char *next_c;struct Node *next;Node_ys_char;char Precede(char x,char y)/运算符优先级判断 int i,j;int from55=0,0,-1,-1,0,0,0,-1,-1,0,1,1,0,0,1,1,1,0,0,1,0,0,-1,-1,0;/定义一个二维数组存放算术符号的优先级 switch(x)case +:i=0;break;case -:i=1;break;case *:i=2;break;case /:i=3;break;case #:i=4;break;switch(y)case +:j=0;break;case -:j=1;break;case *:j=2;break;case /:j=3;break;case #:j=4;break;if(fromij=1)/说明运算符i的优先级比j的优先级高return ;if(fromij=-1)return c);scanf(%c,&p-c);if(q-c=-)p=(CharNode *)malloc(sizeof(CharNode);p-c=0;p-next=q;top=p;p=q;if(q-c=()e=(CharNode *)malloc(sizeof(CharNode);e-c=0;p=(CharNode *)malloc(sizeof(CharNode);p-c=+;e-next=p;p-next=q;p=q;top=e;while(p-c!=#)q=(CharNode *)malloc(sizeof(CharNode);scanf(%c,&q-c);if(p-c=()&(q-c=-)e=(CharNode *)malloc(sizeof(CharNode);e-c=0;e-next=q;p-next=e;p=q;elsep-next=q;p=q;p-c=+;p-next=(CharNode *)malloc(sizeof(CharNode);p-next-c=0;p=p-next;p-next=(CharNode *)malloc(sizeof(CharNode);p-next-c=#;return top;/将数与运算符分开，并将其他进制转化为10进制Node *StackChange(CharNode *top,int m)CharNode *p,*q;long double x=0,y=0;char a10,b10;int n=0,i=0,JiWei,max,min=47,mark_1=0,mark_2=0,h,k=0;Node *node,*head;Node_ys_char *node_char;switch(m)case 2:JiWei=2;max=50;break;case 8:JiWei=8;max=56;break;case 10:JiWei=10;max=97;break;case 16:JiWei=16;max=103;break;p=q=top;while(p-c !=#)while(q-cmin)&(q-cc=46)if(q-c=46)mark_1=1;q=q-next;if(mark_1=0)an=q-c;q=q-next;n+;if(mark_1=1)bi=q-c;q=q-next;i+;for(h=n-1;h=0;h-)x=(an-h-1-48)*pow(JiWei,h)+x;/for(h=0;hn=x+y;mark_1=0;n=0;i=0;if(mark_2=1)node_char-next=node;node_char=(Node_ys_char *)malloc(sizeof(Node_ys_char);node_char-c=q-c;node-next=node_char;node_char-next_c=NULL;node_char-next=NULL;if(q-c=#)node-next=(Node_ys_char *)malloc(sizeof(Node_ys_char);node-next-c=#;return head;q=q-next;if(q-ccnext_c=(Node_ys_char*)malloc(sizeof(Node_ys_char);node_char-next_c-c=q-c;q=q-next ;/node-next=node_char;node_char=node_char-next_c;node_char-next_c=NULL;node_char-next=NULL;elsenode-next=node_char;node_char-next_c=NULL;node_char-next=NULL;p=q;n=0;x=0;y=0;if(mark_2=0)head=node;mark_2=1;return head;/作只有加减乘除运算的表达式求值Node *Compute(Node *p)int mark=0;Node *m,*n;char max_char,min_char;m=n=p;while(p-next-c!=#)max_char=n-next-c;n=n-next-next;min_char=n-next-c;if(Precede(max_char,min_char)=|mark=1)switch(m-next-c)case +:m-n =m-n + n-n ;break;case -:m-n =m-n - n-n ;break;case *:m-n =m-n * n-n ;break;case /:m-n =m-n / n-n ;break;m-next=n-next;n=m;if(m-next-c=#)m=n=p;mark=1;return m;/求用户输入表达式的值Node *GetOutcome(Node *head)Node *p,*q,*R;Node_ys_char *m,*n,*t,*k;n=(Node_ys_char *)malloc(sizeof(Node_ys_char);n-c=(;p=q=head;while(n-c!=)&(q-next-c!=#)if(q-next-c=()m=q-next;k=m;else if(q-next-next_c=NULL)q=q-next-next;elsem=q-next-next_c;k=q-next;/t=q-next;if(m-c=()t=k;k=m;while(m-next_c!=NULL)m=m-next_c;if(m-c=()t=k;k=m;q=m-next ;if(q-next-c=)n=q