下载文档原格式
竭诚为您提供优质文档/双击可除数据结构表达式求值实验报告篇一：数据结构实验二——算术表达式求值实验报告《数据结构与数据库》实验报告实验题目算术表达式求值学院：化学与材料科学学院专业班级：09级材料科学与工程系pb0920603姓学邮名：李维谷号：pb09206285箱：指导教师：贾伯琪实验时间：20XX年10月10日一、需要分析问题描述：表达式计算是实现程序设计语言的基本问题之一，它的实现是栈的应用的一个典型例子。
设计一个程序，演示通过将数学表达式字符串转化为后缀表达式，并通过后缀表达式结合栈的应用实现对算术表达式进行四则混合运算。
问题分析：在计算机中，算术表达式由常量、变量、运算符和括号组成。
由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。
因而在程序设计时，借助栈实现。
设置运算符栈（字符型）和运算数栈（浮点型）辅助分析算符优先关系。
在读入表达式的字符序列的同时完成运算符和运算数的识别处理，然后进行运算数的数值转换在进行四则运算。
在运算之后输出正确运算结果，输入表达式后演示在求值中运算数栈内的栈顶数据变化过程，最后得到运算结果。
算法规定：输入形式：一个(:数据结构表达式求值实验报告)算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。
为使实验更完善，允许操作数为实数，操作符为（、）、.（表示小数点）、+、-、*、/、^（表示乘方），用#表示结束。
输出形式：演示表达式运算的中间结果和整个表达式的最终结果，以浮点型输出。
程序功能：对实数内的加减乘除乘方运算能正确的运算出结果，并能正确对错误输入和无定义的运算报错，能连续测试多组数据。
测试数据：正确输入：12*（3.6/3+4^2-1）#输出结果：194.4无定义运算：12*（3.6/（2^2-4）+1）#输出结果：表达式出错，除数为0，无意义错误输入：12+s#输出结果：eRRoR！二、概要设计拟采用两种类型的展分别对操作数和操作符进行操作。
表达式求值（数据结构-栈的应⽤）⼀.问题描述：限制：只含有‘+’，‘-’，‘*’，‘/ ’和圆括号,正整数。
表⽰：字符数组，栈。
中缀表达式：在程序语⾔中，运算符位于两个运算数中间的表达式称为中缀表达式，例如 1+2*3.中缀表达式运算规则：先乘除，后加减，从左到右，先括号内，后括号外，因此中缀表达式不仅要判断运算符的优先级，⽽且还有处理括号。
后缀表达式：运算符在运算数的后⾯，如1+2*3的后缀表达式：1 2 3*，在后缀表达式中已经考虑了运算符的优先级，没有括号，只有运算数和运算符。
后缀表达式的运算：按照运算符的次序进⾏的。
例如123*+，从左到右扫描时，第⼀个运算符为*，先执⾏2*3=6，第⼆个运算符为‘+’，执⾏1+6=7。
⼆ .表达式求值的过程：将算术表达式转换成后缀表达式，然后对后缀表达式求值。
1.将算术表达式转换为后缀表达式。
（1）从左到右⼀次扫描中缀表达式的每⼀个字符，如果是字符串，直接写⼊后缀表达式。
（2）如果遇到的是' ( '，则压⼊操作符栈，遇到‘（’时，将栈中的元素放到后缀表达式中，直达栈顶元素为'('时，将栈顶元素'('删除，不需要⼊栈。
（3）如果遇到的是操作符，则将操作符和操作符栈顶元素⽐较。
：如果a[i]的运算符的优先级⼩于等于栈顶元素的优先级，退栈运算符并放到后缀表达式中，直到a[i]的运算符优先级⼤于栈顶运算符的优先级：否则⼊栈。
（4）重复上述步骤，知道中缀表达式的结束符标记“#”，转换结束。
我的代码：#include<bits/stdc++.h>using namespace std;stack<char>f;//操作符栈stack<double>s;//操作数栈bool flag;int prior(char ch)//运算符的优先级{switch(ch){case'+':case'-':return 1;case'*':case'%':case'/':return 2;default:return 0;//括号}}string trans(string a){while(!f.empty()) f.pop();f.push('#');string ret="";//保存中缀表达式int len=a.size(),i=0;while(i<len){if(a[i]==' '||a[i]=='=')//??{i++;continue;}else if(a[i]=='(')f.push(a[i++]);else if(a[i]==')'){while(f.top()!='('){ret+=f.top();ret+=' ';f.pop();}f.pop();//(出栈i++;}else if(a[i]=='+'||a[i]=='-'||a[i]=='*'||a[i]=='/'||a[i]=='%'){while(prior(f.top())>=prior(a[i]))//如果a[]的运算符的优先级⼩于等于栈顶元素的优先级，退栈运算符并放到后缀表达式中，直到a[i]的运算符优先级⼤于栈顶运算符的优先级ret+=f.top();ret+=' ';f.pop();}f.push(a[i++]);}else{while((a[i]>='0'&&a[i]<='9')||a[i]=='.'){ret+=a[i++];}ret+=' ';}}while(f.top()!='#'){ret+=f.top();ret+=' ';f.pop();}ret+='=';return ret;}double cal(double a,double b,double ch)//计算{if(ch=='+') return a+b;if(ch=='-') return a-b;if(ch=='*') return a*b;if(ch=='%') return ((int)a%(int)b);if(ch=='/'){if(b!=0)return a/b;flag=true;return 0;}}double solve(string a)//后缀表达式计算{string t=trans(a);while(!s.empty()) s.pop();flag=false;int len=t.length(),i=0;while(i<len){if(t[i]==' '||t[i]=='='){i++;continue;}else if(t[i]=='+'||t[i]=='-'||t[i]=='*'||t[i]=='/'||t[i]=='%') {double num1,num2;num1=s.top();s.pop();num2=s.top();s.pop();s.push(cal(num1,num2,t[i]));i++;}else{double x=0;while(t[i]>='0'&&t[i]<='9'){x=x*10+t[i]-'0';i++;}if(t[i]=='.'){double k=10.0,y=0;i++;while(t[i]>='0'&&t[i]<='9'){y+=((t[i]-'0')/k);i++;k*=10;;}x+=y;}s.push(x);}}return s.top();}int main(){int num;scanf("%d",&num);while(num--){cin>>a;// cout<<e.trans(a)<<endl;//将中缀表达式装换为后缀表达式 cout<<solve(a)<<endl;}return 0;}。
实验报告课程名：数据结构（C语言版）实验名：表达式求值姓名：班级：学号：时间：2014.10.25一实验目的与要求1. 了解栈的应用2. 利用栈进行算术表达式求值二实验内容1.以字符串的形式给出一个算术表达式, 计算出该算术表达式的值。
2.表达式中可能出现”+”, ”−”, ”∗”, ”/”, ”(”, ”)”。
三实验结果与分析分析：r:读入字符t:栈顶字符r( ) # 低优先运算符高优先运算符( 入栈出栈错误入栈入栈) 错误错误错误错误错误t # 入栈错误结束入栈入栈低优先运算符入栈出栈+运算出栈+计算出栈+计算入栈高优先运算符入栈出栈+运算出栈+计算出栈+计算出栈+计算1, 入栈2, 错误3, 出栈4, 出栈+计算5, 结束( ) # 低优先运算符高优先运算符( 1 3 2 1 1) 2 2 2 2 2# 1 2 5 1 1低优先运算符 1 4 4 4 1高优先运算符 1 4 4 4 4此实验可用两个栈和数组来实现，一个操作栈，一个数字栈，两个栈的字符进行优先权比较可得到5种结果。
首先置操作栈为空栈，表达式起始符“#”作为数字栈的栈底元素，依次读入表达式的每个字符，若是操作字符进操作栈，若是数字进数字栈，操作栈和数字栈的栈顶元素比较优先权后进行相应操作，直至结束，最后输出值即可。
实验程序：#include<stdio.h>#include<stdlib.h>#include<string.h>int change(char c)//字符转换{int j=-1;switch(c){case '(':j=0;break;case ')':j=1;break;case '#':j=2;break;case '+':j=3;break;case '-':j=3;break;case '*':j=4;break;case '/':j=4;break;}return(j);}int compu(int x,int y,char c)//数字计算转换{int j=-1;switch(c){case '+':j=x+y;break;case '-':j=x-y;break;case '*':j=x*y;break;case '/':j=x/y;break;}return(j);}void get(char a[],int num_op,int method[5][5]){int a_length=strlen(a)+1;//表达式的长度int p=0,num_p=0,op_p=0;int *num_s=(int *)malloc((a_length)*sizeof(int));// char *op_s=(char *)malloc((a_length)*sizeof(int));// op_s[op_p]='#';op_p++;//进字符栈int k=-1;//输出结果判断int ox,oy;while(1){char c=a[p];//将表达式中的字符一个一个赋值给cif(c>='0'&&c<='9')//判断是不是数字{num_s[num_p]=c-48;//将Ascll码转换成对应数字num_p++;//进数字栈p++;//代表表达式的位置开始为0指向第一位}else{int t=method[change(op_s[op_p-1])][change(c)];//将5种操作的一种传给tswitch(t){case 1:op_s[op_p]=c;op_p++;p++;break;case 2:k=0;break;case 3:op_p--;p++;break;case 4:ox=num_s[num_p-2];oy=num_s[num_p-1];num_p=num_p-2;num_s[num_p]=compu(ox,oy,op_s[op_p-1]);//将计算的值存入num_s[]num_p++;//入数字栈op_p--;break;case 5:k=1;break;}}if(k>=0)//跳出循环{break;}}switch(k)//0错误，1输出结果{case 0:printf("表达式错误！");break;case 1:printf("%s=%d\n",a,num_s[num_p-1]);break;}}int main(int argc,char *argv[]){ char a[20];puts("请输入个位数的表达式:");gets(a);int num_op=5;//表示操作的种数int method[5][5]={{1,3,2,1,1},{2,2,2,2,2},{1,2,5,1,1},{1,4,4,4,1},{1,4,4,4,4}};//1表示入栈，2表示错误，//3表示出栈，4表示出栈+计算，//5表示结束get(a,num_op,method);return 0;}图1.表达式求值运行结果。
(一) 需求分析1、输入的形式和输入值的范围：根据题目要求与提示，先选择你要使用的表达式形式（中缀用1，后缀用0），在输入一个中缀表达式，输入数的范围为int型，此时，程序将计算出表达式的结果。
2、输出的形式：当按照程序要求选择了1或0之后，再输入表达式；如果选择的是1，则程序将自动运算出表达式结果；如果之前选择的是0，则程序将现将中缀表达式转化为后缀表达式并计算出结果。
3、程序所能达到的功能：本程序能计算出含+、-、*、/、（、）等运算符的简单运算。
4、测试数据：输入一个表达式，如果你之前选择的是“中缀表达式”，那么输入5*(4-2)#,那么输出结果是10；如果之前选择的是“后缀表达式”，那么输入5*（4-2）#，那么他将先转换成后缀表达式5 4 2 - * #，再输出结果10。
如果输入表达式没有结束标示符#，如5*（4-2），那将不会输出任何结果，或出现错误结果。
(二) 概要设计为了实现上述操作，应以栈为存储结构。
1．基本操作：（1）. int GetTop(SqStack *s)初始条件：栈存在；操作结果：若栈为空，则返回s的栈顶元素；否则返回ERROR。
（2）.void Push(SqStack *s,int e)初始条件：栈存在；操作结果：插入e为新的栈顶元素。
（3）.int Pop(SqStack *s)初始条件：栈存在；操作结果：若栈不空，则删除之，并返回其值；否则返回REEOR。
（4）.void InitStack(SqStack *s)初始条件：栈存在；操作结果：置栈为空。
（5）.int Empty(SqStack *s)初始条件：栈存在；操作结果：判定s是否为空栈。
（6）.int Operate(int a,char theta, int b)初始条件：操作数a和b存在，且theta是+、-、*、/四则运算；操作结果：返回a与b间theta运算的结果。
（7）.int In(char s,char* TestOp)初始条件：s为待判断字符，TestOp为已知的算符集合；操作结果：s为算符集合中的元素则返回1，否则返回0.（8）.int ReturnOpOrd(char op,char* TestOp)初始条件：op为待确定运算符，TestOp为已知的算符集合；操作结果：确定运算符类型。
数据结构表达式求值实验报告数据结构表达式求值实验报告第一章引言数据结构是计算机科学中重要的基础知识之一，它研究的是数据在计算机中的存储和组织方式，以及基于这些方式进行操作和运算的算法。
表达式求值是数据结构中一个重要的应用场景，它涉及到从一个给定的表达式中计算出最终结果的过程。
本实验旨在通过实际编程实践，掌握表达式求值的算法和数据结构的应用。
第二章实验目的1.理解表达式的概念。
2.熟悉常见表达式求值算法。
3.掌握栈的基本操作。
4.实现一个表达式求值的程序。
第三章实验内容1.表达式的定义：________表达式是由运算符和运算数组成的字符串，它代表了一种计算规则。
2.表达式的分类：________根据运算符的位置和计算顺序，表达式可以分为前缀表达式、中缀表达式和后缀表达式。
3.表达式求值的算法：________1. 前缀表达式求值算法：________1) 创建一个空栈。
2) 从右往左遍历前缀表达式。
3) 如果当前字符是运算符，则将栈顶的两个元素出栈，进行相应的运算，将结果入栈。
4) 如果当前字符是运算数，则将其转化为整数形式，并入栈。
5) 最终栈内只剩下一个元素，即为表达式的求值结果。
2. 中缀表达式求值算法：________1) 将中缀表达式转化为后缀表达式。
2) 创建一个空栈。
3) 从左往右遍历后缀表达式。
4) 如果当前字符是运算符，则将栈顶的两个元素出栈，进行相应的运算，将结果入栈。
5) 如果当前字符是运算数，则将其转化为整数形式，并入栈。
6) 最终栈内只剩下一个元素，即为表达式的求值结果。
3. 后缀表达式求值算法：________1) 创建一个空栈。
2) 从左往右遍历后缀表达式。
3) 如果当前字符是运算符，则将栈顶的两个元素出栈，进行相应的运算，将结果入栈。
4) 如果当前字符是运算数，则将其转化为整数形式，并入栈。
5) 最终栈内只剩下一个元素，即为表达式的求值结果。
4.实验代码实现：________根据算法描述，使用编程语言实现一个表达式求值的程序。
表达式求值实验报告西南大学数据结构实验报告学院：专业：班级：姓名：学号：实验报告一、实验题目：表达式表达式二、实验目的和建议：目的：（1）通过该算法的设计思想，熟识栈的特点和应用领域方法；（2）通过对波函数优先法对算术表达式表达式的算法继续执行过程的模拟，认知在继续执行适当栈的操作方式时的变化过程。
（3）通过程序设计，进一步熟识栈的基本运算函数；（4）通过自己动手同时实现算法，强化从伪码算法至c语言程序的同时实现能力。
建议：（1）采用栈的顺序存储则表示方式；（2）采用波函数优先法；（3）用c语言同时实现；（4）从键盘输入一个符合要求的算术表达式，输入恰当的结果。
三、实验过程：#include#include#include#include#include#include#include#include#include#inclu de#include//函数结果状态代码#definetrue1#definefalse0#defineok1#defineerror0#defineinfeasible-1typedefintstatus;//status就是函数的类型,其值就是函数结果状态代码，如ok等typedefintelemtype;constintstack_init_size=100;constintstackincrement=10;typed efstruct{elemtype*base;elemtype*top;intstacksize;}stack;statusinitstack(stack&s){//构造一个空栈ss.base=(elemtype*)malloc(stack_init_size*sizeof(elemtype));if(!s.base)exit(er ror);s.top=s.base;s.stacksize=stack_init_size;returnok;}statuspush(stack&s,ele mtypee){//插入元素e为新的栈顶元素if(s.top-s.base>=s.stacksize){s.base=(elemtype*)realloc(s.base,(s.stacksize+stackincrem ent)*sizeof(elemtype));if(!s.base)exit(overflow);s.top=s.base+s.stacksize;s.st acksize+=stackincrement;}*s.top++=e;returnok;}statuspop(stack&s,elemtype&e){//若栈不空，则删除，用e返回其值，并返回ok；否则返回errorif(s.top==s.base)returnerror;e=*--s.top;returnok;}statusgettop(stack&s){//若栈不空，用e返回s的栈顶元素，并返回ok；否则返回errorif(s.top==s.base)returnerror;return*(s.top-1);}operate.h:#include\statusin(charc){//辨别c与否为运算符if(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')'||c=='#')returnok;elsereturnerror;}statusoper ate(inta,charc,intb){//二元运算switch(c){case'+':returna+b;break;case'-':returna-b;break;case'*':returna*b;break;case'/':if(b==0){printf(\（提示信息：存有除数为零错误）\\n\);returnerror;}//除数无法为零elsereturna/b;break;}}charprecede(chara,charb){//波函数间优先关系switch(a){case'+':switch(b){case'+':return'>';break;case'-':return'>';break;case'*':return'';break;case'#':return'>';break;}break;case'-':switch(b){case'+':return'>';break;case'-':return'>';break;case'*':return'';break;case'#':return'>';break;}break;case'*':switch(b){case'+':return'>';break;case'-':return'>';break;case'*':return'>';break;case'/':return'>';break;case'(':return'';break;case'#':return'>';break;}break;case'/':switch(b){case'+':return'>'; break;case'-':return'>';break;case'*':return'>';break;case'/':return'>';break;case'(':return'';break;case'#':return'>';break;}break;case'(':switch(b){case'+':return'';b reak;case'-':return'>';break;case'*':return'>';break;case'/':return'>';break;case')':return'>';break;case'#':return'>';break;}break;case'#':switch(b)。
数据结构表达式求值实验报告数据结构表达式求值实验报告1. 引言表达式求值是计算机科学中的一个重要问题，也是数据结构的一个经典应用。
通过将中缀表达式转换为后缀表达式，并利用栈这一数据结构，可以实现对表达式的有效求值。
本实验旨在探究数据结构在表达式求值中的应用。
2. 实验内容本实验中，我们将实现一个表达式求值的程序。
具体步骤如下：1. 将中缀表达式转换为后缀表达式。
2. 使用栈来求解后缀表达式。
3. 算法原理3.1 中缀表达式转后缀表达式中缀表达式是我们常见的数学表达式，如 2 + 3 4。
而后缀表达式是将操作符放在操作数后面的表达式，上述中缀表达式的后缀表达式为 2 3 4 +。
中缀表达式到后缀表达式的转换可以通过以下步骤完成：1. 初始化一个栈和一个输出队列。
2. 从左到右遍历中缀表达式的每个字符。
3. 如果当前字符是数字，将其加入输出队列。
4. 如果当前字符是左括号，将其压入栈。
5. 如果当前字符是右括号，将栈中的操作符依次弹出并加入输出队列，直到遇到左括号为止。
6. 如果当前字符是操作符，将其与栈顶操作符进行比较：1. 如果栈为空，或者栈顶操作符为左括号，直接将当前操作符压入栈。
2. 否则，比较当前操作符与栈顶操作符的优先级，如果当前操作符的优先级较低，将栈顶操作符弹出并加入输出队列，然后将当前操作符压入栈。
3. 如果当前操作符的优先级大于等于栈顶操作符的优先级，则直接将当前操作符压入栈。
7. 遍历完中缀表达式后，将栈中的操作符依次弹出并加入输出队列。
3.2 后缀表达式求值通过将中缀表达式转换为后缀表达式，我们可以利用栈来对后缀表达式进行求值。
具体求值操作如下：1. 初始化一个栈。
2. 从左到右遍历后缀表达式的每个字符。
3. 如果当前字符是数字，将其加入栈。
4. 如果当前字符是操作符，从栈中弹出两个数字，进行相应的运算，然后将结果加入栈。
5. 遍历完后缀表达式后，栈中的元素即为最终的结果。
4. 实验结果我们用中缀表达式\。
实验报告课程名称数据结构实验项目实验二--栈和队列实验系别___ _计算机学院 _ ______专业___ _计算机科学与技术___班级/学号__学生姓名 ____________实验日期成绩_______________________指导教师实验题目：实验二-----栈和队列实验一、实验目的1)掌握栈的顺序存储结构及队列的链式存储结构；2)验证栈的顺序存储结构的操作的实现；3)验证队列的链式存储结构的操作的实现；4)理解算法与程序的关系，能够将算法转换为对应程序。
二、实验内容1)建立一个顺序存储的空栈，并以此分别实现入栈、出栈、取栈顶元素；2)建立一个链式结构的空队列，并以此分别实现入队、出队、取队头等基本操作；3)尝试利用栈和队列的算法解决一些实际的应用问题。
设计与编码1)实验题目主要需求说明2)设计型题目：表达式求值（要求利用栈结构和运算符优先约定表，输入一个表达式，并计算求值）3)结合题目，说明利用栈或队列解决问题的基本算法描述4)程序源码#include<iostream>using namespace std;const int InitSize=100;const int IncreastSize=10;template<class datatype>class SqStack {private:datatype *base;datatype *top;int stacksize;public:SqStack();void DestroyStack();void ClearStack();int StackLength();bool IsEmpty();bool GetTop(datatype &e);bool Pop(datatype &e);bool Push(datatype e);};template<class datatype>SqStack<datatype>::SqStack(){base=new datatype[InitSize];if(!base)exit(1);top=base;stacksize=InitSize;}template<class datatype>void SqStack<datatype>::DestroyStack() {delete[] base;base=top=NULL;stacksize=0;}template<class datatype>void SqStack<datatype>::ClearStack() {top=base;}template<class datatype>int SqStack<datatype>::StackLength() {return top-base;}template<class datatype>bool SqStack<datatype>::IsEmpty() {if(top==base)return fasle;else return true;}template<class datatype>bool SqStack<datatype>::GetTop(datatype &e){if(top==base)return false;e=*(top-1);return true;}template<class datatype>bool SqStack<datatype>::Pop(datatype &e){if(top==base)return false;e=*(top-1);top--;return true;}template<class datatype>bool SqStack<datatype>::Push(datatype e){if(top-base>=stacksize){base=(datatype *)realloc( base , (stacksize+IncreastSize)*sizeof(int) ); if(!base)exit(1);top=base+stacksize;stacksize+=IncreastSize;}*(top)=e;top++;return true;}int com(char m,char t){if(t=='(') return -1;else if(t==')'){if(m=='+'||m=='-'||m=='*'||m=='/') return 1; else if(m=='(') return 0;else return -2;}else if(t=='*'||t=='/'){if(m=='+'||m=='-'||m=='#'||m=='(') return -1; else return 1;}else if(t=='+'||t=='-'){if(m=='#'||m=='(') return -1;else return 1;}else{if(m=='#')return 0;else if(m=='+'||m=='-'||m=='*'||m=='/') return 1; else return -2;}}void main(){SqStack <char> op;SqStack <double> re;char t,m;double result,flag=1;op.Push('#');t=getchar();while(true){if(t>='0'&&t<='9'){double s=0;s=s*10+t-'0';t=getchar();while(t>='0'&&t<='9' ){s=s*10+t-'0';t=getchar();}re.Push(s);}else if(t=='+'||t=='-'||t=='*'||t=='/'||t=='('||t==')'||t=='\n') { op.GetTop(m);while(com(m,t)==1 ){double x1,x2;op.Pop(m);if(re.Pop(x2)&&re.Pop(x1)){if(m=='+') re.Push(x1+x2);else if(m=='-') re.Push(x1-x2);else if(m=='*') re.Push(x1*x2);else if(m=='/') {if(x2!=0)re.Push(x1/x2); else flag=0;} }else flag=0;op.GetTop(m);}if(com(m,t)==-1)op.Push(t);else if(com(m,t)==0)op.Pop(m);else flag=0;if(!op.GetTop(m)) break;t=getchar();}else t=getchar();}if(re.GetTop(result)&&flag)cout<<result<<endl;else cout<<"Input error!\n";}5)运行结果三、总结与心得。
