数据结构表达式求值文档

数据结构课程设计说明书学生姓名:学院:专业:题目:成绩指导教师学号：网络工程利用栈求表达式的值

1．设计目的数据结构课程设计的目的是，通过设计掌握数据结构课程中学到的基本理论和算法并综合运用于解决实际问题中，它是理论与实践相结合的重要过程。设计要求学会如何对实际问题定义相关数据结构，并采用恰当的设计方法和算法解决问题，同时训练学生进行复杂程序设计的技能和培养良好的程序设计习惯。2．设计内容和要求利用栈求解表达式的值。设计内容：1)建立试题库文件，随机产生n个题目；2)题目涉及加减乘除，带括弧的混合运算；3)利用栈求解表达式的值；4)随时可以退出；5)保留历史分数，能回顾历史，给出与历史分数比较后的评价基本要求：1)系统功能的完善；2)代码中有必要的注释3．本设计所采用的数据结构栈的数组表示方法（静态分配整型指针）typedefstruct{typedefdata[MAXSIZE];inttop;};4．功能模块详细设计1.功能一：中缀表达式转化为后缀表达式；2.功能二：后缀表达式求值；3.功能三：文件读写；4.功能四：作业评分；5.功能五：历史成绩本次成绩比较；6.功能六：输入“~”符号退出程序

4.1详细设计思想1.首先实现表达式的求值：要用栈求解一个表达式,就要将这个表达式翻译成正确求值的一个机器指令序列,即正确解释表达式,了解算术四则混合运算的规则：(1).先乘除,后加减;(2).从左算到右;(3).先括号内,后括号外再根据这个运算优先的规定来实现对表达式的编译或解释执行.任何一个表达式都是由操作数(st)和操作符(op)组成的，根据四则运算基本法则，在运算的每一步中，任意两个相继出现的操作符op1和op2之间的优先关系最多有以下3种：(1).op1的优先级低于op2(2).op1的优先级等于op2(3).op1的优先级小于op2为实现运算符优先，可以使用两个操作栈，操作栈st,用于存放操作数及运算结果；操作栈op，用于存放操作符。算法思想：(1).首先将中缀表达式转换成后缀表达式：<1>.从左至右依次扫描中缀表达式的每一个字符，如果是数字字符和“.”，则直接将它们写入后缀表达式中。<2>.如果遇到的是开括号“（”，则将它压入一个操作符栈中，它表明一个新的计算层次的开始，在遇到和它匹配的闭括号时，将栈中元素弹出并放入后缀表达式中，直到栈顶元素为开括号“（”时，将栈顶元素“（”弹出，表明这一层括号内的操作处理完毕。<3>.如果遇到的是操作符，则将该操作符和操作符栈顶元素比较：a)当所遇缀表达式，并弹出该栈顶元素，反复执行直到栈顶元素b)当所遇到的操作符的优先级大于栈顶元素的优先级时，则将它压入栈中。到的操作符的优先级小于或等于栈顶元素的优先级时，则取出栈顶元素放入后的优先级小于当前操作符的优先级；重复上述步骤直到遇到中缀表达式的结束‘’，弹出栈中的所有元素并放入后缀表达式中，算法结束。(2).对后缀表达式求值：将遇到的操作数暂存在一个操作数栈中，凡是遇到操作符，便从栈中弹出两个操作数

执行相应的操作，并将结果存于操作数栈中，直到表达式处理完毕，最后压入栈中的数就是表达式的结果。2.建立试题库文件“shitiku.txt”和成绩库文件“chengji.txt”。试题库文件“shitiku.txt”中存储20道带括号的四则混合运算；成绩库文件“chengji.txt”中存储历史成绩。3.从试题库文件“shitiku.txt”中读出“total”道题：当做的题目数小于“total”时，用随机函数产生每次要做的题号。4.对本次作业进行评分：本次作业共做题“total”道，每道“100/total”分；做对题目数为“r”,本次作业得分为“r*(100/total)”。5.输入“~”符号时，退出程序。4.2源代码#include<stdio.h>#include<stdlib.h>#defineMAXSIZE30intlength[20]={13,15,12,9,11,17,13,15,9,11,11,11,12,10,15,13,18,16,16,9};/*shitiku文件中20个字符串数组的长度*/typedefstruct{floatdata[MAXSIZE];inttop;};floatcompvalue(char*postexp)/*后缀表达式求值*/{struct

