数据结构(C语言版)课程设计报告表达式求值

安徽理工大学

数据结构 课程设计说明书

题目: 表达式求值

院 系： 计算机科学与工程学院 专业班级： 计算机12-1班 学 号： 2012303038 学生姓名： 丰 继 强 指导教师： 刘 文 娟

2013年 12 月 25 日

安徽理工大学课程设计（论文）任务书

计算机科学与工程 学院

2013年 11 月 21 日

安徽理工大学课程设计（论文）成绩评定表

目 录

1 需求分析 ............................................... I 2 概要设计 ............................................... I 2.1 设计思路 .......................................... I 2.2 存储结构设计 ..................................... II 2.3 功能模块设计 ..................................... II 3 详细设计 .............................................. IV 4 运行与测试 ............................................ XI 5总结 ................................................. XII 参考文献 .............................................. XIII

(要求：给出一级目录和二级目录，宋体，四号字,1.5倍行距，页码使用罗马数字，居中)

（报告正文部分）：

(要求：正文部分一律用小四号字，宋体，行距20磅。一级标题靠左，加粗。二级大标题靠左，不加粗。正文页码单独开始用阿拉伯数字编码，居中)

1 需求分析

1、程序所能达到的功能：能够处理以字符序列的形式输入的不含变量的实数表达式，正确处理小数，判断表达式是还语法正确，正确实现对算术四则混合运算表达式的求值。

2、输入的形式和输入值的范围：以字符串的形式输入表达式，以“#”结束。 3、输出的形式：在计算过程中遇到的问题或最终的答案将显示在屏幕上。 4、测试数据：输入“3*(7-2)#”时，输出“15.000000”，测试正确；输入“!(9-2)#”时，输出“输入错误!”，测试正确。

2 概要设计

2.1 设计思路

为了实现算符优先算法，可以使用两个工作栈。一个称为OPTR，用以寄存运算符，另一个称作OPND，用以寄存操作数或运算结果。算法的基本思想是： （1）首先置非运算符栈为空栈，表达式起始符“#” 为运算符栈的栈底元素； （2）依次读入表达式中每个字符，若是非运算符则进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权后做相应的操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为“#”）。

算法中还调用了两个函数，其中Precede是判定运算符栈顶运算符a与读入的运

算符b之间优先关系的函数；Operate为进行二元运算a theta b的函数，如果是编译表达式，则产生这个运算的一组相应指令并返回存放结果的中间变量名；如果是解释执行表达式，则直接进行该运算，并返回运算结果。

2.2 存储结构设计

因为表达式是由操作符，运算符和界限符组成的。所以需要两个栈，一个char类型栈用来寄存运算符，一个int类型的栈用来寄存非运算符。 //定义结点元素结构（用于存放运算符） typedef struct charstack {

char *base; char *top;

int stacksize; }SqStackchar;

//定义结点元素结构（用于存放非运算符） typedef struct intstack {

float *base; float *top; int stacksize;

}SqStackint; 2.3 功能模块设计 1.栈的基本功能：

(1) InitStackchar(Stackchar &S)：构造运算符栈 (2) InitStackint(Stackint &S)：构造非运算符栈

(3) Pushchar(SqStackchar &S，char e)：运算符栈插入元素e为新的栈顶元素 (4) Pushint(SqStackint &S，float e)：非运算符栈插入元素e为新的栈顶元素 (5) Popchar(SqStackchar &S，char &e)： 删除运算符栈S的栈顶元素，用e返回其值

(6) Popint(SqStackint &S，float &e)：删除非运算符栈S的栈顶元素，用e返回其值

(7) GetTopchar(SqStackchar S)：用e返回运算符栈S的栈顶元素 (8) float GetTopint(SqStackint S): 用e返回操作数栈S的栈顶元素

2.其它功能分析：

(1) Xiaoshu(char c)用于计算小数。

(2) Precede(char a，char b) 判断运算符优先权功能，算符间的优先关系见表1：

表1 算符间的优先关系

(3) Operate(float a，char theta，float b) 操作数用对应的运算符进行运算功能，运算结果直接返回。

3 详细设计(程序源代码) #include<stdio.h> #include<stdlib.h>

#define MAXSIZE 100 //存储空间初始分配量

#define STACKINCREMENT 10 //存储空间分配增量

typedef struct charstack {

char *base; //在栈构造之前，base的值为NULL

char *top; //栈顶指针

int stacksize; //当前已分配的存储空间，以元素为单位

}SqStackchar; //定义结点元素结构（用于存放运算符）

typedef struct intstack {

float *base; //在栈构造之前，base的值为NULL

float *top; //栈顶指针

int stacksize; //当前已分配的存储空间，以元素为单位

}SqStackint; //定义结点元素结构（用于存放非运算符）

int InitStackchar(SqStackchar &S){

//构造一个空栈（用于存放非运算符） S.base=(char *)malloc(MAXSIZE * sizeof(char)); if(!S.base)

return 0; //存储分配失败

S.top=S.base; //空栈

S.stacksize=MAXSIZE; return 1; }

int InitStackint(SqStackint &S){

//构造一个空栈（用于存放运算符 …… 此处隐藏：4563字，全部文档内容请下载后查看。喜欢就下载吧 ……