实 验 报 告
年级 班号 学号 姓名
实验名称： 栈的实现及其应用： 算术 表达式的计算
实验日期 2016
年 12
月 2
日
实验报告撰写内容
一、实验环境
二、实验目的
三、实验内容
四、数据结构与算法思想描
述
五、程序清单
六、程序执行结果及其分析
批
阅
计算机科学与技术系
2016 年制
一、 实验环境
32 位操作系统下的 Window 平台 Microsoft Visual C++
二、 实验目的
掌握栈的实现及使用
三、 实验内容
1.实现栈的存储结构
2.实现栈的基本操作的有关算法
3.利用栈解决*算术表达式求值问题
四、 数据结构与算法思想描述
顺序读取中缀表达式：
1、 当遇到数字时，将数字入数字栈
2、 当遇到操作符时，与操作符栈栈顶比较：
If(当前操作符优先级大于操作符栈栈顶的优先级)
If(非”)”操作符)
将当前操作符进操作符栈;
Else
While(操作符栈栈顶不等于”(“)
取操作符栈栈顶及数字栈的两个数进行运算，并将结果压入数字栈;
Else
If(非(“操作符)
While(操作符栈栈顶不等于”(“)
取操作符栈栈顶及数字栈的两个数进行运算，并将结果压入数字栈;
Continue;(直到当前操作符比栈顶操作符优先级大)
Else
将当前操作符进操作符栈;
3、 While(操作符栈非空)
操作符栈栈顶及数字栈的两个数进行运算，并将结果压入数字栈;
4、 在数字栈取最后结果并输出。
五、 程序清单
//10*8^2+16.3+5*(5.2*5+3.01)/4-(-10)+0.1000060+4.00416-40 = 666.666666
//100+(-100)-(-10^2) = 100
//(((2016-2017+(((2015-2014)))))) = 0
//-1+(((((((((1^0))))))))+100%10^2 = 0
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iomanip>
#include<map>
using namespace std;
const int MAX = 105;
typedef double Type;
typedef struct
{
Type TypeStack[MAX];
char charStack[MAX];
int TypeTop, charTop;
}Stack;
//初始化栈
void InitStack(Stack *S)
{
S->charTop = S->TypeTop = 0;
}
//判断 charStack 是否为空
bool IsEmpty_Char(Stack S)
{
return S.charTop == 0;
}
//判断 TypeStack 是否为空
bool IsEmpty_Type(Stack S)
{
return S.TypeTop == 0;
}
//判断 charStack 是否为满
bool IsFull_Char(Stack S)
{
return S.charTop == MAX;
