数据结构表达式求值课程设计

. . . .

数据结构课程设计

设计说明书

算术表达式求值问题

学生姓名白子健

学号1318014057

班级计本1302

成绩

指导教师李军

计算机科学与技术系

2015年9月10日

. 资料. .. .

. . . .

数据结构课程设计评阅书

. 资料. .. .

. . . .

课程设计任务书

2015—2016学年第一学期

专业：计算机科学与技术学号：1318014057 姓名：白子健

课程设计名称：课程设计Ⅰ---数据结构课程设计

设计题目：表达式求值算法的实现

完成期限：自2015 年9 月 1 日至2015 年9 月12 日共2 周

设计内容及要求:

算术表达式求值是程序设计语言编译中的一个基本问题，通过栈实现表达式运算优先级的匹配和运算。用C/C++语言编程实现任意算术表达式的求值，设计内容要求如下：（1）表达式共有三种基本表示方法：前缀法、中缀法、后缀法。从表达式的这三种基本方法中任选一种方法进行编程求值。

（2）分析所选的表示方法，根据选定的表示方法确定对应的存储结构和相关算法。

（3）算法要能正确处理算术运算的优先级规则，即: 先括号内，后括号外的规则；运算先乘除，后加减；同级运算从左到右。

如下表达式：

50+（6*3+2）

要求：

(1)用C/C++语言编写一个程序将

合肥学院

计算机科学与技术系

课程设计报告

2009～2010学年第二学期

课学学专指

业导

班教生

姓

程 数据结构与算法

算术表达式求值问题

杨松 0804012031 08计科(2) 王昆仑 张贯虹

名 号 级 师

课程设计名称

2010年6月

1

题目：（算术表达式求值问题）一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。要求：（1）从键盘读入一个合法的算术表达式，输出正确的结果。（2）显示输入序列和栈的变化过程。选作内容：操作数类型扩充到实数。

一、问题分析和任务定义

要对一个含有加减乘除四则运算的合法的算术表达式进行求值， ①首先，应了解算术表达式的四则运算的规则： (1)从左向右计算 (2)先乘除，后加减 (3)先括号内，后括号外

由此可知，比如算术表达式（7+15）*（23-28/4）的计算顺序，即为 （7+15）*（23-28/4）=22*（

数据结构课程设计报告

栈的应用：表达式求值的设计

专业 徐燕萍

学生姓名 班学

级 号

指导教师 完成日期

栈的应用：表达式求值的设计 目 录

1 设计内容…………………………………………………….1 2 设计分析

2.1 系统需求分析……………………………………………..1 2.1.1 系统目标………………………………………………...1 2.1.2 主体功能………………………………………………...1 2.2 系统概要设计……………………………………………..1 2.2.1 系统的功能模块划分………….………………………..1 2.2.2 系统流程图…………………………………...…………2 3 设计实践

3.1 基本分析…………………………………………………..3 3.2 中缀表达式求值…………………………………………..4 3.3 后缀表达式求值…………………………………………..5 3.4 中缀表达式转换成后缀表达式…………………………..6 4 测试方法

4.1 基本测试…………………………………………………..7 4.2 拓展测试…………………………………………………..7 4.3

课程设计 课程名称：题目名称：

学生姓名：

课程成绩：报告

数据结构

算术表达式求值

学号

：

二零一六 年六 月

1.需求分析

本演示程序用C++6.0编写，完成栈的生成。

（1）输入的形式和输入值的范围：输入合法表达式，以“#”结尾；输入的操作数是正整数，运算符只含加减乘除四种运算符。

（2）输出的形式：显示输入是否正确、输入序列和栈的变化过程、计算结果。

（3）程序所能达到的功能：完成算术表达式的计算。 （4）测试数据：

①输入3*（2+4）#； ②输入5*－2#。

2.概要设计

（1）为了实现上述程序功能，需要定义栈的抽象数据类型：

