算法与数据结构栈与队列实验报告

实验二栈和队列实现四则运算实验二栈和队列实现四则运算一、实验目的及要求：1、掌握栈和队列的基本操作：建立、插入、删除、查找、合并2、掌握用栈和队列的储存3、熟悉C语言上机编程环境4、掌握编译、调试程序的方法二、实验内容：采用栈进行表达式的求值，表达式求值是程序设计语言编译中的一个最基本问题。它的实现是栈应用的又一个典型例子，本报告使用的是“算符优先法”求表达式的值。要把一个表达式翻译成正确求值的一个机器指令序列，或者直接对表达式求值，首先要能够正确解释表达式。若要正确翻译则首先要了解算术四则运算的规则。即：（1）、先乘除，后加减；（2）、从左算到右；（3）、先括号内后括号外。任何一个表达式都是由操作数、运算符和界限符组成的，我们称它们为单词。一般地，操作数既可以是常数也可以是被说明为变量或常量的标识符；运算符可以分为算术运算符、关系运算符和逻辑运算符3类；基本界限符有左右括号和表达式结束符等。为了叙述的简洁，我们仅讨论简单算术表达式的求值问题。这种表达式只包含加、减、乘、除4种运算符。我们把运算符和界限符统称为算符，它们构成的集合命名为OP。根据上述3条运算规则，在运算的每一步中，任意两个相继出现的算符1和2之间的优先级之多是以下3种关系之一：121的优先级低于2121的优先级等于2121的优先级高于2根据实际情况推导出如下的优先关系算符间的优先关系表12+-*/（）#+-*/））#=实验二栈和队列实现四则运算有规则（3），+、-、*和/为1时优先性均低于“（”但高于“），”由规则（2），当12时，令12，“#”是表达式的结束符。为了算法简洁，在表达式左右括号的最左边也虚设了一个“#”构成整个表达式的一对括号。表中的“（”=“）”表示当左右括号相遇时，括号内的运算已经完成。同理，“#”=“#”表示整个表达式求值完毕。“）”与“（、“#”与“）”以及“（”与“#”之间无优先级，这是因为表达式中不允许它们相继出现，一旦遇到这种情况，则可以认为出现语法错误。为实现算符优先算法，可以使用两个栈。一个称作OPTR，用以寄存运算符；另一个称作OPND，用以寄存操作数户哟运算结果。算法的基本思想是：（1）首先输入一个表达式，用一数组记录；（2）置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素；（3）依次读入表达式中的每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈的栈顶元素比较优先权后作相应操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为“#”）。三、程序代码#includestdio.h#includestdlib.h#includestring.h#defineerror0//错误标志#defineok1//正确标志#defineoverflow-1//溢出标志#defineStack_Size100//一般表达式运算符和运算数不会很长，100足够用#defineOP_Size7//一共7种运算符charOP[OP_Size]={'+','-','*','/','(',')','#'};//运算符unsignedcharPrior[7][7]={'','','','','','','','','','','','','','','','','','','','','','','','','','','','','','','','','','=','','','','','','','','','','','','','','','='};//算符间的优先关系templatetypenameTstructSqStack{T*top;T*base;intstacksize;};//顺序栈结构模板实验二栈和队列实现四则运算templatetypenameT1,typenameT2intInitStack(T1&S){S.base=(T2*)malloc(Stack_Size*sizeof(T2));if(!S.base)exit(overflow);S.top=S.base;S.stacksize=Stack_Size;returnok;}//初始化栈函数模板templatetypenameT1,typenameT2intPush(T1&S,T2e){if(S.top-S.base=S.stacksize){S.base=(T2*)realloc(S.base,(S.stacksize+1)*sizeof(T2));if(!S.base)exit(overflow);S.top=S.base+S.stacksize;S.stacksize+=1;}*S.top++=e;returnok;}//入栈函数模板templatetypenameT1,typenameT2intPop(T1&S,T2&e){if(S.top==S.base)returnerror;e=*--S.top;returnok;}//出栈函数模板templatetypenameT1,typenameT2T2GetTop(T1S){if(S.top==S.base)returnerror;elsereturn*(S.top-1);}//获取栈顶元素模板intIn(charTest,char*TestOp){boolFind=false;实验二栈和队列实现四则运算for(inti=0;iOP_Size;i++){if(Test==TestOp[i])Find=true;}returnFind;}//判断是否为运算符floatOperate(floata,unsignedchartheta,floatb){switch(theta){case'+':returna+b;case'-':returna-b;case'*':returna*b;case'/':returna/b;default:return0;}}//运算intReturnOpOrd(charop,char*TestOp){inti;for(i=0;iOP_Size;i++){if(op==TestOp[i])returni;}return0;}charprecede(charAop,charBop){returnPrior[ReturnOpOrd(Aop,OP)][ReturnOpOrd(Bop,OP)];}//ReturnOpOrd和precede组合，判断运算符优先级floatEvaluateExpression(){//算术表达式求值的算符优先算法。//设OPTR和OPND分别为运算符栈和运算数栈，OPSET为运算符集合。SqStackcharOPTR;//运算符栈，字符元素SqStackfloatOPND;//运算数栈，实数元素charTempData[20];floatData,a,b;chartheta,c,x,Dr[2];InitStackSqStackchar,char(OPTR);Push(OPTR,'#');InitStackSqStackfloat,float(OPND);strcpy(TempData,\0);//将TempData置为空c=getchar();while(c!='#'||GetTopSqStackchar,char(OPTR)!='#'){if(!In(c,OP))实验二栈和队列实现四则运算{Dr[0]=c;Dr[1]='\0';//存放单个数strcat(TempData,Dr);//将单个数连到TempData中，形成字符串c=getchar();if(In(c,OP))//如果遇到运算符，则将字符串TempData转换成实数，入栈，//并重新置空{Data=(float)atof(TempData);Push(OPND,Data);strcpy(TempData,\0);}}else{//不是运算符则进栈switch(precede(GetTopSqStackchar,char(OPTR),c)){case''://栈顶元素优先权低Push(OPTR,c);c=getchar();break;case'='://脱括号并接收下一字符Pop(OPTR,x);c=getchar();break;case''://退栈并将运算结果入栈Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b));break;}//forswitch}}//forwhilereturnGetTopSqStackfloat,float(OPND);}//EvaluateExpressionvoidmain(){printf(请输入表达式，并以#结尾：\n);printf(%f\n,EvaluateExpression());}实验二栈和队列实现四则运算四、运行结果：五、实验心得运用栈来实现最简单的四则运算，从实例中了解栈和队列的结构，以及进栈和出栈的过程。有关栈的构造、入栈、出栈等模块的代码都有源程序可参考，完成本实验的代码只需要组合学过的各个模块，结合起来进行相应的调试就可以实现。从中学会了写程序不一定所有代码都是自己重新写的，只要会运用、会调试就能高效地完成。这就要求在学习的过程中多积累好的源代码以备不时之需，也应该多尝试着自己去调试程序完成一些功能。这样在学好了算法与数据结构的前提下就能很快地写出自己需要的程序。