表达式求值课程设计报告.pdf

录

1需求分析1

问题描述..1

1.2基本要求1

2概要设计1

2.1数据结构1

2.2各模块间的调用关系及算法设计2

2.2.1栈的抽象数据类型的定义……………………3

2.2.2栈的基本功能…………………….4

3详细设计6

3.1数据存储结构设计6

3.2主函数和其它函数的设计与实现6

3.3函数功能分析8

3.4函数间的调用关系9

4调试与分析9

4.1程序调试9

4.2数据分析12

5用户手册13

5.1运行环境13

5.2执行文件13

6参考文献13

心得体会13

8小组成员任务分配及工作进度安排14

需求分析

1.1问题描述

不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因

而在程序设计时，借助栈实现。

算法输入：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）

操作符为+、-*、/，用#表示结束。

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

算法要点：设置运算符栈和运算数栈辅助分析算符优先关系。在读入表达式的字符

序列的同时，完成运算符和运算数的识别处理，以及相应运算。

本算法的时间复杂度与输入的表达式的长度有密切的关系，在此不作深入分析。

1.2基本要求

设计友好的用户界面，利用所学工具开发一个简单的表达式求值应用程序，该程序

能够对表达式进行加、减、乘、除运算，表达式中的操作数要求在实数范围内；对于异

常表达式应能给出错误提示。针对前面的要求分别设计合理的测试数据，比如

3.154*(12+18)-23的结果应该是71.62等。

2概要设计

2.1数据结构

表达式求值是程序设计语言编译中的一个最基本的问题。它的实现是栈应用的一个

典型例子。本程序使用通常使用的算法为“算符优先法”。

要把一个表达式翻译成正确求值的一个机器指令序列，或者直接对求值首先要能

够正确解释表达式。例如，要对下面的算术表达式求值：

4+2*3-10/5

首先要了解算术四则运算的规则。即：

（1）先乘除，后加减；

2）从左算到右；

（3）先括号内，后括号外；

由此，这个算术表达式的计算顺序应为

4+2*3-10/5=4+6-10/5=10-10/5=10-2=8

算符优先法就是根据这个运算优先关系的规定来实现对表达式的编译或解释执行的。

任何一个表达式都是由操作数（operand）、运算符（operator）、和界限符（delimiter）、

组成的，我们称它们为单词。一般地操作数即可以是常数也可以是被说明为变量或常量

的标识符；运算符可以分为算术运算符、关心运算数和逻辑运算符三类；基本界限符有

左右括号和表达式结束等。这里我们仅讨论算数表达式的求值问题。这种表达式只含有

加、减、乘、除四种运算符。

我们把运算符和界限符统称为算符，他们构成的集合命名为OP。根据上述三条运

算规则，在运算的每一步中，任意两个相继出现的算符θ和θ之间的优先关系至多是

12

下面三种关系之一；

θθθ的优先权低于θ

1212

θ=θθ的优先权等于θ

121