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

1、实验二 栈和队列实现四则运算一、实验目的及要求：1、掌握栈和队列的基本操作：建立、插入、删除、查找、合并2、掌握用栈和队列的储存3、熟悉C语言上机编程环境4、掌握编译、调试程序的方法二、实验内容：采用栈进行表达式的求值，表达式求值是程序设计语言编译中的一个最基本问题。它的实现是栈应用的又一个典型例子，本报告使用的是“算符优先法”求表达式的值。要把一个表达式翻译成正确求值的一个机器指令序列，或者直接对表达式求值，首先要能够正确解释表达式。若要正确翻译则首先要了解算术四则运算的规则。即：（1）、先乘除，后加减；（2）、从左算到右；（3）、先括号内后括号外。任何一个表达式都是由操作数、运算符和界限符

2、组成的，我们称它们为单词。一般地，操作数既可以是常数也可以是被说明为变量或常量的标识符；运算符可以分为算术运算符、关系运算符和逻辑运算符3类；基本界限符有左右括号和表达式结束符等。为了叙述的简洁，我们仅讨论简单算术表达式的求值问题。这种表达式只包含加、减、乘、除4种运算符。我们把运算符和界限符统称为算符，它们构成的集合命名为OP。根据上述3条运算规则，在运算的每一步中，任意两个相继出现的算符和之间的优先级之多是以下3种关系之一： 的优先级低于 的优先级等于 的优先级高于根据实际情况推导出如下的优先关系算符间的优先关系表 +-*/（）#+-*/）#=有规则（3），+、-、*和/为时优先性均低于“

3、（”但高于“），”由规则（2），当时，令，“#”是表达式的结束符。为了算法简洁，在表达式左右括号的最左边也虚设了一个“#”构成整个表达式的一对括号。表中的“（”=“）”表示当左右括号相遇时，括号内的运算已经完成。同理，“#”=“#”表示整个表达式求值完毕。“）”与“（、“#”与“）”以及“（”与“#”之间无优先级，这是因为表达式中不允许它们相继出现，一旦遇到这种情况，则可以认为出现语法错误。为实现算符优先算法，可以使用两个栈。一个称作OPTR，用以寄存运算符；另一个称作OPND，用以寄存操作数户哟运算结果。算法的基本思想是：（1）首先输入一个表达式，用一数组记录；（2）置操作数栈为空栈，表达式

4、起始符“#”为运算符栈的栈底元素；（3）依次读入表达式中的每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈的栈顶元素比较优先权后作相应操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为“#”）。三、程序代码#include #include #include #define error 0 /错误标志#define ok 1 /正确标志#define overflow -1 /溢出标志#define Stack_Size 100 /一般表达式运算符和运算数不会很长，100足够用#define OP_Size 7 /一共7种运算符char OPOP_Size=+

5、,-,*,/,(,),#; /运算符unsigned char Prior77 = , , , , , , , ,=; / 算符间的优先关系template struct SqStack T *top; T *base; int stacksize;/顺序栈结构模板template int InitStack(T1 &S) S.base=(T2 *)malloc(Stack_Size*sizeof(T2); if(!S.base) exit (overflow); S.top=S.base; S.stacksize=Stack_Size; return ok;/初始化栈函数模板template

6、 int Push(T1 &S,T2 e) 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; return ok;/入栈函数模板template int Pop(T1 &S,T2 &e) if(S.top=S.base) return error; e=*-S.top; return ok;/出栈函数模板templ

7、ate T2 GetTop(T1 S) if(S.top=S.base) return error; else return *(S.top-1);/获取栈顶元素模板int In(char Test,char* TestOp) bool Find=false; for (int i=0; i OP_Size; i+) if (Test = TestOpi) Find= true; return Find;/判断是否为运算符float Operate(float a,unsigned char theta, float b) switch(theta) case +: return a+b; c

8、ase -: return a-b; case *: return a*b; case /: return a/b; default : return 0; /运算 int ReturnOpOrd(char op,char* TestOp) int i; for(i=0; i OP_Size; i+) if (op = TestOpi) return i; return 0;char precede(char Aop, char Bop) return PriorReturnOpOrd(Aop,OP)ReturnOpOrd(Bop,OP);/ReturnOpOrd和precede组合，判断运算

9、符优先级float EvaluateExpression() / 算术表达式求值的算符优先算法。 / 设OPTR和OPND分别为运算符栈和运算数栈，OPSET为运算符集合。 SqStack OPTR; / 运算符栈，字符元素 SqStack OPND; / 运算数栈，实数元素 char TempData20; float Data,a,b; char theta,c,x,Dr2; InitStackSqStack,char (OPTR); Push (OPTR, #); InitStack SqStack,float(OPND); strcpy(TempData,0);/将TempData置为

10、空 c=getchar(); while (c!= # | GetTopSqStack,char(OPTR)!= #) if (!In(c, OP) Dr0=c; Dr1=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(Ge

11、tTopSqStack,char(OPTR), c) case : / 退栈并将运算结果入栈 Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operate(a, theta, b); break; / for switch / for while return GetTopSqStack,float(OPND); / EvaluateExpressionvoid main() printf(请输入表达式，并以#结尾：n); printf(%fn,EvaluateExpression();四、运行结果：5、 实验心得 运用栈来实现最简单的四则运算，从实例中了解栈和队列的结构，以及进栈和出栈的过程。有关栈的构造、入栈