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

实验二 栈和队列实现四则运算 实验二 栈和队列实现四则运算 一、实验目的及要求 ： 1、掌握栈和队列的基本操作：建立、插入、删除、查找、合并 2 、掌握用栈和队列的储存 3 、熟悉 C 语言上机编程环境 4 、掌握编译、调试程序的方法 二、实验内容 ： 采用栈进行表达式的求值， 表达式求值是程序设计语言编译中的一个最基本问题。 它的 实现是栈应用的又一个典型例子，本报告使用的是“算符优先法”求表达式的值。 要把一个表达式翻译成正确求值的一个机器指令序列， 或者直接对表达式求值， 首先要 能够正确解释表达式。若要正确翻译则首先要了解算术四则运算的规则。即： （1）、先乘除，后加减； （2 ）、从左算到右； （3）、先括号内后括号外。 任何一个表达式都是由操作数、运算符和界限符组成的，我们称它们为单词。一般地， 操作数既可以是常数也可以是被说明为变量或常量的标识符；运算符可以分为算术运算符、 关系运算符和逻辑运算符 3 类；基本界限符有左右括号和表达式结束符等。 为了叙述的简洁， 我们仅讨论简单算术表达式的求值问题。这种表达式只包含加、减、乘、除 4 种运算符。 我们把运算符和界限符统称为算符，它们构成的集合命名为 OP。根据上述 3 条运算规 则，在运算的每一步中，任意两个相继出现的算符 1 和 2 之间的优先级之多是以下 3 种关 系之一： 1 2 1 的优先级低于 2 1 2 1 的优先级等于 2 1 2 1 的优先级高于 2 根据实际情况推导出如下的优先关系 算符间的优先关系表 + - * / （ ） # 1 2 + - * / ） ） # = 实验二 栈和队列实现四则运算 有规则（ 3 ），+、-、* 和/ 为 1 时优先性均低于“ （”但高于“），”由规则（ 2 ），当 1 2 时，令 1 2 ，“# ”是表达式的结束符。为了算法简洁，在表达式左右括号的最左边也虚 设了一个“ # ”构成整个表达式的一对括号。表中的“ （”= “）”表示当左右括号相遇时，括 号内的运算已经完成。同理， “#”= “# ”表示整个表达式求值完毕。 “）”与“（、“#”