(完整)数据结构表达式求值实验报告 .pdf

(完整)数据结构表达式求值实验报告--第1页

(完整word版)数据结构表达式求值实验报告

《数据结构》

课程设计报告书

题目:表达式求值

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

学号：

学生姓名：

指导教师:

完成日期:

1

(完整)数据结构表达式求值实验报告--第1页

(完整)数据结构表达式求值实验报告--第2页

(完整word版)数据结构表达式求值实验报告

目录

➢1.前言

➢2.概要设计

2。1数据结构设计

2.2算法设计

2.3ADT描述

2。4功能模块分析

➢3。详细设计

3.1数据存储结构设计

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

➢4.软件测试

➢5。总结

➢附录

2

(完整)数据结构表达式求值实验报告--第2页

(完整)数据结构表达式求值实验报告--第3页

(完整word版)数据结构表达式求值实验报告

1．前言

在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要

考虑括号，因此，算术表达式的求值不可能严格地从左到右进行.因而在程序设计时，借助栈实现。

算法输入：一个算术表达式,由常量、变量、运算符和括号组成（以字符串形式输入）。为简化，规定操作数

只能为正整数，操作符为+、-*、/，用#表示结束。

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

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

和运算数的识别处理，以及相应运算。

2．概要设计

2.1数据结构设计

任何一个表达式都是由操作符,运算符和界限符组成的。我们分别用顺序栈来寄存表达式的操作数和运算

符.栈是限定于紧仅在表尾进行插入或删除操作的线性表。顺序栈的存储结构是利用一组连续的存储单元依次

存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置，base为栈底指针，在

顺序栈中，它始终指向栈底，即top=base可作为栈空的标记，每当插入新的栈顶元素时，指针top增1，

删除栈顶元素时,指针top减1。

3

(完整)数据结构表达式求值实验报告--第3页

(完整)数据结构表达式求值实验报告--第4页

(完整word版)数据结构表达式求值实验报告

2.2算法设计

为了实现算符优先算法。可以使用两个工作栈。一个称为OPTR，用以寄存运算符，另一个称做OPND，

用以寄存操作数或运算结果。

1。首先置操作数栈为空栈，表达式起始符”＃为运算符栈的栈底元素；

2.依次读入表达式，若是操作符即进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权后

作相应的操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为#)。

2.3ADT描述