黔南民族师范学院教师备课用纸第页共NUMPAGES7页实验二栈和队列及其应用实验目的：１．深入了解栈和队列的特性。２．巩固对这两种结构方法的掌握。３．接触较复杂问题的递归算法设计。实验内容：１．对这两种结构方法的掌握。２．接触较复杂问题的递归算法设计。问题描述：（二选一）1、设计一个算术表达式求值演示器2、数制转换实验要求：1、以字符序列的形式从终端输入语法正确的、不含变量的整数表达式。（输入一个十进制数，把该数转换成八进数）2、实现对算术四则混合运算表达式的求值。测试数据：1、3*（7-2）实验代码：typedefcharSElemType;typedefintStatus;#include<string.h>#include<ctype.h>#include<malloc.h>#include<stdlib.h>#include<stdio.h>#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW-2//栈的顺序存储表示#defineSTACK_INIT_SIZE10//存储空间初始分配量#defineSTACKINCREMENT2//存储空间分配增量typedefstruct{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(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).stacksize=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*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).top;returne;}/*Pop2*///基本操作//判断两符号的优先关系SElemTypePrecede(SElemTypet1,SElemTypet2){SElemTypef;switch(t2){case'+':case'-':if(t1=='('||t1=='#')f='<';elsef='>';break;case'^':case'*':case'/':if(t1=='^'||t1=='*'||t1=='/'||t1==')')f='>';elsef='<';break;case'(':if(t1==')'){printf("ERROR1\n");exit(ERROR);}elsef='<';break;c