目 录
1概述............................................................................................................................. 1
1.1问题描述.......................................................................................................... 1 1.2算术表达式的构成.......................................................................................... 1 1.3表达式求值的规则.......................................................................................... 1 2需求分析..................................................................................................................... 1
2.1输入的形式和输入值的范围.......................................................................... 1 2.2程序所能达到的功能...................................................................................... 2 3.系统分析.................................................................................................................... 2 4概要设计..................................................................................................................... 2
4.1数据结构及算法思想...................................................................................... 2 4.2堆栈的抽象数据类型定义.............................................................................. 2 4.3算法分析.......................................................................................................... 3
4.3.1系统流程图........................................................................................... 3 4.3.2运算符优先关系模块........................................................................... 4 4.3.3主程序模块........................................................................................... 4 4.3.4堆栈模块............................................................................................... 4 4.4主程序的模块调用.......................................................................................... 5 4.5主要实现的功能函数...................................................................................... 6
4.5.1包含的主要函数功能所具有的功能................................................... 6 4.5.2数据结构设计....................................................................................... 6
5详细设计..................................................................................................................... 6
5.1功能模块详细设计.......................................................................................... 6
5.1.1详细设计思想....................................................................................... 6 5.2中缀表达式转换成后缀表达式...................................................................... 7 5.3后缀表达式求值.............................................................................................. 7 6运行与测试................................................................................................................. 7
测试结果................................................................................................................. 7 7总结和心得................................................................................................................. 8 参考文献........................................................................................................................ 8 8.附：源代码................................................................................................................ 9
1概述
1.1问题描述
编写一个表达式求值程序，使输入一个四则运算表达式后，能够返回正确的结果。该表达式由数字0~9、+、-、*、/、括号组成，且表达式必须正确无误。程序的编写可用到栈或队列的基本算法，求出该表达式的值，并分析算法的时间复杂度和运算的结果。首先要了解算术四则运算的规则,表达式求值是程序设计语言编译中的一个最基本问题。它的实现是栈应用的又一个典型例子。
1.2算术表达式的构成
一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。我们称它们为单词。一般地，操作数既可以是常数也可以是被说明为变量或常量的标识符；运算符可以分为算术运算符、关系运算符和逻辑运算符3类；基本界限符有左右括号和表达式结束符等。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。
1.3表达式求值的规则
1.3.1先乘除，后加减； 1.3.2从左算到右； 1.3.3先括号内，后括号外。
2需求分析
2.1输入的形式和输入值的范围
根据题目要求与提示，在输入一个中缀表达式，输入数的范围为int型，此时，程序将计算出表达式的结果。
2.2输出的形式
1
当按照程序要求选择了,再输入表达式程序将自动运算出表达式结果；中缀表达式转化为后缀表达式并计算出结果。
2.2程序所能达到的功能
本程序能计算出含+、-、*、/、（、）等运算符的简单运算。
3.系统分析
(1) 构造一个空栈S,初始条件：栈S已存在
(2) 用P返回S的栈顶元素
(3) 插入元素ch为新的栈顶元素 (4) 删除S的栈顶元素
(5) 判断字符是否是运算符，运算符即返回1 (6) 判断运算符优先权，返回优先权高的 (7) 输入表达式
(8) 返回表达式的最终结果
4概要设计
4.1数据结构及算法思想
表达式计算是实现程序设计逻辑语言的基本问题之一，也是栈和队列应
用的一个典型的例子。该设计是先通过栈将中缀表达式转换为后缀表达式，在转换过程中又用到了队列的操作。而在得到后缀表达式之后，又用到队列的操作对生成的后缀表达式进行计算。在整个设计的实现过程中，用到的都是栈和队列的概念。
4.2堆栈的抽象数据类型定义
ADT Stack｛
数据对象:D={ai|ai∈正整数，i=0，1，2，3，…n,及｛+-*/()｝} 数据关系：R1={|ai-1,ai∈D} 基本操作： InitStack（&S）
2
操作结果：构造一个空的堆栈S Push（&S, e）
初始条件：存在堆栈S
操作结果:元素e压入堆栈S，top+1 Pop（&S，e）
初始条件：栈S已经存在且非空
操作结果：删除栈顶元素e，输出其值，top-1
4.3算法分析
4.3.1系统流程图
输入一个表达式和’#’入栈 当输入符号时 是 是数字吗？ 否 是 栈顶运算符优先级低于输入符号吗？ 否 栈顶运算符优先级等于输入符号吗？ 是 栈顶是“（”且输入符号为“）” 是 否 栈顶运算符优先级高于输入符号吗？ 否 输出栈顶运算符 出错 将符号入栈 对数字进行处理 栈顶运算符出栈 程序结束 是 图4.3.1系统流程图
3
4.3.2运算符优先关系模块
int Priority(DataType op) //求运算符优先级 {
switch(op) {
case '(':
case '#': return(0); case '-':
case '+': return (1); case '*':
case '/': return (2); }
return -1; }
4.3.3主程序模块
void main( ) {
SeqQueue *Q;
SeqQueue PostQ; //定义队列，存放后缀表达式 Q=&PostQ;
InitQueue(Q); //初始化队列
CTPostExp(Q); //调用转换函数将中缀表达式转换成后缀表达式while(!QueueEmpty(Q)) //输出后缀表达式 printf(\printf(\Q->front=0;
printf(\ }
4.3.4堆栈模块
为了实现上述操作，应以栈为存储结构。 基本操作：
（1）. int GetTop(SqStack *S)
初始条件：栈存在；
4