{floatdata[MAXSIZE];inttop;}st;floata,b,c,d;intk=0;st.top=-1;{switch(*postexp){case'+':a=st.data[st.top];st.top--;b=st.data[st.top];st.top--;c=b+a;st.top++;st.data[st.top]=c;break;case'-':a=st.data[st.top];st.top--;b=st.data[st.top];st.top--;c=b-a;st.top++;st.data[st.top]=c;break;case'*':

a=st.data[st.top];st.top--;b=st.data[st.top];st.top--;c=b*a;st.top++;st.data[st.top]=c;break;case'/':a=st.data[st.top];st.top--;b=st.data[st.top];st.top--;if(a!=0){c=b/a;st.top++;st.data[st.top]=c;}else{return(0);}break;default:d=0;while(*postexp>='0'&&*postexp<='9'){/*读整数部分*/d=10*d+*postexp-'0';/*整数部分处理*/

postexp++;}if(*postexp=='.')/*读数时遇到小数点*/{postexp++;while(*postexp>='0'&&*postexp<='9')/*读小数部分*/{d=d*10+*postexp-'0';postexp++;k++;}}while(k!=0)/*小数部分处理*/{d=d/10.0;k=k-1;}st.top++;st.data[st.top]=d;break;}postexp++;}returnst.data[st.top];/*操作栈st中最终剩下表达式运算结果*/}voidtrans(char*exp,char*postexp)/*将中缀表达式转换成后缀表达式*/{struct

{chardata[MAXSIZE];inttop;}op;inti=0;op.top=-1;{switch(*exp){case'(':op.top++;op.data[op.top]=*exp;exp++;break;case')':while(op.data[op.top]!='('){postexp[i++]=op.data[op.top];op.top--;}op.top--;exp++;break;case'+':case'-':while(op.top!=-1&&op.data[op.top]!='('){postexp[i++]=op.data[op.top];op.top--;}op.top++;op.data[op.top]=*exp;exp++;break;case'*':case'/':

while(op.data[op.top]=='*'||op.data[op.top]=='/'){postexp[i++]=op.data[op.top];op.top--;}op.top++;op.data[op.top]=*exp;exp++;break;case'':break;default:while(*exp>='0'&&*exp<='9'||*exp=='.'){postexp[i++]=*exp;exp++;}postexp[i++]='#';}}while(op.top!=-1){postexp[i++]=op.data[op.top];op.top--;}}voidmain(){inti;intn;intt;

intformer,mark;charexp[30];/*former：历史成绩mark：本次成绩*//*存储中缀表达式*/floatresult,answer;/*result：从键盘输入的结果answer：程序中函数求得的正确答案*//*total：要做的题的总数r：做对的题目总数*/inttotal,r;charpostexp[MAXSIZE];chars1[20][30];FILE*fp;/*存储后缀表达式*//*存储所有的表达式*/r=0;randomize();/*产生随机种子*/if(fp==NULL){exit(2);}for(i=0;i<20;i++)fgets(s1[i],30,fp);/*将所有20个表达式存入二维数组s1[20][30]中*/fclose(fp);if(total<0||total>=21)/*total小于0或大于21时，退出*/exit(0);t=total;while(t>0){n=random(21);/*产生一个小于21的随机整数*//*将第n题存入exp[]中*/for(i=0;i<length[n];i++){exp[i]=s1[n][i];

}trans(exp,postexp);result=compvalue(postexp);if(answer=='~')/*输入“~”即退出*/exit(0);elseif((result-answer)<=0.01){/*比较计算结果与正确答案*/r++;}elsefor(i=0;i<30;i++)t--;清空用来存放表达式的数组*/}mark=r*100/total;/*赋分*/读取文件中存储的历史分数*/将本次分数存入文件中*/fclose(fp);if(mark<=former)else/*比较历史分数与本次分数并给出评价*/

}4.3．运行结果：１.选择本次要做的题目数：3；每道题为100/3=33分；做对题目，输出“Congratulations!Youareright！”；做错题目，输出“Therightansweris：(正确答案)”；得分为做对题目*33；本次成绩比上一次低或与上一次相同，输出“tryhard”：

2．选择本次