当前位置：文档之家 › 表达式求值实验报告

表达式求值实验报告

  • 格式：doc
  • 大小：261.50 KB
  • 文档页数：23

淮 海 工 学 院 计算机工程学院 课程设计报告

设计名称： 数据结构课程设计 选题名称： 表达式求值 姓 名： 学 号： 专业班级： 系 （院）： 计算机工程学院 设计时间： 设计地点： 软件工程实验室、教室

指导教师评语：

签名： 成绩： 年 月 日 1．课程设计目的 1、训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。 2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 4.训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。

2．课程设计任务与要求： 任务 根据教材《数据结构-C语言描述》（耿国华主编）和参考书《数据结构题集（C语言版）》（严蔚敏、吴伟民主编）选择课程设计题目，要求通过设计，在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。 设计题目从任务书所列选题表中选取，每班每题不得超过2人。 学生自选课题 学生原则上可以结合个人爱好自选课题，要求课题有一定的深度与难度，有一定的算法复杂性，能够巩固数据结构课程所学的知识。学生自选课题需在18周前报课程设计指导教师批准方可生效。 要求： 1、在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。前期准备工作完备与否直接影响到后序上机调试工作的效率。在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率。 2、.设计的题目要求达到一定工作量（300行以上代码），并具有一定的深度和难度。 3、程序设计语言推荐使用C/C++，程序书写规范，源程序需加必要的注释; 4、每位同学需提交可独立运行的程序； 5 、每位同学需独立提交设计报告书（每人一份），要求编排格式统一、规范、内容充实，不少于10页（代码不算）； 6、课程设计实践作为培养学生动手能力的一种手段，单独考核。 3．课程设计说明书 一 需求分析 [问题描述] 一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。 [基本要求] （1） 从键盘读入一个合法的算术表达式，输出正确的结果。 （2） 显示输入序列和栈的变化过程。 二 概要设计 1、设定“操作数”的栈的抽象数据类型定义： ADT SqStack_f{

数据对象：D={ia},NiRai

数据关系：R1={<1,iiaa>|1ia,Dai,i=2,…，n} 约定na端为栈顶，ia端为栈底。 基本操作： InitStack_f(&S) 操作结果：构造一个空栈S。 GetTop_f(&S,&e) 初始条件：栈S已存在。 操作结果：用e返回S的栈顶元素。 Push_f(&S，ch) 初始条件：栈S已存在。 操作结果：插入元素ch为新的栈顶元素。 Pop_f(&S,&e) 初始条件：栈S已存在。 操作结果：删除S的栈顶元素，并以e返回其值。 }ADT SqStack_f 2、设定“操作符”的栈的抽象数据类型定义： ADT SqStack_c{

数据对象：D={ia},'^'/'''*'''''Niai

数据关系：R1={<1,iiaa>|1ia,Dai,i=2,…，n} 约定na端为栈顶，ia端为栈底。 基本操作： InitStack_c(&S) 操作结果：构造一个空栈S。 GetTop_c(&S,&e) 初始条件：栈S已存在。 操作结果：用e返回S的栈顶元素。 Push_c(&S，ch) 初始条件：栈S已存在。 操作结果：插入元素ch为新的栈顶元素。 Pop_c(&S,&e) 初始条件：栈S已存在。 操作结果：删除S的栈顶元素，并以e返回其值。 }ADT SqStack_c 3、本程序包含六个模块 1）主程序模块 void main( ) { 初始化； while(命令==“继续”) { 接受数据； 处理数据； 接受命令； ｝ ｝ 2）栈模块——实现栈抽象数据类型 3）判断运算符优先级模块——判断运算符的优先级别 4）后缀表达式转换模块——将中缀表达式转换为后缀表达式，方便操作 5）无括号表示式求值运算模块——根据后缀表达式求值，并输出中间和最终结果 6）运算结果输出模块——以正确形式输出表达式的值

三 详细设计 1、主程序中需要的全程量 #define TTACK_INIT_SIZE 100 //初始分配最大空间量 #define STACKINCREMENT 10 //（默认）增补空间量 2、结点类型、指针类型 typedef struct{ float *base; //存储实型数据元素的一位数组 float *top; //栈顶指针 int stacksize; //栈数组容量 }SqStack_f; //有序存储实型的顺序表类型 typedef struct{ char *base; //存储字符数据元素的一位数组 char *top; //栈顶指针 int stacksize; //栈数组容量 }SqStack_c; //有序存储字符型的顺序表类型 void InitStack_f(SqStack_f *s) void InitStack_f(SqStack_f *s) //构造一个存储实型（字符型）的空栈，预设空间为100，分配失败就退出 void GetTop_f(SqStack_f *s,float *e) void GetTop_c(SqStack_c *s,char *e) //若栈s不空，则以e带值返栈顶元素，否则显示错误“ERROR”,并退出程序 void Push_f(SqStack_f *s,float e) void Push_c(SqStack_c *s,char e) //在s的栈顶插入新的栈顶元素e，若栈的当前空间已满，则追加存储空间 void Pop_f(SqStack_f *s,float *e) void Pop_c(SqStack_c *s,char *e) //若栈s不空，则删除栈s的栈顶元素，用e带值返回，否则退出程序

其中部分操作的伪码算法（由于比较类似，以浮点型的栈为例） void InitStack_f(SqStack_f *s) {//构造一个存储实型的空栈，预设空间为100，分配失败就退出 s->base=(float *)malloc(TTACK_INIT_SIZE*sizeof(float)); if(!s->base) exit(1); s->top=s->base; s->stacksize=TTACK_INIT_SIZE; } void GetTop_f(SqStack_f *s,float *e) {//若栈s不空，则以e带值返栈顶元素，否则显示错误“ERROR”,并退出程序 if(s->top==s->base) { printf("ERROR!\n"); exit(1); } *e=*(s->top-1); } void Push_f(SqStack_f *s,float e) {//在s的栈顶插入新的栈顶元素e，若栈的当前空间已满，则追加存储空间 if(s->top-s->base>=s->stacksize) { s->base=(float *)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(float)); if(!s->base) { printf("OVERFLOW!\n"); exit(1); } s->top=s->base+s->stacksize; s->stacksize+=STACKINCREMENT; } *s->top++=e; } void Pop_f(SqStack_f *s,float *e) {//若栈s不空，则删除栈s的栈顶元素，用e带值返回，否则退出程序 if(s->top==s->base) exit(1); *e=*--s->top; } 3、判断运算符优先级的算法：

算符间的优先关系如下：

+ - * / ( ) # + >= < < < < > > - > >= < < < > > * > > >= > < > > / > > > >= < > > ( < < < < < = ) > > > > > > # < < < < < =

伪码算法： int precede(char Top_char,char s1_char) {//栈顶的运算符赋给Top_char，新读入的运算符赋给s1_char。判断它们的优先级 //若栈顶运算符优先级高，则返回1，否则返回0 int i,pre[2]; char op[2]; op[0]=Top_char; //栈顶的运算符赋给op[0] op[1]=s1_char; //新读入的运算符赋给op[1] for(i=0;i<2;i++) switch(op[i]) { case'(':case')':pre[i]=0;break; //将括号的优先级设为0 case'+':case'-':pre[i]=1;break; //将+ - 运算符的优先级设为1 case'*':case'/':pre[i]=2;break; //将* / 运算符的优先级设为2 case'^':pre[i]=3;break; //将^ 运算符的优先级设为3 } if(pre[0]>=pre[1]) //栈顶元素优先级高返回1 return 1; else return 0; //否则返回0 } 4、中缀表达式转换为后缀表达式的算法： 算法过程描述： 1) 首先将左括号“(”压进栈，作为栈底元素； 2) 从左而右对算数表达式进行扫描，每次读入一个字符s1[i]； 3) 若遇到数字或小数点，则立即写入s2[i]，若遇算数运算符，将“ ”（空格）写入s2[i]；

合集下载

算术表达式求值-数据结构实验报告

算术表达式求值-数据结构实验报告


//存放运算数的栈的顺序存储表示
//存放运算符的栈的顺序存储表示
void InitStack(SqStack *S) //构造空栈（运算数 栈） { S->base=(float*)malloc((STACK_INIT_SIZE)*sizeof(float)); S->top=S->base; S->stacksize=STACK_INIT_SIZE; } void initStack(sqStack *S) //构造空栈（运算符 栈） { S->base=(char*)malloc((STACK_INIT_SIZE)*sizeof(char)); S->top=S->base; S->stacksize=STACK_INIT_SIZE; } float GetTop(SqStack *S) //用e返回栈顶元素（运
初始条件：a, b为整数，OP为运算符。 操作结果：a与b进行运算，OP为二元运算符，返回其值。 }ADT Stack （2）符号之间的优先权关系比较 <：的优先权低于: =：的优先权等于 >：的优先权高于 + + * / ( ) # > > > > < > < > > > > < > < * < < > > < > < / < < > > < > < < ( < < < < < ) > > > > = > > = # > > > >
//用e返回栈顶元素
数据结构实验报告表达式求值

数据结构实验报告表达式求值

数据结构实验报告题目：编制一个表达式求值的程序。

一．需求分析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.本次作业的核心就是利用堆栈将中序表达式改成后序表达式，然后进行表达式的求值。

数据结构实验报告--表达式求值

数据结构实验报告--表达式求值


void Initstack1(stack1 *s>
{
(*s>->base = (int *>malloc(SIZE * (sizeof(int>>>
。
(*s>->top = (*s>->base
。
(*s>->stacksize = INCREMENT 。
}
int Ifempty2(stack2 *s>
<6）中缀转后缀并计算模块：
( 三 > 详细设计
1．元素类型 , 结点类型和指针类型：
typedef struct{
int stacksize 。 int *base 。
int *top 。
}Sqstack1,*stack1 。
typedef struct{
int stacksize 。
char *base 。
{
if(((a=='*'>||(a=='/'>>&&((b=='+'>||(b=='-'>||(b=='#'>>>
5PCzVD7HxA
return '>'
。
else
return '<'
。
}
<4）运算符操作模块；
int Operate(int a,char b,int c>
{
int t 。
if(b == '+'> t = a + c
{
【7A版】四则运算表达式求值实验报告

【7A版】四则运算表达式求值实验报告

HUNANUNIVERSITY课程实习报告题目：四则运算表达式求值学生姓名：学生学号：专业班级：指导老师：完成日期：一、需求分析四则运算表达式求值，将四则运算表达式用中缀表达式表示，然后转换为后缀表达式，并计算结果。

本程序要求利用二叉树后序遍历来实现表达式的转换，同时可以使用实验2的结果来求解后缀表达式的值。

在字符界面上输入一个中缀表达式，回车表示结束。

如果该中缀表达式正确，那么在字符界面上输出其后缀表达式，其中后缀表达式中两相邻操作数之间利用空格隔开；如果不正确，在字符界面上输出表达式错误提示。

测试数据输入：21+23G（12-6）输出：2123126-G+二、详细设计输入和输出的格式输入本程序可以将输入的四则运算表达式（中缀表达式）转换为后缀表达式输出后缀表达式为：//输出结果的位置表达式的值为：//输出结果的位置三、调试分析本次实验的难点主要是在建立二叉树的问题上。

关于如何把中缀表达式存入二叉树中，我参考了网上的一些方法，成功实现了目标，但是却遇到了一个问题，那就是不能处理小数，甚至两位或两位以上的整数。

因为如果采用字符数组来存储操作数，运算符合一位整数还可以处理，但对于两位数就就会出问题，最后我改进采用字符串数组来存储操作数，成功解决了问题。

另外在处理输入的非法表达式问题中，我也费了很大功夫，但总体问题不大。

四、测试结果五、用户使用说明（可选）1、运行程序时提示输入四则运算表达式本程序可以将中缀表达式转化为后缀表达式，并计算结果请输入四则运算表达式：输出后缀表达式为：表达式的值为：程序源代码（c++）#include<iostream>#include<string>#include<stack>#include<iomanip>constintMaG=100;usingnamespacestd;classNode{public:charch[MaG];//考虑到数值有时会是两位数，所以使用字符串数组NodeGlChild;NodeGrChild;Node(){strcpy(ch,"");lChild=rChild=NULL;}~Node(){if(lChild!=NULL)deletelChild;if(rChild!=NULL)deleterChild;}};staticintcount=0;staticchararray[MaG];//保存原始的中缀表达式staticcharstr[2GMaG];//保存后序遍历出来的字符串，为表达式求值提供方便staticintk=0;chargetOp(NodeGtemp);//temp指针保存每个结点，返回的是运算符NodeGcrtTree(NodeGroot);//传入根结点指针，返回根结点指针voidoutput(NodeGroot);//获得处理后的字符串boolisError(char);//判断字符是否有问题voiddeal();//对字符数组进行处理doublevalue(string);//计算后缀表达式，得到其结果。