资源描述：
《数据结构实验三 栈和队列的应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构试验报告实验三栈和队列的应用实验题目：表达式求值问题专业班级：网络工程1002班组长：郭坤铭（2010100243）组员：王星（2010100230）张磊（2010100244）2012年4月13日11实验报告实验类型__综合设计__实验室_软件实验室一__一、实验题目表达式求值问题二、实验目的和要求1．掌握栈和队列的概念和特点2．掌握栈和队列在顺序和链式存储结构下的插入、删除算法3．认真分析项目实例中的内容，将相关程序在计算机上运行实现三、需求分析本演示程序用c++6.0编写，完成用户输入一个包含正整数、括号和四则运算符（“+”、“—”
2、、“*”、“/”）的算术表达式后，计算出其结果的简易计算器。1、置操作数栈为空栈，表达式起始符“#”为运算符栈底元素；2、依次读入表达式中每个字符，若是操数则进操作数栈，若是操作符则和操作符栈顶的运算符进行比较优先权后作相应的操作，直到整个表达式求值完毕（即操作符栈顶元素和当前读入的字符均为“#”）3、测试数据：用户输入的表达式为(2+3)*4/5-1,程序对此表达式进行计算后，所得结果应为3.四、概要设计为了实现上述程序功能，需要定义1、栈的抽象数据类型如下： ADTStack{11 数据对象：D={ai
3、ai∈ElemSet,i=1,2,
4、…,n,n≥0} 数据关系：R1={
5、ai-1,ai∈D,i=2,…,n}约定an端为栈顶，a1端为栈底。 基本操作： InitStack(seqstack*S) 操作结果：构造一个空的栈S. Empty(seqstack*S) 初始条件：栈S已存在操作结果：若S为栈空，则返回TRUE，否则FALSE。Push(seqstack*S,inte) 初始条件：栈S已存在 操作结果：插入元素e为新的栈顶元素Pop(seqstack*S) 初始条件：栈S已存在 操作结果：删除S的栈顶元素。 GetTop(se
6、qstack*S) 初始条件：栈S已存在且非空 操作结果：取出S的栈顶元素。Operate(inta,charr,intb) 操作结果：将a,b变成相应的数字。Proceed(char,char)操作结果：比较读取的运算符和栈顶运算符的优先级。In(char)操作结果：判断读入的字符是不是运算符是则进栈。11EvalExpres(void)操作结果：对表达式进行求值操作，计算出结果。 }2、本程序包含三个模块1)主程序模块：协调各函数的调用，调用表达式求值模块中的函数，最终实现所要求的功能;2)表达式求值模块：实现对用户输入的表达式计算出值
7、的功能；3）各模块之间的调用关系如下：主程序模块↓(调用)表达式求值模块四、详细设计#include#defineMAXSIZE161、顺序栈的定义typedefstruct{intdata[MAXSIZE];inttop;intbase;}seqstack;2、以下为函数声明voidInitStack(seqstack*);intEmpty(seqstack*);voidPush(seqstack*,int);intPop(seqstack*);intGetTop(seqstack*);intOperate(int,char,
8、int);charProceed(char,char);11intIn(char);intEvalExpres(void);3、定义两个栈分别存放运算符和操作数seqstackOPTR,OPND;4、主函数intmain(){intv;charch;while(1){printf("t*****************用顺序栈实现整型算术表达式的求值**************");v=EvalExpres();printf("结果为:%d",v);//以下为程序控制printf("输入q为退出程序，输入回车则继续:");do{scan
9、f("%c",&ch);if(ch=='q'
10、
11、ch=='Q')exit(0);}while(ch!='');system("cls");}return0;}voidInitStack(seqstack*s){s->top=0;s->base=0;}//初始化栈intEmpty(seqstack*s){if(s->top==s->base)return1;elsereturn0;11}//判断栈是否为空voidPush(seqstack*s,intx){if(s->top==MAXSIZE){printf("OVERFLOW!");exi
12、t(0);}else{s->data[s->top]=x;s->top++;}}//进栈intPop(seqstack*s){inte;
