数据结构实验报告题目：编制一个表达式求值的程序。
一．需求分析1.本演示程序中，利用堆栈存储结构存储读入的运算符，输入的限定范围是数字（0—9），以及+*/()。
输入字符串限定长度为20，可以根据需要进行改变。
如果遇到不是以上范围或者连续输入两个运算符，如：++，则会提示输入错误，请重新输入。
输出的结果是转换后的后序表达式，以及float型数字，不会含有非法字符。
2.演示程序采用的是文件输入，只需要在源代码中输入要输入的文件的地址，然后就可以在文本文件中进行输入，运行过程中会自动读取，输出文本输入的表达式，及运算结果。
3.程序执行的命令包括：1）构造字符优先级比较表，比较优先关系2）文件输入3）构造堆栈，运算符入栈4）堆栈输出，变为后序表达式，并计算5）输出结果，结束4.测试数据文件地址：C:\\Users\\lenovo\\Desktop\\4.txt1) 输入：(35+20/2)*2-4/2+12正确输出结果是：100.00002)输入：(35+20/2)*2-/2+12结果是:error input3) 输入：a+ar/3=135结果是:error input二．概要设计为实现以上程序功能，需运用堆栈用于存储运算符，因此需要定义抽象数据类型。
1.堆栈的抽象数据类型定义为:ADT stack｛数据对象:D={ai|ai∈正整数，i=0，1，2，3，…n,及｛+-*/()｝}数据关系：R1={<ai-1,a1>|ai-1,ai∈D}基本操作：Init stack（&s）操作结果：构造一个空的堆栈sPush stack（&s, e）初始条件：存在堆栈s操作结果:元素e压入堆栈s，top+1Pop （&s，e）初始条件：栈s已经存在且非空操作结果：删除栈顶元素e，输出其值，top-12.程序包含三个模块：1）运算符优先关系模块2）主程序模块;Int main(void){初始化；Do｛接受命令；处理命令；｝while（“命令”=”退出”）；｝3）堆栈模块三．详细设计1.程序源代码解释为：float Result(int c,float r[],int top){ //定义输出结果int j;float temp;switch(c){ //以下是四种基本运算的计算定义，运算完成后直接将top-1值赋予topcase 42:r[top-1]=r[top-1]*r[top];top=top-1;break; //乘法case 43:r[top-1]=r[top-1]+r[top];top=top-1;break;///加法case 45:r[top-1]=r[top-1]-r[top];top=top-1;break;//减法case 47:r[top-1]=r[top-1]/r[top];top=top-1;break;// 除法case 94:for(j=1,temp=r[top-1];j<r[top];j++) //平方或者几次方的运算temp=r[top-1]*temp; //循环相乘r[top-1]=temp;top=top-1;break;}return(r[top]);}if(temp1!=1){while(top>=1){ //栈不空的时候，栈中元素赋给houzhi，并计数biaozhi[b++]=i;houzhi[i]=duizhan[top-1];top=top-1;i=i+1;}max=i; //从0到i循环输出后序表达式for(i=0,b=0;i<max;i++){if(i!=biaozhi[b])printf("%d ",houzhi[i]) ; //输出后序表达式中的数字else {printf("%c ",houzhi[i]); //输出后序表达式中的运算符b=b+1;}}top=-1;for(i=0,b=0;i<max;i++){ //从0到maxif(i!=biaozhi[b]){top=top+1;result[top]=houzhi[i]; //将后值赋予result，调用result函数，进行Result运算}else {Result(houzhi[i],result,top); //运算结束，输出栈顶值，既是运算结果top--;b=b+1;}}printf("\n\nThe result is %f ",Result(houzhi[i],result,top)); //输出并打印结果}}getch();return 0;///返回0}2.程序的模块调用：主程序↓文件打开读入字符↓输入字符有效及优先级的判断↓运算模块↓输出结果四.调试分析1.本次作业的核心就是利用堆栈将中序表达式改成后序表达式，然后进行表达式的求值。
算术表达式的求解-数据结构课程设计报告课程设计报告题目：算术表达式求值一、需求分析 1、设计要求：给定一个算术表达式，通过程序求出最后的结果 1>、从键盘输入要求解的算术表达式； 2>、采用栈结构进行算术表达式的求解过程； 3>、能够判断算术表达式正确与否；4>、对于错误表达式给出提示；5>、对于正确的表达式给出最后的结果； 2、设计构想：为了实现算符优先算法使用两个工作栈，一个称作OPTR，以寄存运算符；另一个称作OPND，用以寄存操作数或运算结果。
在操作数和操作符入栈前，通过一个函数来判别，输入的是操作数还是操作符，操作数入OPND，操作符入OPTR。
在输入表达式的最后输入‘#’，设定‘#’的优先级最低，代表表达式输入结束。
在表达式输入过程中，遇操作数则直接入栈，遇到运算符则与栈顶运算符比较优先级,若当前运算符优先级高，则当前运算符入栈,扫描下一符号;否则栈顶运算符出栈,两操作数出栈,进行运算,所得结果入数栈,重新比较当前运算符与新栈顶运算符。
如此重复直到栈顶运算符与当前符号均为‘#’，运算结束。
二、概要设计1、本程序包含的模块：栈模块——实现栈抽象数据类型运算模块——实现数据表达式的运算主程序模块算术运算式的求解栈模块主函数模块main 运算模块定义栈结构初始化栈出栈入栈取栈顶元素判断输入字符类型判断符号优先级基础运算函数运算函数三、详细设计栈模块1、定义栈结构 struct Sqstack{elemtype *top;//栈顶元素 elemtype *base; //栈底元素 int stacksize;//栈的大小 };2、栈的基本操作①初始化栈status initstack(struct Sqstack &s) {=(elemtype *)malloc(stack_size*sizeof(elemtype)); if(!) return OVERFLOW; =;=stack_size; return OK; } ②入栈status push(struct Sqstack &s,elemtype e) {if(>=) {=(elemtype*)realloc(,(+stack_increasement)*sizeof(elemtype));if(! ) return OVERFLOW; =+; +=stack_increasement; } * ++=e; return OK; } ③出栈elemtype pop(struct Sqstack &s) {elemtype e; if(= =) return ERROR; e=*--;return e; }④取栈顶元素elemtype gettop(struct Sqstack &s) {elemtype e; if(==) return ERROR; e=* ; return e; } 运算模块1、判断输入字符c是否为操作符：若是，则返回1；否则，返回0 int In(int c) {char p[10]=\ int i=0;while(p[i]!='\\0') {if(p[i]==c) return 1;i++; } return 0; }2、判断运算符的优先级char precede(char top,char c)//该函数为判断当前运算符与前一个运算符的优先级，前一个运算符高于或等于当前运算符的优先级则返回‘>’，前一个运算符小于当前运算符的优先级则返‘'; break; case '+': case '-':if(top=='#'||top=='(')result=''; break; case '*': case '/':if(top=='*'||top=='/'||top=='^') result='>'; elseresult=''; elseresult=''; break;case '(': result='': theta=pop(optr); b=pop(opnd); a=pop(opnd); push(opnd,operate(a,theta,b)); break;// 若当前操作符的优先级低于操作符栈的栈顶元素，则将操作符栈栈顶元素出栈，并将操作数栈的栈顶两个元素出栈，计算两个元素间以操作符栈栈顶元素为运算符的数学运算}//switch }//if}//whilereturn pop(opnd); }主程序模块1、main函数void main(int argc,char *argv) {struct Sqstack opnd; //操作数栈 struct Sqstack optr;//操作符栈initstack(opdn); initstack(optr); elemtype result;printf(\ printf(\算术运算式的求解\printf(\ printf(\请输入算术运算表达式(以'#'结尾):\\n\ printf(\result=evaluate(opnd,optr);printf(\printf(\运算的结果是 :\\n \\n%d\\n\printf(\}四、调试分析 1、测试结果1> 测试数据：3+7*2-1# 测试结果：2> 测试数据：(3+7)*2-1# 测试结果：3> 测试数据： 1/0# 测试结果：2、程序时间复杂度为O；3、设计中出现的问题：在开始的设计中没有注意除数不能为0 ，后来加入if(b==0) {printf(\分母为0,the result is error\\n\ result=0; } elseresult=a/b;break;来判断除数是否为0 4、算法改进：1>输入的操作数和操作码于是字符串类型的，在原设计中实现的操作都是对个位数实现的，实用性不大，故在后来的设计中，通过一个标志flag实现了标志操作数的连续输入的判别，继而实现了多位数的表达式运算2>开始只实现了加、减、乘、除及带小括号的数学运算，考虑到实用性，在后来的设计中引入pow函数，实现了乘方的运算，调整结果如下：3>最初设计的运行界面过于单调，不够友好，改进时加入一些*调整调整结果如下：五、课程设计总结本学期是我第一次接触课程设计，发现了很多学习上的问题，也有很多收获。
算术表达式求值实验报告前言算术表达式求值是计算机科学中比较基础的内容，同时也是很实用的技能，因为有时候我们需要用程序来计算一些复杂的数学运算。
在本次实验中，我们将对算术表达式的求值进行深入研究，并实际编写程序来实现这一功能。
实验原理算术表达式通常由数字、运算符和括号组成，我们需要将其转换为计算机能够直接执行的形式。
常见的算术表达式求值方法有两种：1.中缀表达式求值中缀表达式就是我们平时所熟悉的数学表达式，如2+3*4-5/2。
中缀表达式求值需要遵循一定的运算符优先级和括号的影响，可以通过栈来实现。
首先，我们需要将中缀表达式转换为后缀表达式，即将运算符放在数字后面。
具体的转换方法可以使用栈来实现。
遍历中缀表达式，遇到数字就直接输出，遇到运算符就将其与栈顶运算符进行比较，如果优先级高于栈顶运算符，则将其入栈，否则将栈顶运算符弹出并输出，直到遇到优先级小于等于栈顶运算符或者栈顶为空时，将运算符入栈。
最后将栈中的运算符依次弹出并输出即可。
转换为后缀表达式之后，我们可以通过再次遍历后缀表达式来求值。
遇到数字将其入栈，遇到运算符则弹出栈顶两个数字进行运算，并将结果入栈。
遍历完毕后，栈中剩下的数字就是最终结果。
2.前缀表达式求值前缀表达式就是将运算符放在数字前面的表达式，如：- + * 3 4 5 6。
前缀表达式求值与后缀表达式求值类似，不同之处在于需要从右至左遍历表达式，并将运算符与栈顶数字进行操作。
实验步骤在本次实验中，我们将通过 Python 语言来实现算术表达式求值功能。
具体步骤如下：1. 输入待求值的算术表达式。
2. 对算术表达式进行转换，得到后缀表达式或前缀表达式。
3. 遍历后缀表达式或前缀表达式，求出最终结果。
4. 输出结果。
实验结果我们在 Python 中编写了求解算术表达式的程序，以下是一些样例输入和输出：1. 输入：2+3*4 输出：142. 输入：(2+3)*4 输出：203. 输入：-+*3456 输出：-9通过多组测试，我们可以发现程序能够正确地求解各种算术表达式，包括包含括号和负数的表达式。
