算术表达式求值系统

数据结构课程设计报告

课设题目：班 级: 姓 名：学 号：指导教师: 成 绩:

算式表达式求值系统 软件1202 李斌

2013 年 1月

目录

一、需求分析.......................................2 二、概要设计.......................................2 (一）设计思想......................................2 (二）实现方法......................................2 (三）模块整体设计图................................3 (四）函数功能介绍..................................3 三、详细设计.......................................4 （一）数据结构设计.................................4 （二）模块接口设计.................................4 （三）盒图.........................................5 四、调试分析.......................................7 五、用户手册.......................................7 六、测试结果.......................................8 七、附录...........................................9 附录一 设计体会....................................9 附录二 源程序......................................9

一、 需求分析

算式表达式求值是程序设计语言编译中一个最基本的问题。本次任务要求完成一个四则算式表达式求值系统。具体需求为：当用户输入一个四则算式（包括加、减、乘、除和括号），如（12+3）*2+9*4，输出其计算结果。具体要求如下： （一） 要实现栈的基本操作算法，包括初始化栈、进栈、出栈等。

（二) 在本程序中，表达式中的元素限定为char型，表达式长度不超过100，表达式以“#”号为结束标志。

（三）要求程序输出表达式的计算结果。

二、 概要设计

（一）设计思想

本次四则算式表达式求值的程序采用的是中缀表达式的求值的方法。所谓中缀表达式，就是指每个二目运算符在两个运算量的中间，假设所讨论的算术运算符包括：+ 、- 、*、/、%、^（乘方）和括号（）。而本次程序的编写只涉及四则运算（+、-、*、/）和括号（）。 设运算规则为：

．运算符的优先级为：（）> *、/> +、- ；

．有括号出现时先算括号内的，后算括号外的，多层括号，由内向外进行；

表达式作为一个满足表达式语法规则的串存储，如表达式“3*2^（4+2*2-１*3）-5”,它的的求值过程为：自左向右扫描表达式，当扫描到3*2时不能马上计算，因为后面可能还有更高的运算，正确的处理过程是：需要两个栈：对象栈s1和算符栈s2。当自左至右扫描表达式的每一个字符时，若当前字符是运算对象，入对象栈，是运算符时，若这个运算符比栈顶运算符高则入栈，继续向后处理，若这个运算符比栈顶运算符低则从对象栈出栈两个运算量，从算符栈出栈一个运算符进行运算，并将其运算结果入对象栈，继续处理当前字符，直到遇到结束符“#”。

根据运算规则，左括号“（”在栈外时它的级别最高，而进栈后它的级别则最低了; 乘方运算的结合性是自右向左，所以，它的栈外级别高于栈内; 就是说有的运算符栈内栈外的级别是不同的。当遇到右括号“）”时，一直需要对运算符栈出栈，并且做相应的运算，直到遇到栈顶为左括号“(”时，将其出栈，因此右括号“）”级别最低但它是不入栈的。对象栈初始化为空。根据以上分析，每个运算符栈内、栈外的级别如下：

算符 栈内级别 栈外级别 ^ 3 4 *、/、% 2 2 +、- 1 1 ( 0 4 ） -1 -1 （二）实现方法

由于算符是字符类型，而表达式中的数字为数值类型，如果建立两个栈的结构的话，他们除了数据元素不同，其余操作都是类似的，这样不仅会增加程序的空间开销和执行时间，而且也使程序冗余度较大。我采用的解决方案是设置一个算符值x来表示算符，+、-、*、/、（、）的算符值依次为：1,2,3,4,5,6，用一个switch-case语句将算符转化为相应的数值，然后再入栈，这样就统一了对象栈和算符栈元素的数据类型。在将“（”出栈时，要避免将初值0数据多次入栈而导致出错，如2*（3-1）-1，正常情况下在遇到*时，就应该将数字2入对象栈，然后将保存算式中数值的变量a置零，但是当遇到“（”时，又要将数字0入栈，这样就会导致结果出错，所以在用户输入的数据入对象栈之前，应先判断是否为“（”，若为“(”,则不能将数据入对象栈；当遇到“）”时，“（”不能入栈，并且要将前面的“3”，“-”，“1”都依次出栈进行计算，在遇到“（”时，将“（”出栈，但接下来又会遇到“-”，因此又要将数字0入栈，这样也会导致结果出错因此，我用了一个z[Max]数组来存放“（”的算符值，在每次入对象栈之前，都需要判断在z[i-1]的值。

在解决了数据类型问题之后，程序的编写就显得容易多了。基本的操作包括栈的初始化、入栈、出栈、判空栈以及取栈顶元素，然后按照设计思路编写求四则表达式值的程序，此外还有一个界面程序，通过调用清屏函数system("cls")以及switch-case语句来实现界面的切换。 （三）模块整体设计图

（四）函数功能介绍

1.主函数void main()

功能：调用其他各个函数； 2.菜单函数 int menu()

功能：构造系统界面；

3.算式求值函数void suanshi() 功能：求解四则算式表达式之值

4.栈初始化函数SeqStack *Init_SeqStack() 功能：置空栈

5.入栈函数int Push_SeqStack (SeqStack *s, int x) 功能：将数据元素入栈

6.出栈函数int Pop_SeqStack(SeqStack *s, int *x) 功能：将数据元素出栈

7.取栈顶元素函数int Top_SeqStack(SeqStack *s) 功能：取出栈顶元素并将栈顶指针减一

8.判空栈函数int Empty_SeqStack(SeqStack *s) 功能：判断是否为空栈

三、 详细设计

（一）数据结构设计

1.本系统采用结构体来定义栈，其结构如下: typedef struct {

int data[Max]; int top; }SeqStack;

并且设置了两个栈s1,s2分别表示对象栈和算符栈。

2.定义了一个z[Max]数组用来存放出栈的“（”的算符值，以避免将数据初值0入栈而导致出错。 （二）模块接口设计： 1.各函数原型为：

void main() /*主函数*/ int menu() /*菜单函数*/

void suanshi() /*计算四则运算表达式*/ SeqStack *Init_SeqStack() /*栈初始化*/ int Push_SeqStack (SeqStack *s, int x) /*入栈*/ int Pop_SeqStack(SeqStack *s, int *x) /*出栈*/ int Top_SeqStack(SeqStack *s) /*取栈顶元素*/

int Empty_SeqStack(SeqStack *s) /*判断是否为空栈*/ 2.系统界面切换的实现

利用清屏函数system("cls")实现屏幕切换，在从本界面返回上一界面时，根据 …… 此处隐藏：7264字，全部文档内容请下载后查看。喜欢就下载吧 ……