数据结构课设报告-算术表达式求值.docx
文本预览下载声明
课程设计
报告
数据结构
数据结构
课程名称：
算术表达式求值
算术表达式求值
题目名称：
学生姓名： 学号：
课程成绩：
二零一六 年 六 月
需求分析
本演示程序用C++6.0编写，完成栈的生成。
输入的形式和输入值的范围：输入合法表达式，以“#”结尾；输入的操作数是正整数，运算符只含加减乘除四种运算符。
（2）输出的形式：显示输入是否正确、输入序列和栈的变化过程、计算结果。
（3）程序所能达到的功能：完成算术表达式的计算。
（4）测试数据：
①输入3*（2+4）#；
②输入5*－2#。
概要设计
为了实现上述程序功能，需要定义栈的抽象数据类型：
ADT SqStack{
数据对象：D={ai| ai ∈ElemSet,i=1,2,3……，n,n≥0}
数据关系：R1={ai-1,ai| ai-1,ai ∈D,i=1,2,3,……，n}
基本操作：
InitStack(SqStack S)
操作结果：声明栈建立函数
Push(SqStack S,char e)
初始条件：栈已经存在
操作结果：声明入栈函数
Pop(SqStack S)
初始条件：栈已经存在
操作结果：声明出栈函数
DispStack(SqStack S)
初始条件：栈已经存在
操作结果：从栈底到栈顶依次输出各元素
本程序包括5个函数：
①主函数main（）
②确定如何入栈函数evaluate( )
③声明取栈顶元素函数GetTop( )
④声明比较函数Compare( )
⑤声明运算函数Operate( )
各函数间关系如下：
InitStack
main push
evaluate DispStack
Compare
Pop
GetTop
Operate
详细设计
实现概要设计中定义的所有的数据类型，对每个操作给出伪码算法。对主程序和其他模块也都需要写出伪码算法。
（1）栈和指针类型
typedef struct //运算符栈
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack1;
typedef struct //运算数栈
{
SElemType2 *base;
SElemType2 *top;
int stacksize;
}SqStack2;
（2）栈的基本操作
void InitStack1(SqStack1 S1)//构造一个空栈S1
{
S1.base=new SElemType[STACK_INIT_SIZE];
if(!S1.base)cout存储分配失败！;//存储分配失败
S1.top=S1.base;
S1.stacksize=STACK_INIT_SIZE;
}
void InitStack2(SqStack2 S2)//构造一个空栈S2
{
S2.base=new SElemType2[STACK_INIT_SIZE];
if(!S2.base)cout存储分配失败！;//存储分配失败
S2.top=S2.base;
S2.stacksize=STACK_INIT_SIZE;
}
void Push1(SqStack1 S1,char e)//入栈
{
if(S1.top-S1.base=S1.stacksize)//如果栈满，追加存储空间
{
S1.base=(char *)realloc(S1.base,(S1.stacksize+STACKINCREMENT)*sizeof(char));
if(!S1.base) cout存储分配失败！;
else
{
S1.top=S1.base+S1.stacksize;
S1.stacksize=S1.stacksize+STACKINCREMENT;
}
}
*S1.top=e;S1.top=S1.top+1;//将元素压入栈中，指针上移
}
void Push2(SqStack2 S2,float e)//入栈
{
if(S2.top-S2.base=S2.stacksize)//栈满，追加存储空间
{
S2.base=(float *)realloc(S2.base,(S2.stacksize+STACKINCREMENT)*sizeof(float));
if(!S2.base)cou
显示全部