数据结构算术表达式求值实验
北京理工大学珠海学院
《数据结构》课程设计报告
题目：____________算术表达式求值_________________
所在学院：
专业班级：
学生姓名：
指导教师：
2010年05 月26 日
目录
1．前言 (1)
2．概要设计 (1)
2.1 数据结构设计 (1)
2.2 算法设计 (1)
2.3 ADT描述 (2)
2.4 功能模块分析 (2)
3．详细设计 (3)
3.1 数据存储结构设计 (3)
3.2主要算法流程图（或算法伪代码） (3)
4．软件测试 (6)
5．心得体会 (8)
参考文献 (8)
附录 (8)
1．前言
在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。
算法输入：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为简化，规定操作数只能为正整数，操作符为+、-*、/，用#表示结束。
算法输出：表达式运算结果。
算法要点：设置运算符栈和运算数栈辅助分析算符优先关系。在读入表达式的字符序列的同时，完成运算符和运算数的识别处理，以及相应运算。
2．概要设计
2.1 数据结构设计
任何一个表达式都是由操作符，运算符和界限符组成的。我们分别用顺序栈来寄存表达式的操作数和运算符。栈是限定于紧仅在表尾进行插入或删除操作的线性表。顺序栈的存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top 指示栈顶元素在顺序栈中的位置，base 为栈底指针，在顺序栈中，它始终指向栈底，即top=base 可作为栈空的标记，每当插入新的栈顶元素时，指针top 增1，删除栈顶元素时，指针top 减1。
2.2 算法设计
为了实现算符优先算法。可以使用两个工作栈。一个称为OPTR ，用以寄存运算符，另一个称做OPND ，用以寄存操作数或运算结果。
1.首先置操作数栈为空栈，表达式起始符”#”为运算符栈的栈底元素；
2.依次读入表达式，若是操作符即进OPND 栈，若是运算符则和OPTR 栈的栈顶运算符比较优先权后作相应的操作，直至整个表达式求值完毕（即OPTR 栈的栈顶元素和当前读入的字符均为”#”）。
2.3 ADT 描述
ADT Stack{
数据对象：D={i a |i a ∈ElemSet,i=1,2,…，n, n ≧0} 数据对象：R1={<1,-i i a a >|1-i a ,D a i ∈,i=2,…，n}
约定n a 端为栈顶，i a 端为栈底。
基本操作：
InitStack(&S)
操作结果：构造一个空栈S 。 GetTop(S)
初始条件：栈S 已存在。
操作结果：用P 返回S 的栈顶元素。 Push(&S ，ch)
初始条件：栈S 已存在。
Pop(&S)
初始条件：栈S已存在。
操作结果：删除S的栈顶元素。
In(ch)
操作结果：判断字符是否是运算符，运算符即返回1。
Precede(c1, c2)
初始条件：c1,c2为运算符。
操作结果：判断运算符优先权，返回优先权高的。
Operate(a,op,b)
初始条件：a,b为整数，op为运算符。
操作结果：a与b进行运算，op为运算符，返回其值。
num(n)
操作结果：返回操作数的长度。
EvalExpr()
初始条件：输入表达式合法。
操作结果：返回表达式的最终结果。
}ADT Stack
2.4 功能模块分析
1.栈的基本功能。
InitStack(Stack *s) 和InitStack2(Stack2 *s)分别构造运算符栈与构造操作数栈，Push(Stack *s,char ch) 运算符栈插入ch为新的栈顶元素，Push2(Stack2 *s,int ch) 操作数栈插入ch为新的栈顶元素，Pop(Stack *s) 删除运算符栈s的栈顶元素，用p返回其值，Pop2(Stack2 *s)删除操作数栈s的栈顶元素，用p返回其值，GetTop(Stack s)用p返回运算符栈s的栈顶元素，GetTop2(Stack2 s) 用p返回操作数栈s的栈顶元素。
2.其它功能分析。
(1)In(char ch) 判断字符是否是运算符功能，运算符即返回1，该功能只需简单的一条语句即可实现，return(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#')。
(2) Precede(char c1,char c2) 判断运算符优先权功能，该函数判断运算符c1,c2的优先权，具体优先关系参照表1。
(3) Operate(int a,char op,int b)操作数用对应的运算符进行运算功能。运算结果直接返回。
(4) num(int n) 求操作数的长度功能，需要用itoa函数把int型转换成字符串型，strlen函数可求字符长度。
(5) EvalExpr()主要操作函数运算功能。分析详细见“3.详细设计…3.2”。
3．详细设计
3.1 数据存储结构设计
因为表达式是由操作符，运算符和界限符组成的。如果只用一个char类型栈，不能满足2位以上的整数，所以还需要定义一个int类型的栈用来寄存操作数。
/* 定义字符类型栈*/
typedef struct{
int stacksize;
char *base;
char *top;
} Stack;
/* 定义整型栈*/
typedef struct{
int stacksize;
int *base;
int *top;
} Stack2;
3.2主要算法流程图（或算法伪代码）
1. Precede(char c1,char c2) 判断运算符优先权，返回优先权高的。
算符间的优先关系如下：
表 1
算法伪代码如下：
char Precede(char c1,char c2)
{
static char array[49]={
'>', '>', '<', '<', '<', '>', '>',
'>', '>', '<', '<', '<', '>', '>',
'>', '>', '>', '>', '<', '>', '>',
'<', '<', '<', '<', '<', '=', '!',
'>', '>', '>', '>', '!', '>', '>',
'<', '<', '<', '<', '<', '!', '='}; //用一维数组存储49种情况
switch(c1)
{
/* i为下面array的横标*/
case '+' : i=0;break;
case '-' : i=1;break;
case '*' : i=2;break;
case '/' : i=3;break;
case '(' : i=4;break;
case ')' : i=5;break;
case '#' : i=6;break;
}
switch(c2)
{
/* j为下面array的纵标*/
case '+' : j=0;break;
case '-' : j=1;break;
case '*' : j=2;break;
case '/' : j=3;break;
case '(' : j=4;break;
case ')' : j=5;break;
case '#' : j=6;break;
}
return (array[7*i+j]); /* 返回运算符array[7*i+j]为对应的c1,c2优先关系*/ }
2. int EvalExpr()主要操作函数。算法概要流程图：
利用该算法对算术表达式3*(7-2)求值操作过程如下：
表2
算法伪代码如下：
int EvalExpr()//主要操作函数
{ c = *ptr++;
while(c!='#'||GetTop(OPTR)!='#')
{
if(!In(c)) //不是运算符即进栈
{ if(!In(*(ptr-1))) ptr=ptr-1;
m=atoi(ptr);//取字符串前面的数字段
n=num(m);
Push2(&OPND,m);
ptr=ptr+n;
c=*ptr++;
}
else
switch(Precede(GetTop(OPTR),c))
{
case '<': //栈顶元素优先权底
Push(&OPTR,c);
c = *ptr++;
case '=': //脱括号并接收下一字符
x=Pop(&OPTR);
c = *ptr++;
break;
case '>'://退栈并将运算结果入栈theta=Pop(&OPTR);
b=Pop2(&OPND); a=Pop2(&OPND); Push2(&OPND,Operate(a,theta,b)); break;
}
}
4．软件测试
1.运行成功后界面。
2.输入正确的表达式后。
3.更改表达式，输入有2位数的整数调试。
5．心得体会
这次课程设计让我更加了解大一学到的C和这个学期学到的数据结构。课设题目要求不仅要求对课本知识有较深刻的了解，同时要求程序设计者有较强的思维和动手能力和更加了解编程思想和编程技巧。
这次课程设计让我有一个深刻的体会，那就是细节决定成败，编程最需要的是严谨，如何的严谨都不过分，往往检查了半天发现错误发生在某个括号，分号，引号，或者数据类型上。就像我在写EvalExpr()函数时，忘了指针的地址符值不用加*号，这一点小小的错误也耽误了我几十分钟，所以说细节很重要。
程序设计时，也不要怕遇到错误，在实际操作过程中犯的一些错误还会有意外的收获，感觉课程设计很有意思。在具体操作中这学期所学的数据结构的理论知识得到巩固，达到
C语言具有的语句简洁，使用灵活，执行效率高等特点。发现上机的重要作用，特别算术表达式有了深刻的理解。
这个程序是我们3个人完成的，同时我认为我们的工作是一个团队的工作，团队需要个人，个人也离不开团队，必须发扬团结协作的精神。某个人的离群都可能导致导致整项工作的失败。实习中只有一个人知道原理是远远不够的，必须让每个人都知道，否则一个人的错误，就有可能导致整个工作失败。团结协作是我们成功的一项非常重要的保证。而这次课程设计也正好锻炼我们这一点，这也是非常宝贵的
最后，感谢老师在这次课程设计的悉心指导，祝老师身体健康，工作顺利。
参考文献：
1.《数据结构(C语言版)》严蔚敏清华大学出版社
2.《C语言程序设计》丁峻岭中国铁道出版社
3.《C程序设计》谭浩强清华大学出版社
附录
程序源代码：
#include
#include
#include
#define NULL 0
#define OK 1
#define ERROR -1
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 20
/* 定义字符类型栈*/
typedef struct{
int stacksize;
char *base;
char *top;
} Stack;
/* 定义整型栈*/
typedef struct{
int stacksize;
int *base;
int *top;
} Stack2;
/* ----------------- 全局变量--------------- */
Stack OPTR;/* 定义运算符栈*/
Stack2 OPND; /* 定义操作数栈*/
char expr[255] = ""; /* 存放表达式串*/
char *ptr = expr;
int InitStack(Stack *s) //构造运算符栈
{
s->base=(char *)malloc(STACK_INIT_SIZE*sizeof(char)); if(!s->base) return ERROR;
s->top=s->base;
s->stacksize=STACK_INIT_SIZE;
}
int InitStack2(Stack2 *s) //构造操作数栈
{
s->base=(int *)malloc(STACK_INIT_SIZE*sizeof(int));
if(!s->base) return ERROR;
s->stacksize=STACK_INIT_SIZE;
s->top=s->base;
return OK;
}
int In(char ch) //判断字符是否是运算符，运算符即返回1 {
return(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#'); }
int Push(Stack *s,char ch) //运算符栈插入ch为新的栈顶元素{
*s->top=ch;
s->top++;
return 0;
}
int Push2(Stack2 *s,int ch)//操作数栈插入ch为新的栈顶元素{
*s->top=ch;
return 0;
}
char Pop(Stack *s) //删除运算符栈s的栈顶元素，用p返回其值{
char p;
s->top--;
p=*s->top;
return p;
}
int Pop2(Stack2 *s)//删除操作数栈s的栈顶元素，用p返回其值{
int p;
s->top--;
p=*s->top;
return p;
}
char GetTop(Stack s)//用p返回运算符栈s的栈顶元素
{
char p=*(s.top-1);
return p;
}
int GetTop2(Stack2 s) //用p返回操作数栈s的栈顶元素
int p=*(s.top-1);
return p;
}
/* 判断运算符优先权，返回优先权高的*/ char Precede(char c1,char c2)
{
int i=0,j=0;
static char array[49]={
'>', '>', '<', '<', '<', '>', '>',
'>', '>', '<', '<', '<', '>', '>',
'>', '>', '>', '>', '<', '>', '>',
'>', '>', '>', '>', '<', '>', '>',
'<', '<', '<', '<', '<', '=', '!',
'>', '>', '>', '>', '!', '>', '>',
'<', '<', '<', '<', '<', '!', '='};
switch(c1)
{
/* i为下面array的横标*/
case '+' : i=0;break;
case '-' : i=1;break;
case '*' : i=2;break;
case '/' : i=3;break;
case '#' : i=6;break;
}
switch(c2)
{
/* j为下面array的纵标*/
case '+' : j=0;break;
case '-' : j=1;break;
case '*' : j=2;break;
case '/' : j=3;break;
case '(' : j=4;break;
case ')' : j=5;break;
case '#' : j=6;break;
}
return (array[7*i+j]); /* 返回运算符*/ }
/*操作函数*/
int Operate(int a,char op,int b)
{
switch(op)
{
case '+' : return (a+b);
case '/' : return (a/b);
}
return 0;
}
int num(int n)//返回操作数的长度
{
char p[10];
itoa(n,p,10);//把整型转换成字符串型n=strlen(p);
return n;
}
int EvalExpr()//主要操作函数
{
char c,theta,x; int n,m;
int a,b;
c = *ptr++;
while(c!='#'||GetTop(OPTR)!='#')
{
if(!In(c))
{ if(!In(*(ptr-1))) ptr=ptr-1;
m=atoi(ptr);//取字符串前面的数字段
Push2(&OPND,m);
ptr=ptr+n;
c=*ptr++;
}
else
switch(Precede(GetTop(OPTR),c)) {
case '<':
Push(&OPTR,c);
c = *ptr++;
break;
case '=':
x=Pop(&OPTR);
c = *ptr++;
break;
case '>':
theta=Pop(&OPTR);
b=Pop2(&OPND); a=Pop2(&OPND); Push2(&OPND,Operate(a,theta,b)); break;
}
}
}
int main( )
{
printf("请输入正确的表达式以'#'结尾:");
do{
gets(expr);
}while(!*expr);
InitStack(&OPTR); /* 初始化运算符栈*/
Push(&OPTR,'#'); /* 将#压入运算符栈*/
InitStack2(&OPND); /* 初始化操作数栈*/
printf("表达式结果为:%d\n", EvalExpr());
return 0;
}
课程设计成绩评定表
数据结构表达式求值实验报告
竭诚为您提供优质文档/双击可除数据结构表达式求值实验报告 篇一：数据结构实验二——算术表达式求值实验报告 《数据结构与数据库》 实验报告 实验题目算术表达式求值 学院：化学与材料科学学院 专业班级：09级材料科学与工程系pb0920603 姓学 邮名：李维谷号：pb09206285箱： liwg@https://www.sodocs.net/doc/c711255412.html,指导教师：贾伯琪 实验时间：20XX年10月10日 一、需要分析 问题描述： 表达式计算是实现程序设计语言的基本问题之一，它的实现是栈的应用的一个典型例子。设计一个程序，演示通过将数学表达式字符串转化为后缀表达式，并通过后缀表达式结合栈的应用实现对算术表达式进行四则混合运算。
问题分析： 在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。 设置运算符栈（字符型）和运算数栈（浮点型）辅助分析算符优先关系。在读入表达式的字符序列的同时完成运算符和运算数的识别处理，然后进行运算数的数值转换在进行四则运算。 在运算之后输出正确运算结果，输入表达式后演示在求值中运算数栈内的栈顶数据变化过程，最后得到运算结果。 算法规定： 输入形式：一个(:数据结构表达式求值实验报告)算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为使实验更完善，允许操作数为实数，操作符为（、）、.（表示小数点）、+、-、*、/、^（表示乘方），用#表示结束。 输出形式：演示表达式运算的中间结果和整个表达式的最终结果，以浮点型输出。 程序功能：对实数内的加减乘除乘方运算能正确的运算出结果，并能正确对错误输入和无定义的运算报错，能连续测试多组数据。 测试数据：正确输入：12*（3.6/3+4^2-1）#
全国计算机等级考试二级公共基础之树与二叉树1
全国计算机等级考试二级公共基础之树与二叉树 1.6 树与二叉树 1.6.1 树的基本概念 树是一种简单的非线性结构。在树这种结构中，所有元素之间的关系具有明显的层次关系。用图形表示树这种数据结构时，就象自然界中的倒长的树，这种结构就用“树”来命名。如图： 在树结构中，每个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称为树的根（如R）。 在树结构中，每一个结点可以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点（如W，Z，A ，L，B，N，O，T，H，X）。 在树结构中，一个结点拥有的后件个数称为结点的度（如R的度为4，KPQDEC 结点度均为2）。 树的结点是层次结构，一般按如下原则分层：根结点在第1层；同一个层所有结点的所有子结点都在下一层。树的最大层次称为树的深度。如上图中的树深度为4。R结点有4棵子树，KPQDEC结占各有两棵子树；叶子没有子树。 在计算机中，可以用树结构表示算术运算。在算术运算中，一个运算符可以有若干个运算对象。如取正（+）与取负（-）运算符只有一个运算对象，称为单目运算符；加（+）、减（-）、乘（*）、除（/）、乘幂（**）有两个运算对象，称为双目运算符；三元函数f(x,y,z)为 f函数运算符，有三个运算对象，称为三目运算符。多元函数有多个运算对象称多目运算符。 用树表示算术表达式原则是： (1)表达式中的每一个运算符在树中对应一个结点，称为运算符结点
(2)运算符的每一个运算对象在树中为该运算结点的子树(在树中的顺序从 左到右) (3)运算对象中的单变量均为叶子结点 根据上面原则，可将表达式：a*(b+c/d)+c*h-g*f表示如下的树。 树在计算机中通常用多重链表表示，多重链表的每个结点描述了树中对应结点的信息，每个结点中的链域（指针域）个数随树中该结点的度而定。 1.6.2 二叉树及其基本性质 1. 什么是二叉树 二叉树是很有用的非线性结构。它与树结构很相似，树结构的所有术语都可用到二叉树这种结构上。 二叉树具有以下两个特点： （1）非空两叉树只有一个根结点 （2）每个结点最多有两棵子树，且分别称该结点的左子树与右子树。 也就是说，在二叉树中，每一个结点的度最大为2，而且所有子树也均为二叉树。二叉树中的每一个结点可以有左子树没有右子树，也可以有右子树没有左子树，甚至左右子树都没有。
数据结构实验二——算术表达式求值实验报告
《数据结构与数据库》 实验报告 实验题目 算术表达式求值 学院：化学与材料科学学院 专业班级：09级材料科学与工程系PB0920603 姓名：李维谷 学号：PB09206285 邮箱：liwg@https://www.sodocs.net/doc/c711255412.html, 指导教师：贾伯琪 实验时间：2010年10月10日 一、需要分析 问题描述：
表达式计算是实现程序设计语言的基本问题之一，它的实现是栈的应用的一个典型例子。设计一个程序，演示通过将数学表达式字符串转化为后缀表达式，并通过后缀表达式结合栈的应用实现对算术表达式进行四则混合运算。 问题分析： 在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。 设置运算符栈（字符型）和运算数栈（浮点型）辅助分析算符优先关系。在读入表达式的字符序列的同时完成运算符和运算数的识别处理，然后进行运算数的数值转换在进行四则运算。 在运算之后输出正确运算结果，输入表达式后演示在求值中运算数栈内的栈顶数据变化过程，最后得到运算结果。 算法规定： 输入形式：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为使实验更完善，允许操作数为实数，操作符为（、）、.（表示小数点）、+、-、*、/、^（表示乘方），用#表示结束。 输出形式：演示表达式运算的中间结果和整个表达式的最终结果，以浮点型输出。 程序功能：对实数内的加减乘除乘方运算能正确的运算出结果，并能正确对错误输入和无定义的运算报错，能连续测试多组数据。 测试数据：正确输入：12*（3.6/3+4^2-1）# 输出结果：194.4
用栈和二叉树实现中缀表达式转后缀表达式构建计算机并求值实验报告
实验报告 姓名：黄雄镖学号：13331093 院系专业：软件学院2013级教务4班 完成日期：2014 年10 月20 日 实验题目：实现一个较为通用的计算器 需求分析： 实现一个包含加减乘除运算的较为通用的计算器，操作数可能是负数，并且可能是多位数。运算式中可以有括号和多余空格。计算器对负号不敏感, 形如1+-1或者1+(-1)都是可以接受的。 概要设计 思路: 将表达式的中缀表达式转换成后缀表达式，然后利用一个栈或者建立二叉树对后缀表达式进行求值。 由于多位数在转为后缀表达式时会分不清, 故在每个数和运算符后面加上一个空格作为区别 在主程序中调用用栈求值的计算器类和用二叉树计算的计算器类, 输出算式的结果 13331093_03.h里存放用栈求值的计算器类 13331093_03_tree.h里存放用二叉树计算的计算器类 13331093_03.h的类里主要包括: 获得算术表达式的函数getexpression(string expression), expression为所要计算的算术表达式计算函数calculate(string num2, string num1, string op), 输入为两个数(字符串形式)和一个操作符, 返回值为计算结果(字符串形式) 返回中缀表达式函数ShowMiddleExpression(), 返回的中缀表达式为字符串形式 RidSpace(string origin)用于去除输入中多余的空格, 输入为要除去空格的算术表达式, 返回去掉空格的算术表达式
MidToLast(string str)中缀表达式转后缀表达式 获得后缀表达式函数GetLastExpression(), 返回的后缀表达式为字符串形式 用栈执行计算后缀表达式函数exe(), 返回计算结果为字符串形式 13331093_03_tree.h类里主要包括: 获得算术表达式的函数getexpression(string expression), expression为所要计算的算术表达式计算函数calculate(string num2, string num1, string op), 输入为两个数(字符串形式)和一个操作符, 返回值为计算结果(字符串形式) 返回中缀表达式函数ShowMiddleExpression(), 返回的中缀表达式为字符串形式 RidSpace(string origin)用于去除输入中多余的空格, 输入为要除去空格的算术表达式, 返回去掉空格的算术表达式 MidToLast(string str)中缀表达式转后缀表达式 获得后缀表达式函数GetLastExpression(), 返回的后缀表达式为字符串形式 生成一颗二叉树的函数makeTree(TNode *&p) 后序遍历二叉树并计算的函数PostOrder(TNode *p), 返回计算结果为字符串形式 a.调试过程遇到的问题与解决方案： 遇到的问题:调试过程中出现程序崩溃的现象, 后来debug发现是没有考虑到执行运算过程中出现的-()的情况 原因:没有考虑-()的情况, 导致栈为空的时候还弹出元素 解决方案：特殊处理这种情况 b.时间和空间复杂度：
算术表达式求值演示程序
数理学院 课程设计报告书 课程名称数据结构课程设计 设计题目算术表达式求值演示 专业班级 学号 姓名 指导教师
2014 年12 月
4.2.2 基本操作： InitStack(&S) 操作结果：构造一个空栈S。 GetTop(S) 初始条件：栈S 已存在。 操作结 果： 用P 返回S的栈顶元素。Push(&S 初始条 件：，ch) 栈S 已存在。 操作结 果：插入元素ch 为新的栈顶元素。 Pop(&S) 初始条件：栈S 已存在。 操作结 果：删除S 的栈顶元素。 In(ch) 操作结果：判断字符是否是运算符，运算符即返回1 Precede(c1, c2) 初始条件：c1,c2 为运算符。操作结果：判断运算符优先权，返回优先权高的。Operate(a,op,b) 初始条件：a,b 为整数，op为运算符。操作结果： a 与 b 进行运算，op 为运算符，返回其值。num(n) 操作结果：返回操作数的长度。EvalExpr() 初始条件：输入表达式合法。操作结果：返回表达式的最终结果。}ADT Stack 主程序的流程：
EvaluateExpression() 函数实现了对表达式求值的功能，main() 函数直接调用EvaluateExpression() 对输入的表达式求值输出。 4.2.3 函数的调用关系图
4.3 详细设计 4.3.1 ① . Precede(char c1,char c2)判断运算符优先权，返回优先权高的 算符间的优先关系 如下： 算法伪代码如下： char Precede(char c1,char c2) { static char array[49]={ >', '>', '<', '<', '<', '>', '>', >', '>', '<', '<', '<', '>', '>', >', '>', '>', '>', '<', '>', '>', >', '>', '>', '>', '<', '>', '>', <', '<', '<', '<', '<', '=', '!', >', '>', '>', '>', '!', '>', '>', <', '<', '<', '<', '<', '!', '='}; // 用一维数组存储 49 种情况 switch(c1) { /* i 为下面 array 的横标 */ case '+' : i=0;break; case '-' : i=1;break; case '*' : i=2;break;
数据结构算术表达式求值实验报告
软件技术基础实验报告 实验名称：表达式计算器 系别：通信工程 年级： 班级： 学生学号： 学生姓名： 《数据结构》课程设计报告 题目简易计算表达式的演示 【题目要求】 要求：实现基本表达式计算的功能 输入：数学表达式，表达式由整数和“+”、“-”、“×”、“/”、“（”、“）”组成输出：表达式的值 基本操作：键入表达式，开始计算，计算过程和结果记录在文档中 难点：括号的处理、乘除的优先级高于加减
1．前言 在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。 算法输入：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为简化，规定操作数只能为正整数，操作符为+、-*、/、=，用#表示结束。 算法输出：表达式运算结果。 算法要点：设置运算符栈和运算数栈辅助分析算符优先关系。在读入表达式的字符序列的同时，完成运算符和运算数的识别处理，以及相应运算。 2．概要设计 2.1 数据结构设计 任何一个表达式都是由操作符，运算符和界限符组成的。我们分别用顺序栈来寄存表达式的操作数和运算符。栈是限定于紧仅在表尾进行插入或删除操作的线性表。顺序栈的存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top 指示栈顶元素在顺序栈中的位置，base 为栈底指针，在顺序栈中，它始终指向栈底，即top=base 可作为栈空的标记，每当插入新的栈顶元素时，指针top 增1，删除栈顶元素时，指针top 减1。 2.2 算法设计 为了实现算符优先算法。可以使用两个工作栈。一个称为OPTR ，用以寄存运算符，另一个称做OPND ，用以寄存操作数或运算结果。 1.首先置操作数栈为空栈，表达式起始符”#”为运算符栈的栈底元素； 2.依次读入表达式，若是操作符即进OPND 栈，若是运算符则和OPTR 栈的栈顶运算符比较优先权后作相应的操作，直至整个表达式求值完毕（即OPTR 栈的栈顶元素和当前读入的字符均为”#”）。 2.3 ADT 描述 ADT Stack{ 数据对象：D={ i a |i a ∈ElemSet,i=1,2,…，n, n ≧0} 数据对象：R1={< 1 ,-i i a a >| 1-i a ,D a i ∈,i=2,…，n}
嵌入式--计算器--实验报告
计算器设计实验报告 一、实验设计主要分工 04009320 文斌：算法设计，LCD显示。 04** 张希：界面（按钮控件）设计，文件内容读取。 共同调试、完善设计。 二、程序设计实现功能效果 （1）支持整数、小数基本加减乘除运算； （2）有优先级的判别计算。优先级由高到低一次为括号运算、乘除运算、加减运算。（3）支持键盘输入和触摸屏输入； （4）能读取指定目录下文本内容（内容为计算表达式）并计算得出结果，将内容和结果显示在LCD上。 程序任务开始后，等待键盘或触摸屏的输入。输入键有0~9数字键、+-*/（）运算符、del退格键、clear清屏键、read读指定目录文本内容并计算键、enter'='键、‘.’小数点键。 每当有字符输入时，触摸屏相应键显示“AAA”，100ms后恢复原相应按键符号，同时LCD 屏幕上显示相应字符。当输入'del'键时，屏幕显示去掉最后一位字符。当输入'='号后，得出计算结果，结果显示于表达式的下一行。若是除零错误，则结果显示为“/0ERROR!”。若有非法字符（触摸点不能识别为设计按键符则视为非法字符），则结果输出为“Syntax Error!!”。若表达式有运算符连续输入，则忽略前面的运算符，只取最后一位运算符计算，正常显示数字结果。当输入'clear'键时，情况显示区域。当输入'read'键时，从指定目录文本文件中读取表达式并计算。将表达式内容和计算结果显示在LCD上。 三、程序算法实现 1、计算算法 首先将输入的0~9数字、+-*/（）运算符的内容存储于一个全局变量cal[number]中， 表达为中缀表达式。用void str2repol（）函数，将输入字符串cal[number]转换成逆波 兰表达式并存于全局数组char repol[maxs]中。str2repol（）函数中缀表达式转成逆波兰 后缀表达式算法如下： (1)首先构造一个运算符栈stack[maxs]，此运算符在栈内遵循越往栈顶优先级越高的 原则。
第6章树和二叉树习题
第六章 树和二叉树 一、选择题 1．算术表达式a+b*（c+d/e ）转为后缀表达式后为（ B ） A ．ab+cde/* B ．abcde/+*+ C ．abcde/*++ D ．2. 设有一表示算术表达式的二叉树（见下图）， 它所表示的算术表达式是（ C ） A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+（F-G ）) D. A*B+C/D*E+F-G 3. 设树T 的度为4，其中度为1，2，3和4的结点个数分别为4，2，1 ，1 则T 中的叶子数为（ D ） A ．5 B ．6 C ．7 D ．8 4. 在下述结论中，正确的是（ D ） ①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意 交换; ④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A ．①②③ B ．②③④ C ．②④ D ．①④ 5. 设森林F 对应的二叉树为B ，它有m 个结点，B 的根为p,p 的右子树结点个数为n,森林F 中第一棵树的结点个数是（ A ） A ．m-n B ．m-n-1 C ．n+1 D ．条件不足，无法确定 6．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ B ） A ．9 B ．11 C ．15 D ．不确定 7．设森林F 中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F 对应的二叉树根结点的右子树上的结点个数是（ D ）。 A ．M1 B ．M1+M2 C ．M3 D ．M2+M3 8．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ E ） A ． 250 B ． 500 C ．254 D ．505 E ．以上答案都不对 9. 有关二叉树下列说法正确的是（ B ） A ．二叉树的度为2 B ．一棵二叉树的度可以小于2 C ．二叉树中至少有一个结点的度为2 D ．二叉树中任何一个结点的度都为2 10．二叉树的第I 层上最多含有结点数为（ C ） A ．2I B ． 2I-1-1 C ． 2I-1 D ．2I -1 11. 一个具有1025个结点的二叉树的高h 为（ C ） A ．11 B ．10 C ．11至1025之间 D ．10至1024之间 12．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( B )结点 A ．2h B ．2h-1 C ．2h+1 D ．h+1 13. 一棵树高为K 的完全二叉树至少有（ C ）个结点 A ．2k –1 B. 2k-1 –1 C. 2k-1 D. 2 k 14．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( C )次序的遍历 实现编号。 A ．先序 B. 中序 C. 后序 D. 从根开始按层次遍历 15．一棵二叉树的前序遍历序列为ABCDEFG ，它的中序遍历序列可能是（ B ）
四则运算表达式求值实验报告
HUNAN UNIVERSITY 课程实习报告 题目：四则运算表达式求值 学生姓名： 学生学号： 专业班级： 指导老师： 完成日期：
一、需求分析 四则运算表达式求值，将四则运算表达式用中缀表达式表示，然后转换为后缀表达式，并计算结果。 本程序要求利用二叉树后序遍历来实现表达式的转换，同时可以使用实验2的结果来求解后缀表达式的值。 在字符界面上输入一个中缀表达式，回车表示结束。如果该中缀表达式正确，那么在字符界面上输出其后缀表达式，其中后缀表达式中两相邻操作数之间利用空格隔开；如果不正确，在字符界面上输出表达式错误提示。 测试数据 输入： 21+23*（12-6） 输出： 21 23 12 6 -*+ 二、详细设计 输入和输出的格式 输入 本程序可以将输入的四则运算表达式（中缀表达式）转换为后缀表达式 输出 后缀表达式为：//输出结果的位置 表达式的值为：//输出结果的位置 三、调试分析 本次实验的难点主要是在建立二叉树的问题上。关于如何把中缀表达式存入二叉树中，我参考了网上的一些方法，成功实现了目标，但是却遇到了一个问题，那就是不能处理小数，甚至两位或两位以上的整数。因为如果采用字符数组来存储操作数，运算符合一位整数还可以处理，但对于两位数就就会出问题，最后我改进采用字符串数组来存储操作数，成功解决了问题。 另外在处理输入的非法表达式问题中，我也费了很大功夫，但总体问题不大。 四、测试结果 五、用户使用说明（可选） 1、运行程序时 提示输入四则运算表达式 本程序可以将中缀表达式转化为后缀表达式，并计算结果 请输入四则运算表达式： 输出 后缀表达式为： 表达式的值为： 程序源代码（c++） #include
算术表达式语法检查实验报告
中南民族大学计算机科学学院本科课程设计 任务书 设计名称：算术表达式语法检查 指导教师：下达时间： 2015-5-8 学生姓名：学号： 专业： 一、课程设计的基本要求 根据所学知识，编写指定题目的C++语言程序，并规范地完成课程设计报告。通过课程设计，加深对《C++面向对象程序设计》课程所学知识的理解，熟练掌握和巩固C++语言的基本知识和语法规范，掌握C++语言的基础知识，理解面向对象系统的封装性、继承性和多态性；熟练使用C语言中的函数、数组、指针、链表和字符串等基本知识；掌握类的定义、标准String类和向量；理解掌握友元函数和重载操作符，动态数组；理解掌握继承和多态性；掌握模版的使用；能够进行程序调试过程中的异常处理；进一步掌握利用C++进行类的定义和操作方法；进一步掌握类的继承和派生方法；进一步理解虚函数和多态；综合利用上述知识，学习设计并编写面向对象的C++简单应用程序；培养解决复杂任务功能分解方法（自顶向下逐步求精、模块化设计、信息隐藏等）。 学会编制结构清晰、风格良好、数据结构适当的C++语言程序，从而具备利用计算机编程分析解决综合性实际问题的初步能力。 具体要求如下： 1、采取模块化方式进行程序设计，要求程序的功能设计、数据结构设计及整体结构设计合理。学生也可根据自己对题目的理解增加新的功能模块（视情况可另外加分）。 2、系统以菜单界面方式（至少采用文本菜单界面，如能采用图形菜单界面更好）工作，运行界面友好，演示程序以用户和计算机的对话方式进行。 3、程序算法说明清晰，理论分析与计算正确，运行情况良好，实验测试数据无误，容错性强（能对错误输入进行判断控制）。 4、编程风格良好（包括缩进、空行、适当注释、变量名和函数名见名知意，程序容易阅读等）； 5、写出规范的课程设计报告，具体要求见相关说明文档。
算术表达式与二叉树
目录 一、系统开发的背景 (1) 二、系统分析与设计 (1) （一）系统功能要求 (1) （二）系统模块结构设计 (1) 三、系统的设计与实现 (3) （一）二叉树的遍历 (3) （二）算术表达式求值 (5) 四、系统测试 (9) （一）测试二叉树遍历函数 (9) （二）测试算术表达式求值函数 (10) 五、总结 (10) 六、附件（代码、部分图表） (10) (一)程序代码 (10) (二)实验截图 (15)
算术表达式与二叉树 一、系统开发的背景 为了方便进行基本的算术运算，减轻对数字较大的数操作时所带来的麻烦，及其在运算过程中错误的避免。因此设计算术表达式与二叉树的程序来解决此问题。 二、系统分析与设计 （一）系统功能要求 由于一个表达式和一棵二叉树之间，存在着自然的对应关系。遍写一个程序，实现基于二叉树表示的算术表达式的操作。算术表达式内可以含有变量（a～z）、常量（0～9）和二元运算符（+，-，*，/，^(乘幂)）。 具体实现以下操作： 1以字符序列的形式输入语法正确的前缀表达式并构造表达式。 2用带括弧的中缀表达式输出表达式。 3实现对变量V的赋值（V=c），变量的初值为0。 4对算术表达式E求值。 （二）系统模块结构设计 通过对系统功能的分析，基于二叉树表示的算术表达式的功能 如图（1）所示。
图1：基于二叉树表示的算术表达式的功能图 通过上图的功能分析，把整个系统划分为主要的两大个模块： 1、将语法正确的前缀表达式用二叉树的遍历转换成相应的遍历序列，必要时可以求出此二叉树的结点数及其树的深度。该模块借助函数BiTree Create(BiTree T)创建二叉树，void Preorder(BiTree T) 先序遍历， void InOrder(BiTree T)中序遍历，void PostOrder(BiTree T)后序遍历，int Sumleaf(BiTree T)统计叶结点的数目，int Depth(BiTree T)二叉树的深度6个函数联合来实现； 2、计算中序遍历所得的算术表达式的值。其中先要将扫描得到的中缀表达式转换为后缀表达式，然后利用栈的初始化，进栈与取栈顶元素操作进行对后缀表达式进行计算。该模块借助函数void InitStack(SeqStack *S)初始化栈，int PushStack(SeqStack *S,char e)进栈，int GetTop(SeqStack
算术表达式求值课程设计报告
课程设计 教学院 课程名称 题目 专业 班级 姓名 同组人员 指导教师 2013 年 6 月22 日 (完成时间)
目录 一．概述 (2) 二．总体方案设计 (4) 三．详细设计 (6) 四．程序的调试与运行结果说明 (14) 五．课程设计总结 (14) 六．附录 (16) 参考文献 (3233) （“目录”要求必须自动生成）
一概述（宋体，三号，加粗，居中） 1.课程设计的目的（小标题，宋体，四号，加粗，左对齐顶格） （1）．理解和掌握该课程中的有关基本概念，程序设计思想和方法。 （2）．培养综合运用所学知识独立完成课题的能力。 （3）．培养勇于探索、严谨推理、实事求是、有错必改，用实践来检验理论，全方位考虑问题等科学技术人员应具有的素质。 （4）．掌握从资料文献、科学实验中获得知识的能力，提高学生从别人经验中找到解决问题的新途径的悟性，初步培养工程意识和创新能力。 2.课程设计的要求 算术表达式求值程序实现以下功能： (1)构造一个空栈S,初始条件：栈S已存在 (2)用P返回S的栈顶元素 (3)插入元素ch为新的栈顶元素 (4)删除S的栈顶元素 (5)判断字符是否是运算符，运算符即返回1 (6)判断运算符优先权，返回优先权高的 (7)输入表达式 (8)返回表达式的最终结果。
二总体方案设计 a)需求分析 该程序能实现算术四则运算表达式的求值，显示运算过程。 输入的形式：表达式，例如5*（3+7）#。 包含的运算符只能有'+'、 '-'、'*'、 '/'、 ' (' ') '； 程序所能达到的功能：对表达式求值并输出。 b)总体设计 本程序使用的是编程工具是Visual c++ 6.0，实现了运算器的功能和仿真界面（大体界面如下图所示）。在基本要求的基础上，运算数可以是实数类型，同时增加了乘方运算的功能；可以实现对负数的运算，例如用户输入表达式6* （-0.25）,则程序会在负号的前面自动加上一个0。 1)算符包括加（+）、减（-）、乘（*）、除（/）、乘方（^）；另一个称作 OPND，用以寄存操作数和运算结果，操作数可以是float型的浮点数。 算法的基本思想是： 2)首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素； 依次读入表达式中的每个字符，若是操作数（浮点数）则进OPND栈， 若是运算符（+、—、*、/、^）则和OPTR栈的栈顶运算符比较优先权 后作相应操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当 前读入的字符均为“#”）。 3)编写一个原型为void strtofloat(char str[ ],int n,int i)，把一 个数字串转换为一个实型数，并压入运算数栈中。（整个程序的源代码 见附录，并有具体解释）
《数据结构课程设计》表达式求值实验报告
实验课程名称 专业班级 学生姓名 学号 指导教师 20 至 20 学年第学期第至周
算术表达式求值演示 一、概述 数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。 在这次的课程设计中我选择的题目是算术表达式求值演示。表达式计算是实现程序设计语言的基本问题之一，也是栈的应用的一个典型例子。设计一个程序，演示用算符优先法对算术表达式求值的过程。深入了解栈和队列的特性，以便在解决实际问题中灵活运用它们，同时加深对这种结构的理解和认识。 二、系统分析 1．以字符列的形式从终端输入语确的、不含变量的整数表达式。利用已知的算符优先关系，实现对算术四则混合运算表达式的求值，并仿照教科书的例子在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。 2．一般来说，计算机解决一个具体问题时，需要经过几个步骤：首先要从具体问题抽象出一个适当的数学模型，然后设计一个解决此数学模型的算法，最后编出程序，进行测试，调试直至得到想要的答案。对于算术表达式这个程序，主要利用栈，把运算的先后步骤进行分析并实现简单的运算！为实现算符优先算法，可以使用两个栈，一个用以寄存运算符，另一个用以寄存操作数和运算结果。 3．演示程序是以用户于计算机的对话方式执行，这需要一个模块来完成使用者与计算机语言的转化。 4．程序执行时的命令： 本程序为了使用具体，采用菜单式的方式来完成程序的演示，几乎不用输入什么特殊
的命令，只需按提示输入表达式即可。（要注意输入时格式，否者可能会引起一些错误）5. 测试数据。 三、概要设计 一个算术表达式中除了括号、界限符外，还包括运算数据和运算符。由于运算符有优先级别之差，所以一个表达式的运算不可能总是从左至右的循序执行。每次操作的数据或运算符都是最近输入的，这与栈的特性相吻合，故本课程设计借助栈来实现按运算符的优先级完成表达式的求值计算。 算法设计 程序包含三个模块 (1) 主程序模块，其中主函数为 void main{ 输入表达式； 根据要求进行转换并求值； 输出结果； } (2) 表达式求值模块——实现具体求值。 (3) 表达式转换模块——实现转换。 各个函数之间的调用关系
表达式求值实验报告
淮海工学院计算机工程学院 课程设计报告 设计名称：数据结构课程设计 选题名称：表达式求值 姓名：学号： 专业班级： 系（院）：计算机工程学院 设计时间： 设计地点：软件工程实验室、教室 指导教师评语： 成绩： 签名： 年月日
1．课程设计目的 1、训练学生灵活使用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。 2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 4.训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。 2．课程设计任务和要求： 任务 根据教材《数据结构-C语言描述》（耿国华主编）和参考书《数据结构题集（C语言版）》（严蔚敏、吴伟民主编）选择课程设计题目，要求通过设计，在数据结构的逻辑特性和物理表示、数据结构的选择使用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。 设计题目从任务书所列选题表中选取，每班每题不得超过2人。 学生自选课题 学生原则上可以结合个人爱好自选课题，要求课题有一定的深度和难度，有一定的算法复杂性，能够巩固数据结构课程所学的知识。学生自选课题需在18周前报课程设计指导教师批准方可生效。 要求： 1、在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。前期准备工作完备和否直接影响到后序上机调试工作的效率。在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率。 2、.设计的题目要求达到一定工作量（300行以上代码），并具有一定的深度和难度。 3、程序设计语言推荐使用C/C++，程序书写规范，源程序需加必要的注释; 4、每位同学需提交可独立运行的程序； 5 、每位同学需独立提交设计报告书（每人一份），要求编排格式统一、规范、内容充实，不少于10页（代码不算）； 6、课程设计实践作为培养学生动手能力的一种手段，单独考核。 3．课程设计说明书
C语言_算术表达式求值_代码
源代码： //用来存储字符的结点类型 typedef struct CharNode { char c; struct CharNode *next; }CharNode; //用来存储数的结点类型 typedef struct IntNode { long double i; struct IntNode *next; }IntNode; //用来存储数的结点类型 typedef struct Node { long double n; struct Node_ys_char *next; }Node; //用来存储运算符的结点类型 typedef struct Node_ys_char { char c; struct Node_ys_char *next_c; struct Node *next; }Node_ys_char; char Precede(char x,char y)//运算符优先级判断{ int i,j; int from[5][5] ={ {0,0,-1,-1,0}, {0,0,-1,-1,0}, {1,1,0,0,1},
{1,1,0,0,1}, {0,0,-1,-1,0} };//定义一个二维数组存放算术符号的优先级 switch(x) { case '+':i=0;break; case '-':i=1;break; case '*':i=2;break; case '/':i=3;break; case '#':i=4;break; } switch(y) { case '+':j=0;break; case '-':j=1;break; case '*':j=2;break; case '/':j=3;break; case '#':j=4;break; } if(from[i][j]==1)//说明运算符i的优先级比j的优先级高return '>'; if(from[i][j]==-1) return '<'; else return '='; } //输入表达式，并对特殊情况做处理 CharNode *CreatRegister() { CharNode *top,*p,*q,*e; top=(CharNode *)malloc(sizeof(CharNode)); p=q=top; scanf("%c",&p->c); scanf("%c",&p->c);
C语言程序设计实验报告实验数据类型运算符和表达式
凯里学院C 语言程序设计实验报告 ×××××专业××年级××班，学号××××××姓名××成绩 合作者实验日期年月日 指导教师评阅日期年月日 实验二数据类型、运算符和表达式 一、实验目的： （1）掌握C 语言数据类型，熟悉如何定义一个整型、字符型、实型变量、以及对它们赋值的方法，了解以上类型数据输出时所用的格式转换符。 （2）学会使用C 的有关算术运算符，以及包含这些运算符的表达式，特别是自加（++）和自减（――）运算符的使用。 （3）掌握C 语言的输入和输出函数的使用 （4）进一步熟悉C 程序的编辑、编译、连接和运行的过程，学会使用stepbystep 功能。 （5）认真阅读教材数据类型，算术运算符和表达式，赋值运算符和表达式部分内容。 二、实验内容： (1)输人并运行下面的程序 #include
printf("%c%c\n",c1,c2); } （2）按习题3.7的要求编程序并上机运行 该题的要求是: 要将“China”译成密码，密码规律是:用原来字母后面的第4个字母代替原来的字母。 例如，字母“A”后面第4个字母是“E”，用“E”代替“A”。因此，“China”应译为“Glmre"。 请编一程序，用赋初值的方法使。cl，c2，c3，c4，c5五个变量的值分别为‘C’、‘h’、‘i’、‘n’、‘a’，经过运算，使cl，c2，c3，c4，c5分别变为‘G’、‘l’、‘m’、‘r’、‘e’，并输出。 三、实验步骤： (1)输人并运行下面的程序 #include
数据结构实验二叉树
实验六：二叉树及其应用 一、实验目的 树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构的特性，以及如何应用树结构解决具体问题。 二、问题描述 首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。其次，以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。 如算术表达式：a+b*(c-d)-e/f 三、实验要求 如果利用完全二叉树的性质和二叉链表结构建立一棵二叉树，分别计算统计叶子结点的个数。求二叉树的深度。十进制的四则运算的计算器可以接收用户来自键盘的输入。由输入的表达式字符串动态生成算术表达式所对应的二叉树。自动完成求值运算和输出结果。四、实验环境 PC微机 DOS操作系统或 Windows 操作系统 Turbo C 程序集成环境或 Visual C++ 程序集成环境 五、实验步骤 1、根据二叉树的各种存储结构建立二叉树； 2、设计求叶子结点个数算法和树的深度算法； 3、根据表达式建立相应的二叉树，生成表达式树的模块； 4、根据表达式树，求出表达式值，生成求值模块； 5、程序运行效果，测试数据分析算法。 六、测试数据 1、输入数据：*（+）3 正确结果： 2、输入数据：(1+2)*3+(5+6*7);
正确输出：56 七、表达式求值 由于表达式求值算法较为复杂，所以单独列出来加以分析： 1、主要思路：由于操作数是任意的实数，所以必须将原始的中缀表达式中的操作数、操作符以及括号分解出来，并以字符串的形式保存；然后再将其转换为后缀表达式的顺序，后缀表达式可以很容易地利用堆栈计算出表达式的值。 例如有如下的中缀表达式： a+b-c 转换成后缀表达式为： ab+c- 然后分别按从左到右放入栈中，如果碰到操作符就从栈中弹出两个操作数进行运算，最后再将运算结果放入栈中，依次进行直到表达式结束。如上述的后缀表达式先将a 和b 放入栈中，然后碰到操作符“+”，则从栈中弹出a 和b 进行a+b 的运算，并将其结果d（假设为d）放入栈中，然后再将c 放入栈中，最后是操作符“-”，所以再弹出d和c 进行d-c 运算，并将其结果再次放入栈中，此时表达式结束，则栈中的元素值就是该表达式最后的运算结果。当然将原始的中缀表达式转换为后缀表达式比较关键，要同时考虑操作符的优先级以及对有括号的情况下的处理，相关内容会在算法具体实现中详细讨论。 2、求值过程 一、将原始的中缀表达式中的操作数、操作符以及括号按顺序分解出来，并以字符串的 形式保存。 二、将分解的中缀表达式转换为后缀表达式的形式，即调整各项字符串的顺序，并将括 号处理掉。 三、计算后缀表达式的值。 3、中缀表达式分解 DivideExpressionToItem()函数。分解出原始中缀表达式中的操作数、操作符以及括号，保存在队列中，以本实验中的数据为例，分解完成后队列中的保存顺序如下图所示：
算术表达式求值-数据结构实验报告
清华大学数据结构课程实验报告（20 -20 学年第学期） 报告题目：算术表达式求值 任课老师： 专业： 学号： 姓名： 二0一年月日
摘要：现代科学技术高速发展，各种高科技产品频频问世，而各种技术的基础都离不开基本的表达式求值，它虽然简单，但却是任何复杂系统的基本执行操作。栈是一种重要的线性结构，从数据结构的角度看，它是一种特殊的线性表，具有先入先出的特点。而算符优先法的设计恰巧符合先入先出的思想。故我们基于栈这种数据结构，利用算符优先法，来实现简单算术表达式的求值。 关键字：算符优先法；算术表达式；数据结构；栈 一、课题概述 1、问题描述 一个算术表达式是由运算数、运算符、界限符组成。假设操作数是正整数，运算符只含有加“+”、减“-”、乘“*”、除“/”四种二元运算符，界限符有左括号“（”、右括号“）”和表达式起始、结束符“#”。利用算符优先法对算术表达式求值。 2、设计目的 （1）通过该算法的设计思想，熟悉栈的特点和应用方法； （2）通过对算符优先法对算术表达式求值的算法执行过程的演示，理解在执行相应栈的操作时的变化过程。 （3）通过程序设计，进一步熟悉栈的基本运算函数； （4）通过自己动手实现算法，加强从伪码算法到C语言程序的实现能力。3、基本要求： （1）使用栈的顺序存储表示方式； （2）使用算符优先法； （3）用C语言实现； （4）从键盘输入一个符合要求的算术表达式，输出正确的结果。 4、编程实现平台 Microsoft Visual C++ 6.0 二、设计思路及采取方案 1、设计思路： 为了实现算符优先法，可以使用两个工作栈。一个称做OPTR，用以寄存运
算术表达式与二叉树课程设计
山西大学 课程设计任务书 设计题目算术表达式与二叉树 所属课程：数据结构 系别软件学院 专业软件工程 班级软工1408班 姓名霍志斌 指导教师李雪梅 设计任务下达日期 2015年 12 月15 日 设计时间2016年1月4日至 2016年1月8日
目录： 一、需求分析 二、概要设计 1、数据类型的声明： 2、表达式的抽象数据类型定义 3、整体设计 三、详细设计 1、二叉树的存储类型 2、顺序栈的存储类型 3、表达式的基本操作 4、主程序和其他伪码算法 5、函数的调用关系 四、设计和调试分析 五、测试 六、课程设计的心得和心得以及问题 一、需求分析【课程设计要求】 【问题的描述】 一个表达式和一棵二叉树之间，存在着自然的对应关系。写一个程序，实现基于二叉树表示的算术表达式Expression的操作。 【基本要求】 假设算术表达式Expression内可以含有变量（a-z）,常量（0-9）和二元运算符（+，-，*，/，^（乘幂））。实现以下操作： （1）ReadExpr(E)――以字符序列的形式输入语法正确的前缀表达式并构造表达式E。 （2）WriteExpr(E)――用带括号的中缀表达式输出表达式E。
（3）Assign(V，c)――实现对变量V的赋值（V=c），变量的初值为0。 （4）Value(E)――对算术表达式E求值。 （5）CompoundExpr(p,E1,E2)――构造一个新的复合表达式（E1）p（E2）。【测试数据】 1)分别输入0；a;-91;+a*bc;+*5x2*8x;+++*3^*2^x2x6并输出。 2)每当输入一个表达式后，对其中的变量赋值，然后对表达式求值。 二、概要设计 1、数据类型的声明： 在这个课程设计中，采用了链表二叉树的存储结构，以及两个顺序栈的辅助存储结构 /*头文件以及存储结构*/ #include
相关文档
- 数据结构课程设计表达式求值【完整版】
- 数据结构表达式求值(可以求小数与多位数)
- 数据结构算术表达式求值实验报告
- 数据结构课程设计_表达式求值完整版
- 数据结构课程设计算术表达式求值计算器.doc
- 数据结构实验报告_表达式求值
- 表达式求值课程设计(数据结构C语言版)
- 数据结构表达式求值完整篇(含实验报告)
- 数据结构表达式求值代码
- 长沙理工大学数据结构栈的实现及应用算术表达式求值实验报告
- 数据结构算术表达式求值实验报告
- 长沙理工大学数据结构栈的实现及应用算术表达式求值实验报告
- 数据结构算术表达式求值实验报告
- 数据结构实验二——算术表达式求值实验报告
- 数据结构算术表达式求值实验报告
- 数据结构课程设计表达式求值问题
- 数据结构表达式求值完整篇(含实验报告)
- 实用数据结构基础（第二版）实验7：标识符树与表达式求值
- 数据结构表达式求值实验报告
- 表达式求值(数据结构)