栈的应用实验报告

栈的应用实验报告

实验目的：1.学习栈的特性和基本算法。

2.学习利用数据结构解决实际问题的方法。

问题描述：设计一个合法的算术表达式，（含四则运算，小括号和正的浮点数）的值。

实验内容：

1.栈的抽象数据类型定义：

typedef struct SqStack{int * base;int * top;int size;}SqStack; 基本操作：

InitSqStack(SqStack &t)：建立一个工作栈。

clearstack(SqStack &t)：清空工作栈。

push(SqStack &t, int n)：向栈中添加一个元素。

out(SqStack &t)：使栈顶元素出栈。

Empty( SqStack &t)：检验栈是否为空，返回值为栈内元素个数。 GetTop(SqStack &t)：返回栈顶元素。

Precede(char c,char d)：比较运算符优先级。

读取时从第一个字符开始，以‘=’结束，必须输入等号否则执行错误，无法求出表达式值。

算法的时间复杂度：设表达式字符数为n，基本操作的运算次数均为O(1),而每读取一个字符，若为数字，操作数为4，若为加减乘除，调用Precede(char c,char d)，操作数也为O(1),若为其他字符，则显示结果出错。故在不考虑表达式中含有非表达式值时，时间复杂度为O(n)。

实验结果：

输入表达式23+（-5）*（2+3）=得到结果为2，正确。

输入表达式23+(-5)*）2+3（=得到结果为ERROR，并显示请重新输入表达式。正确。