《数据结构与算法设计》
实验报告
——实验二
学院：
班级： 学号： 姓名：
一、实验目的
1. 通过实验实践、巩固栈的相关操作； 2. 熟悉VC环境，加强编程、调试的练习； 3. 用C语言实现栈的抽象数据类型，实现栈的建立、进栈、出栈、取数据等基本操作； 4. 用C语言实现判断运算符优先级、表达式求值等基本操作；
5. 理论知识与实际问题相结合，利用上述基本操作实现简单计算器。
二、实验内容
1、简单计算器。
请按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。要求：
① 从键盘输入一个完整的表达式，以回车作为表达式输入结束的标志。 ② 输入表达式中的数值均为大于等于零的整数。中间的计算过程如果出现小数也只取整。
例如，输入：4+2*5=
输出：14 输出：-48
输入：(4+2)*(2-10)=
三、程序设计 1、概要设计
为实现上述程序功能，应用栈存储运算符和操作数，为此需要建立一个抽象数据类型：栈。
（1）、栈的抽象数据类型定义为： ADT Stack{
数据对象：D={ai|ai∈ElemSet,i=1,2,3……,n,n≥0} 数据关系：R1={
操作结果：创建一个空栈S。 Push(&S, e)
初始条件：栈S已存在
操作结果：插入运算符e作为新的栈顶元素 GetTop(&S)
初始条件：栈S已存在且非空
操作结果：用e返回寄存运算符栈S的栈顶元素 Pop(&S,&e)
初始条件：栈S已存在且非空
操作结果：删除寄存运算符栈S的栈顶元素 Operate(a,theta,b)
初始条件：a，b为整数，theta为运算符 操作结果：返回a与b运算的结果 Precede(d,c)
初始条件：d，c为运算符
操作结果：若d优先级大于c,返回‘>’；若d优先级小于c,返回‘<’；若d优先
级等于c,返回‘=’；
EvaluateExpression()
初始条件：输入合法的表达式 操作结果：返回表达式的值 }ADT Stack
⑵主程序流程
调用EvaluateExpression()函数计算表达式的值，并将结果输出在屏幕上。 ⑶各函数模块的调用关系
先由主函数调用计算求值函数；
再由求值模块调用栈构造函数，构造两个栈分别用来保存操作数和运算符，然后根据情况多次调用进栈、出栈、取栈顶元素、判断运算符优先级、计算表达式的值等多个函数，计算并返回表达式的值；
最后由主函数在屏幕上输出表达式的结果。 ⑷流程图