ADT SqStack{

数据对象：D={ai| ai ∈ElemSet,i=1,2,3??，n,n≥0} 数据关系：R1={| ai-1,ai ∈D,i=1,2,3,??，n} 基本操作：

InitStack(SqStack &S)

操作结果：声明栈建立函数 Push(SqStack &S,char e)

初始条件：栈已经存在 操作结果：声明入栈函数 Pop(SqStack &S)

初始条件：栈已经存在 操作结果：声明出栈函数 DispStack(SqStack &S)

初始条件：栈已经存在

操作结果

算法与数据结构课程设计任务书

（09级）

题目：表达式求解问题

学生姓名： XX 学号： 09780015 班级： 计算机网络 题目类型：软件工程（R） 指导教师： XXX

一． 题目简介

该设计要求学生设计程序，实现任意算术表达式的求解问题。通过该题目的设计过程，可以加深理解线性表及栈的逻辑结构、存储结构，掌握线性表及栈上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养学生的动手能力。

二．

主要任务

1、查阅文献资料，一般在3篇以上； 2、建立数据的逻辑结构和物理结构； 3、完成相应算法的设计； 4、完成测试工作； 5、撰写设计说明书； 6、做好答辩工作。

三． 主要内容、功能及技术指标

（1）使用顺序栈存储算术表达式，主要功能有：输入并建立算术表达式、输出算术表达式、算术表达式的计算及显示输出等；

（2）至少要用10个测试数据，算法对

算法与数据结构课程设计任务书

（09级）

题目：表达式求解问题

学生姓名： XX 学号： 09780015 班级： 计算机网络 题目类型：软件工程（R） 指导教师： XXX

一． 题目简介

该设计要求学生设计程序，实现任意算术表达式的求解问题。通过该题目的设计过程，可以加深理解线性表及栈的逻辑结构、存储结构，掌握线性表及栈上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养学生的动手能力。

二．

主要任务

1、查阅文献资料，一般在3篇以上； 2、建立数据的逻辑结构和物理结构； 3、完成相应算法的设计； 4、完成测试工作； 5、撰写设计说明书； 6、做好答辩工作。

三． 主要内容、功能及技术指标

（1）使用顺序栈存储算术表达式，主要功能有：输入并建立算术表达式、输出算术表达式、算术表达式的计算及显示输出等；

（2）至少要用10个测试数据，算法对

#include<stdio.h>
#define StackSize 100
#define QueueSize 100

typedef char DataType;
typedef struct {
char data[100];
int front,rear;
}SeqQueue;//队列的定义

typedef struct{
DataType data[100];
int top;
}SeqStack;//栈类型的定义

int DeQueue(SeqQueue * Q);
void InitQueue(SeqQueue * Q);
int QueueEmpty(SeqQueue * Q);
void EnQueue(SeqQueue * Q,DataType x);
void InitStack(SeqStack * S);
void Push(SeqStack * S,DataType x);
DataType Pop(SeqStack * S);
DataType GetTop(SeqStack * S);
int Priority(DataType op);
void CTPostExp(SeqQueue *Q);

void InitQueue(SeqQueu

#include<stdio.h>
#define StackSize 100
#define QueueSize 100

typedef char DataType;
typedef struct {
char data[100];
int front,rear;
}SeqQueue;//队列的定义

typedef struct{
DataType data[100];
int top;
}SeqStack;//栈类型的定义

int DeQueue(SeqQueue * Q);
void InitQueue(SeqQueue * Q);
int QueueEmpty(SeqQueue * Q);
void EnQueue(SeqQueue * Q,DataType x);
void InitStack(SeqStack * S);
void Push(SeqStack * S,DataType x);
DataType Pop(SeqStack * S);
DataType GetTop(SeqStack * S);
int Priority(DataType op);
void CTPostExp(SeqQueue *Q);

void InitQueue(SeqQueu

1、

实验目的和要求

（1）深入理解栈的特点及其描述方法。

（2）能够在两种存储结构上实现栈抽象数据类型实现。 （3）掌握栈的几个典型应用算法，能灵活应用栈解决实际问题。

2、 概要设计

【定义所有抽象数据类型、自定义函数间的调用关系图，自定义函数的功能描述和流程图，以及主程序的流程图。】

开始 定义运算符和操作数栈并初 始化 并fflush(stdin)清除缓存 输入每个字符并执行相应的条件语句入栈出栈 //比较OPTR的栈顶元素和ch的优先级 char Precede (SElemType_OPTR top, While(1) Y EvaluateExpression( ) //运算并将结果出栈 Operate 输出结果

3、 调试分析

【(1) 调试过程中遇到的问题是如何解决的以及对设计与实现中关键点的回顾讨论和分析；(2) 算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和改进设想；(3) 经验和体会等。】

1.栈的定义、初始化、出栈进栈、取栈顶元素等步骤不难就先把结构打好了 2.操作数和运算符分别入不同的栈 char->int 进操作数栈

先考虑了小于10的整数直接进栈,重点是运算符的优先级这块函数的编

《汇编语言程序设计》

综合程序设计实验报告

题 目：班 级：

姓 名： 学 号： 20112820

完成日期： 2013-11-24

一、项目简介

题目完成了对简单的加减乘除四则表达式的求值，同时能判断各种运算级括号的优先级，进行正确的运算顺序。

二、小组成员具体分工

韩亚华：完成判断优先级方法设计，以及细节的处理。

姜力比：完成输入输出函数的设计，以及各运算函数。

三、需求分析与设计

要完成四则运算表达式求值必须解决以下问题

1.如何在汇编环境下输入并保存操作数

2.如何保存运算符和比较运算符的优先级

3.如何输出计算结果

4.负数和括号的细节问题

四、代码及分析

DSEG SEGMENT

STR1 DB 0AH,0DH, 'please input the expression:("N"jump out)$'

SIGN1 DW 0 ;判断数字是否输入完毕

SIGN2 DW 0 ;判断括号是否配对

;SIGN3 DW 0 ;

NUMB DW 20H DUP(0) ;保存输入的数值

MARK DB 'A' ;保存输入的运算符

DB 10H DUP(0) ;

ERROR DB 'YOUR INPUT ARE WRON