《数据结构》

课 程 设 计 报 告 书

题    目：      表达式求值       

系    别：   计算机科学与信息系  

学    号：           

学生姓名：               

指导教师：

完成日期：               

目录

Ø 1.前     言

Ø 2.概要设计

2.1 数据结构设计

2.2  算法设计

2.3  ADT描述

2.4  功能模块分析

Ø 3.详细设计

3.1 数据存储结构设计

3.2主要算法流程图（或算法代码）

Ø 4.软件测试

Ø 5.总结

Ø 附    录

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)

初始条件：栈存在；

操作结果：置栈为空。

…… …… 余下全文

问题描述：

四则运算表达式求值，将四则运算表达式用中缀表达式，然后转换为后缀表达式，并计算结果。

一、       需求分析：

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

2、输入输出格式：

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

请输入表达式：

输入一个中缀表达式

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

逆波兰表达式为：

                      输出逆波兰表达式

          运算结果为：输出运算后的结果

3、测试用例

输入：21+23*（12-6）

输出：21 23 12 6 -*+

二、概要设计 ：

     抽象数据类型

    二叉树类BiTree

    算法的基本思想

根据题目要求，利用栈计算，和二叉树存储，来计算表达式

该算法的基本思想是：

先利用栈进行计算，然后用二叉树进行存储，和实验三算法一样来计算逆波兰表达式的值

程序的流程

    程序由三个模块组成：

     （1）  输入模块：输入一个运算式

…… …… 余下全文

清华大学数据结构课程实验报告

（20  -20  学年 第  学期）

报告题目：  算术表达式求值 

任课老师：                  

专　　业：                 

学　　号：                 

姓　　名：                  

二0一   年  月  日

摘要：现代科学技术高速发展，各种高科技产品频频问世，而各种技术的基础都离不开基本的表达式求值，它虽然简单，但却是任何复杂系统的基本执行操作。栈是一种重要的线性结构，从数据结构的角度看，它是一种特殊的线性表，具有先入先出的特点。而算符优先法的设计恰巧符合先入先出的思想。故我们基于栈这种数据结构，利用算符优先法，来实现简单算术表达式的求值。

关键字：算符优先法；算术表达式；数据结构；栈

一、课题概述

1、问题描述

一个算术表达式是由运算数、运算符、界限符组成。假设操作数是正整数，运算符只含有加“+”、减“-”、乘“*”、除“/”四种二元运算符，界限符有左括号“（”、右括号“）”和表达式起始、结束符“#”。利用算符优先法对算术表达式求值。

…… …… 余下全文

西   南   大   学

 数据结构实验报告

        学院：

    专业：   

班级：

    姓名：

    学号：

       

实验报告

…… …… 余下全文

数据结构课程实验指导书

一：问题描述

本程序要求用户输入一个中缀表达式，然后转换为后缀表达式，并计算结果。然后将中缀表达式用栈的方式存储，将这些符号的将中缀表达式中的符号赋给树的

二、概要设计

数据对象 字符数组

基本操作

stack<char> OptrStack; /* 操作符栈 */

stack<treeNode*> ExprStack; /* 表达式栈 */

typedef struct nodeTag /* 表达式二叉树结点类型 */

Char Precede(char opf, char opg) //比较栈顶运算符与下一输入运算符优先关系

treeNode* mkleaf(int num) //建立二叉树数结点(叶结点)

treeNode* mknode(char op, treeNode* left,treeNode* right) // 建立二叉树运算符结点(内结点)

treeNode* CreateBinaryTree() //建立表达式二叉树

int PreOrderTraverse(treeNode* T) //输出前缀表达式

int FollowOrderTraverse(treeNode* T) //输出后缀表达式

算法的基本思想

1）以二叉链表的存储结构创建一棵。

2）后根遍历为：此中缀表达式的后缀表达式

设str1= a+b)*((c+d)*e+f*h*g)，str2 是目的串。先用一个堆

－ 1 －

数据结构课程实验指导书

栈存储operator（首先设置表达式起始符‘#’为运算符栈的栈底元素），遇到数字就不做处理直接放到目的串中，遇到operaor则将其与堆栈顶元素比较优先级，决定是否送到输出串中，直至整个表达式遍历完毕（即运算符栈的栈顶元素和当前读入的字符均为'#'）这样处理之后能得到一个后续的排列，再建立二叉树。

…… …… 余下全文

中缀表达式求值实验报告

一、需求分析（要实现的功能描述）

1．问题描述：

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

2．实现功能：

算法输入：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为简化，规定操作数只能为正整数，操作符为“+、-、*、/”。

算法运行：将输入的中缀表达式改为后缀表达式，并进行运算。

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

3．测试数据：

（1）、1+3*4-（5/5）；         一位数运算

（2）、45-5*（1+2）/5;         多位数运算

二、概要设计

整个程序包含功能模块及模块间的调用关系

(1)、struct node                      创建结构体，被主函数调用

(2)、struct node *Initialization()         创建栈链，被主函数调用

(3)、struct node *assort(struct node *s)    将中缀表达式转换为后缀表达式并存在s2中被主函数调用

(4)、struct node *calcolate(struct node *s)  求出表达式的值，被主函数调用

…… …… 余下全文