实验二栈和队列及其应用.doc

《实验二栈和队列及其应用.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、实验二　栈和队列及其应用实验目的：１．深入了解栈和队列的特性。２．巩固对这两种结构方法的掌握。３．接触较复杂问题的递归算法设计。实验内容：１．对这两种结构方法的掌握。２．接触较复杂问题的递归算法设计。问题描述：（二选一）1、设计一个算术表达式求值演示器2、数制转换实验要求：1、以字符序列的形式从终端输入语法正确的、不含变量的整数表达式。（输入一个十进制数，把该数转换成八进数）2、实现对算术四则混合运算表达式的求值。测试数据：1、3*（7-2）实验代码：typedefcharSElemType;typede

2、fintStatus;#include#include#include#include#include#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW-2//栈的顺序存储表示#defineSTACK_INIT_SIZE10//存储空间初始分配量#defineSTACKINCREMENT2//存储空间分配增量typedefstruct{

3、SElemType*base;//在栈构造之前和销毁之后，base的值为nullSElemType*top;//栈顶指针intstacksize;//当前已分配的存储空间，以元素为单位}SqStack2;//顺序栈typedefstruct{int*base;int*top;intstacksize;}SqStack1;/*结构类型1，用于定义存储操作数的栈*/intReadNum(char*s,int*j);intInitStack1(SqStack1*S){(*S).base=(int*)malloc

4、(STACK_INIT_SIZE*sizeof(int));if(!(*S).base)exit(0);(*S).top=(*S).base;(*S).stacksize=STACK_INIT_SIZE;return1;}/*InitStack1*/intInitStack2(SqStack2*S){(*S).base=(char*)malloc(STACK_INIT_SIZE*sizeof(char));if(!(*S).base)exit(0);(*S).top=(*S).base;(*S).stac

5、ksize=STACK_INIT_SIZE;return1;}/*InitStack2*/intGetTop1(SqStack1*S){inte;if((*S).top==(*S).base)return0;e=*((*S).top-1);returne;}/*GetTop1*/charGetTop2(SqStack2*S){chare;if((*S).top==(*S).base)return0;e=*((*S).top-1);returne;}/*GetTop2*/intPush1(SqStack1*

6、S,inte){*(*S).top++=e;return1;}/*Push1*/intPush2(SqStack2*S,chare){*(*S).top++=e;return1;}/*Push2*/intPop1(SqStack1*S){inte;if((*S).top==(*S).base)return0;e=*--(*S).top;returne;}/*Pop1*/intPop2(SqStack2*S){chare;if((*S).top==(*S).base)return0;e=*--(*S).to

7、p;returne;}/*Pop2*///基本操作//判断两符号的优先关系SElemTypePrecede(SElemTypet1,SElemTypet2){SElemTypef;switch(t2){case'+':case'-':if(t1=='('

8、

9、t1=='#')f='<';elsef='>';break;case'^':case'*':case'/':if(t1=='^'

10、

11、t1=='*'

12、

13、t1=='/'

14、

15、t1==')')f='>';elsef='<';break;case'(':if(t

16、1==')'){printf("ERROR1");exit(ERROR);}elsef='<';break;case')':switch(t1){case'(':f='=';break;case'#':printf("ERROR2");exit(ERROR);default:f='>';}break;case'#':switch(t1){case'#':f='=';break;case'(':printf("ERROR