长沙理工大学数据结构栈的实现及应用算术表达式求值实验报告

批 阅 实 验 报 告

年级 班号 学号 姓名

实验名称： 栈的实现及其应用：算术表达式的计算

实验日期 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^2 = 0 #include #include #include #include #include #include

typedef double Type; typedef struct {

Type TypeStack[MAX]; char charStack[MAX];

int TypeTop, charTop;

}Stack;

//初始化栈

void InitStack(Stack *S) { }

//判断charStack是否为空 bool IsEmpty_Char(Stack S) { }

//判断TypeStack是否为空 bool IsEmpty_Type(Stack S) { }

//判断charStack是否为满 bool IsFull_Char(Stack S) { }

return S.charTop == MAX; return S.TypeTop == 0; return S.charTop == 0; S->charTop = S->TypeTop = 0;