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

课程设计 课程名称：题目名称：

学生姓名：

课程成绩：报告

数据结构

算术表达式求值

学号

：

二零一六 年六 月

1.需求分析

本演示程序用C++6.0编写，完成栈的生成。

（1）输入的形式和输入值的范围：输入合法表达式，以“#”结尾；输入的操作数是正整数，运算符只含加减乘除四种运算符。

（2）输出的形式：显示输入是否正确、输入序列和栈的变化过程、计算结果。

（3）程序所能达到的功能：完成算术表达式的计算。 （4）测试数据：

①输入3*（2+4）#； ②输入5*－2#。

2.概要设计

（1）为了实现上述程序功能，需要定义栈的抽象数据类型：

ADT SqStack{

数据对象：D={ai| ai ∈ElemSet,i=1,2,3??，n,n≥0} 数据关系：R1={| ai-1,ai ∈D,i=1,2,3,??，n} 基本操作：

InitStack(SqStack &S)

操作结果：声明栈建立函数 Push(SqStack &S,char e)

初始条件：栈已经存在 操作结果：声明入栈函数 Pop(SqStack &S)

初始条件：栈已经存在 操作结果：声明出栈函数 DispStack(SqStack &S)

初始条件：栈已经存在

操作结果：从栈底到栈顶依次输出各元素

（2）本程序包括5个函数：

①主函数main（）

②确定如何入栈函数evaluate() ③声明取栈顶元素函数GetTop() ④声明比较函数Compare() ⑤声明运算函数Operate()

各函数间关系如下：

InitStack

main

push

evaluate

DispStack Compare Pop GetTop

Operate

3.详细设计

实现概要设计中定义的所有的数据类型，对每个操作给出伪码算法。对主程序和其他模块也都需要写出伪码算法。

（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 { }

void InitStack2(SqStack2 &S2)//构造一个空栈S2 { }

void Push1(SqStack1 &S1,char e)//入栈 {

if(S1.top-S1.base>=S1.stacksize)//如果栈满，追加存储空间 {

S1.base=(char

S2.base=new SElemType2[STACK_INIT_SIZE];

if(!S2.base)cout<<\存储分配失败！\存储分配失败 S2.top=S2.base;

S2.stacksize=STACK_INIT_SIZE;

S1.base=new SElemType[STACK_INIT_SIZE];

if(!S1.base)cout<<\存储分配失败！\存储分配失败 S1.top=S1.base;

S1.stacksize=STACK_INIT_SIZE;

*)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));

}

char Pop1(SqStack1 &S1)//出栈 { }

float Pop2(SqStack2 &S2)//出栈 {

float e; char e;

if(S1.top==S1.base)cout<<\运算符栈已空!\\n\e=*(--S1.top); return e; }

*S2.top=e;S2.top=S2.top+1;//将元素e入栈，指针上移

if(!S2.base)cout<<\存储分配失败！\else { }

S2.top=S2.base+S2.stacksize;

S2.stacksize=S2.stacksize+STACKINCREMENT;

本文来源：https://www.bwwdw.com/article/cakd.html