东北大学数据结构算术表达式求值实验报告

《数据结构》课程设计报告书题目: 表达式求值系别：计算机科学与信息系学号：学生姓名：指导教师:完成日期:目录➢1.前言➢2.概要设计2。

1 数据结构设计2.2 算法设计2.3 ADT描述2。

4 功能模块分析➢3。

详细设计3.1 数据存储结构设计3.2主要算法流程图（或算法代码）➢4.软件测试➢5。

总结➢附录1．前言在计算机中，算术表达式由常量、变量、运算符和括号组成。

由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行.因而在程序设计时，借助栈实现。

算法输入：一个算术表达式,由常量、变量、运算符和括号组成（以字符串形式输入）。

为简化，规定操作数只能为正整数，操作符为+、-*、/，用#表示结束。

算法输出：表达式运算结果。

算法要点：设置运算符栈和运算数栈辅助分析算符优先关系。

在读入表达式的字符序列的同时,完成运算符和运算数的识别处理，以及相应运算。

2．概要设计2.1 数据结构设计任何一个表达式都是由操作符,运算符和界限符组成的。

我们分别用顺序栈来寄存表达式的操作数和运算符.栈是限定于紧仅在表尾进行插入或删除操作的线性表。

顺序栈的存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置，base为栈底指针，在顺序栈中，它始终指向栈底，即top=base可作为栈空的标记，每当插入新的栈顶元素时，指针top增1，删除栈顶元素时,指针top减1。

2.2 算法设计为了实现算符优先算法。

可以使用两个工作栈。

一个称为OPTR ，用以寄存运算符，另一个称做OPND ，用以寄存操作数或运算结果。

1。

首先置操作数栈为空栈，表达式起始符”＃"为运算符栈的栈底元素；2.依次读入表达式，若是操作符即进OPND 栈，若是运算符则和OPTR 栈的栈顶运算符比较优先权后作相应的操作，直至整个表达式求值完毕（即OPTR 栈的栈顶元素和当前读入的字符均为"#")。

竭诚为您提供优质文档/双击可除数据结构表达式求值实验报告篇一：数据结构实验二——算术表达式求值实验报告《数据结构与数据库》实验报告实验题目算术表达式求值学院：化学与材料科学学院专业班级：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！二、概要设计拟采用两种类型的展分别对操作数和操作符进行操作。

实验报告课程名：数据结构（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.理解表达式的概念。

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. 表达式求值这个程序，主要利用栈和数组，把运算的先后步骤进行分析并实现简单的运算，以字符列的形式从终端输入语法的正确的、不含变量的整数表达式。

利用已知的算符优先关系，实现对算术四则运算的求值，在求值中运用栈、运算栈、输入字符和主要操作的变化过程。

该程序相当于一个简单的计算机计算程序，只进行简单的加减乘除和带括号的四则运算。

1、基本思想（中缀表达式求值）要把一个表达式翻译成正确求值的一个机器指令序列，或者直接对表达式求值，首先要能够正确解释表达式，要了解算术四则运算的规则即：（1）先乘除后加减；（2）从左到右计算；（3）先括号内，后括号外。

下表定义的运算符之间的关系:b + - * / （） # a+ > > < < < > > _ > > < < < > > * > > > > < > > / > > > > < > > ( < < < < < = ) > > > > > > # < < < < < =为了实现运算符有限算法，在程序中使用了两个工作栈。

分别是：运算符栈OPTR,操作数栈OPND.基本思想：（1）首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素；（2）依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈得栈顶运算符比较优先级后作相应操作。

表达式求值实验报告西南大学数据结构实验报告学院：专业：班级：姓名：学号：实验报告一、实验题目：表达式表达式二、实验目的和建议：目的：（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)。