数据结构课设报告-算术表达式求值.docxVIP

课程设计 报告 数据结构 数据结构 课程名称： 算术表达式求值 算术表达式求值 题目名称： 学生姓名： 学号： 课程成绩： 二零一六 年 六 月 需求分析 本演示程序用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