数据结构实验报告栈操作

《数据结构》实验报告◎实验题目:栈的应用。◎实验目的：熟悉掌握对栈的应用和基本操作。◎实验内容：用算符优先法对算术表达式求值。一、需求分析通过程序设计实现算符优先法：1以字符串的形式输入整形数据和运算符号；2、输出算术表达式的结果；3、实现简单的一位整型数据的算术运算；4、测试数据：算术表达式，其中的整型数据均只有一位。二概要设计

1.基本操作 voidInitStack(SqStack*s) 操作结果：栈的初始化。 intGetTop(SqStack*s) 初始条件：栈已存在且不空； 操作结果：将栈顶元素返回。 voidPush(SqStack*s,inte) 初始条件：栈已存在； 操作结果：插入e作为新的栈顶元素。 charPop1(SqStack*s) 初始条件：运算符栈已存在且不空； 操作结果：栈顶元素出栈。 intPop2(SqStack*s) 初始条件：运算数栈已存在且不空； 操作结果：栈顶元素出栈。 charprecede(charA,charB) 操作结果：比较两个算符的优先级，并将比较结果返回。 intIn(charTest) 操作结果：判断字符是否是运算符。 intEvaluateExpression() 操作结果：通过调用一系列的函数，对表达式求值。 main() 操作结果：主要通过调用函数EvaluateExpression得到最终结果。2．本程序包含两个模块：（1）构造栈的模块；（2）主程序模块；(三)详细设计1．声明，栈的结构体和判断运算符优先级的表格（以数组形式表达）：typedefstruct{ int*base; int*top; intstacksize;}SqStack;#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineoverflow1#defineerror0charOPSET[7]={'+','-','*','/','(',')','#'};//运算符种类unsignedcharPrior[7][7]= {//算符间的优先关系 '>','>','<','<','<','>','>', '>','>','<','<','<','>','>', '>','>','>','>','<','>','>', '>','>','>','>','<','>','>', '<','<','<','<','<','=','', '>','>','>','>','','>','>', '<','<','<','<','<','','=' };2.各个函数的详细设计：voidInitStack(SqStack*s)//栈的初始化{ s->base=(int*)malloc(STACK_INIT_SIZE*sizeof(int)); if(!s->base)exit(error);//存储分配失败 s->top=s->base; s->stacksize=STACK_INIT_SIZE;}intGetTop(SqStack*s)//若运算符栈不空则用e返回栈顶元素{ if(s->top==s->base) exit(overflow); return(*(s->top-1));}voidPush(SqStack*s,inte)//插入e为新的栈顶元素{ if(s->top-s->base>=s->stacksize) { s->base=(int*)realloc(s->base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(int)); if(!s->base)exit(error); s->top=s->base+s->stacksize;; s->stacksize=s->stacksize+STACKINCREMENT; } *s->top=e; s->top++;}charPop1(SqStack*s)//运算符栈顶元素出栈{ if(s->top==s->base) returnerror; return(*--s->top);}intPop2(SqStack*s)//运算数栈顶元素出栈{ if(s->top==s->base) returnerror; return(*--s->top);}charPrecede(charA,charB)//实现两个算符优先级的比较{ returnPrior[FindOpOrd(A,OPSET)][FindOpOrd(B,OPSET)];}在Precede函数中再调用FindOpOrd函数，设计如下：intFindOpOrd(charop,char*TestOp)//在Prior数组中按行或者按列找到算符对应的位置{ inti; for(i=0;i<7;i++) { if(op==TestOp[i]) returni; }}intOperate(inta,unsignedchartheta,intb)//根据运算符进行二元运算{switch(theta){case'+':returna+b;case'-':returna-b;case'*':returna*b;case'/':if(b!=0) returna/b; else exit(error);default:returnerror;}}intIn(charTest)//判断字符是否为运算符，如果是运算符返回1，否则返回0{if('0'<=Test&&Test<='9') return0;else return1;}intEvaluateExpression()//算符优先法的实现{SqStackOPTR,OPND; charc,theta;inta,b,result;InitStack(&OPTR);//创建运算符栈Push(&OPTR,'#');//在运算符栈栈底放上#InitStack(&OPND);//创建运算数栈c=getchar();while(c!='#'||GetTop(&OPTR)!='#'){if(In(c)==0)//不是运算符则进栈 { Push(&OPND,c-48); printf(" 运算数%d直接进运算数栈\n",c-48); c=getchar();} else {switch(Precede(GetTop(&OPTR),c)) {case'<'://栈顶元素优先级低Push(&OPTR,c); printf(" 运算符%c直接进运算符栈\n",c);c=getchar();break;case'='://脱括号并接收下一字符Pop1(&OPTR); printf(" 输入）后运算符栈进行脱括号操作\n");c=getchar();break;case'>'://退栈并将运算结果入栈theta=Pop1(&OPTR); printf(" 运算符%c从运算符栈顶弹出\n",theta);b=Pop2(&OPND); printf(" 运算数%d从运算数栈顶弹出\n",b);a=Pop2(&OPND); printf(" 运算数%d从运算数栈顶弹出\n",a);Push(&OPND,Operate(a,theta,b)); printf(" 运算数%d和运算数%d进行%c运算并将结果进运算数栈\n",a,b,theta);break;}//switch}}//whilereturn(Pop2(&OPND));}//EvaluateExpression函数EvaluateExpression通过调用其它函数实现了算符优先法计算表达式，因此主函数主要通过调用该函数进行运算。intmain(){ intresult; printf("请输入表达式（以#表示输入结束）：\n"); result=EvaluateExpression(); printf("result=%d\n",result); return0;}3.完整的程序见源文件。(四)程序使用说明及测试结果1．程序使用说明（1）本程序的运行环境为VC6.0。（2）进入演示程序后即显示提示信息： 请输入表达式（以#表示输入结束）：例如输入：3+2*(5+8)#点击回车即可得到结果及运算过程。（3）运行界面如图所示：（五）、实验总结(实验心得)1.关于函数调用过程中要注意参数的传递，以及函数的返回值问题。特别应注意参数类型和返回值的类型。2.在设计比较两个运算符优先级函数Precede的过程中花费时间长，最后采用直接将