“数据结构与算法”课程综合设计报告
题目：
表达式求值问题
学院
计算机科学技术学院
年级
2021 级
专业
物联网工程
学号
20214905
姓名
刘思彤
日期
2022 年 10 月 30 日
成绩
评语
黑龙江大学
计算机科学技术学院、软件学院
1.系统概述
1.1 开发系统的目的与意义
熟练掌握线性结构(线性表、栈、队列等）的存储方式，及在其上进行复杂
操作的方式。
1.2 概要介绍系统
表达式求值是程序设计语言编译中的一个最基本问题。人们在书写表达式式
时通常采用将运算符放在两个操作数中间的“中缀”表示形式，称为中缀表达式。
但是这种表达式形式对计算机处理来说是不适合的。在计算机领域，经常将算术
表达式表示成“后缀”表示形式，称为后缀表达式。如：中缀表达式 3+2*7-(7-5)
对应的后缀表达式为 3275-*+。
表达式是由操作数、运算符、界限符组成的。操作数既可以是常数，也可以
是说明为变量或常量的标识符；运算符可以分为算术运算符、关系运算符和逻辑
运算符 3 类；基本界限符有左右括号和表达式结束符等。
2.系统需求分析
（1）要求以字符序列的形式从终端输入或从文件输入语法正确的、不含变
量的整数或小数表达式，并根据输入表达式实现：①算数四则运算中缀表达式
到后缀 表达式的转换；②后缀表达式的求值；③中缀表达式的求值。要求演示
在求值过程中运算符栈、操作数栈、输入字符和主要操作过程及运算结果。在本
题目中可将表达式中的操作数规定为 1 位数字字符。也可根据个人的能力对这部
分功能进行扩充，使得操作数可以是多位数甚至是小数。
算法应该能够过滤掉输入符号之间的空格。也可对本算法功能进行扩充，使
其具有对对输入表达式进行语法检查的功能。为了简化问题，运算符可只包含+、
-、*、/四种基本运算，括号只有圆括号。可根据需要及个人能力对算法的功能
进行扩充，允许有其它运算符。
本项目可使用控制台界面或可视化图形界面，若使用可视化图形界面有加分。要
求配备菜单，至少含如下选项：
表达式求值
1. 中缀表达式到后缀表达式的转换
2. 后缀表达式的计算
3. 中缀表达式的计算
4. 退出
（2）要求输入表达式采用字符串存储，操作数和运算符采用栈存储，待输
出的表达式用队列存储。
3.系统概要设计
3.1 数据结构设计
输入表达式采用字符串存储，操作数和运算符采用栈存储，待输出的表达式用队
列存储。
顺序栈结构体：
typedef struct
{
char* base;
char* top;
int stacksize;
}sqstack;
队列结构体：
typedef struct
{
QueuePtr front, rear;
}LinkQueue;
3.2 软件结构设计
表达式求值系统根据需求分析中的功能分析，可以提炼出主要中缀表达式到
后缀表达式的转换、后缀表达式的计算、中缀表达式的计算三个模块。后缀表达
式的计算可以计算上次输入的表达式、键盘输入表达式。系统软件结构如图 1
