表达式求值课程设计报告

. . . .

数据结构课程设计

设计说明书

算术表达式求值问题

学生姓名白子健

学号1318014057

班级计本1302

成绩

指导教师李军

计算机科学与技术系

2015年9月10日

. 资料. .. .

. . . .

数据结构课程设计评阅书

. 资料. .. .

. . . .

课程设计任务书

2015—2016学年第一学期

专业：计算机科学与技术学号：1318014057 姓名：白子健

课程设计名称：课程设计Ⅰ---数据结构课程设计

设计题目：表达式求值算法的实现

完成期限：自2015 年9 月 1 日至2015 年9 月12 日共2 周

设计内容及要求:

算术表达式求值是程序设计语言编译中的一个基本问题，通过栈实现表达式运算优先级的匹配和运算。用C/C++语言编程实现任意算术表达式的求值，设计内容要求如下：（1）表达式共有三种基本表示方法：前缀法、中缀法、后缀法。从表达式的这三种基本方法中任选一种方法进行编程求值。

（2）分析所选的表示方法，根据选定的表示方法确定对应的存储结构和相关算法。

（3）算法要能正确处理算术运算的优先级规则，即: 先括号内，后括号外的规则；运算先乘除，后加减；同级运算从左到右。

如下表达式：

50+（6*3+2）

要求：

(1)用C/C++语言编写一个程序将这组学生成绩输入到计算机中，数据运算的存储

逻辑结构为栈。

(2)程序要能正确处理表达式的优先级、输出正确运算结果。

最终设计成果形式为：

1、设计好的软件一套；

2、撰写一份课程设计说明书一份，打印并装订成册。

指导教师（签字）：教研室主任（签字）：

批准日期：年月日

. 资料. .. .

. . . .

目录

1 课题描述 (1)

2 设计思路 (2)

3 算法设计 (3)

4 程序代码 (5)

5 测试及分析 (12)

6 总结 (13)

参考文献 (13)

. 资料. .. .

. . . .

1 课题描述

表达式求值是程序设计语言编译中的一个最基本问题。表达式求值在计算机中的实现是栈结构在计算机中的一个典型应用。这里使用“算符优先算法”实现表达式求值。

要把一个表达式翻译成正确求值的一个机器指令序列，或者直接对表达式求值，首先要能够正确解释表达式。例如对表达式求值：

50+（6*3+2）

首先要了解算术四则运算的规则。即：先算括号内，后算括号外；先乘除后加减；同级运算顺序从左到右；所以，这个表达式的运算顺序为：

50+（6*3+2）=50+（18+2）=50+20=70

算符优先算法就是根据这个运算优先关系来编译或者解释执行的。

. 资料. .. .

. . . .

2 设计思路

2.1表达式的输入：

表达式从键盘输入，存入字符串数组中。

2.2运算的实现：

任何一个表达式都是由操作数（operand）、运算符（operator）和界限符（delimiter）组成的。可以把运算符和界限符统称为算符，根据算术运算规则，在运算的每一步中，任意两个相继出现的算符opt1和opt2之间的优先关系至多是下面三种关系之一：opt1

opt1=opt2，即opt1的优先级等于opt2；

opt1>opt2，即opt1的优先级高于opt2。

表1

输入的表达式（包含运算符和操作数）以字符串的形式输入，故需要一个字符串数组存储键盘的输入。在对输入的表达式求值前，应先检查输入的合法性。只有正确的输入才能输出正确的计算结果。算符优先算法运算需要两个栈：操作数栈（OPND）和运算符栈（OPTR）。栈可以采用数组实现，并定义栈的相关操作：初始化、压栈、出栈、判断栈满、判断栈空等相关操作。

输入的字符串解析分离出操作数和运算符，分别进入操作数栈和运算符栈。运算始终在栈顶实现，最终操作数栈只剩一个元素，即运算结果。

. 资料. .. .

. . . .

3算法设计

使用两个工作栈：一个称作OPTR，用以寄存运算符；另一个称作OPTD，用以寄存操作数或运算结果。算法的基本思想是：

（1）置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素；

（2）依次读入表达式中的每个字符，若是操作数则进入OPND栈，若是运算符则和OPTR栈的栈顶元素比较优先级后进行相应的操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前字符串读入的字符均为“#”）。

算法如下：

OperandType EvaluateExpression(){

//算术表达式求值的算符优先算法。OPTR和OPND分别为运算符栈和运算数栈

//OP为运算符集合{+、-、*、/、（、）、#、.}

InitStack(OPTR);

Push(OPTR, ‘#’);

InitStack(OPND);

c = getchar();

while (c!=’#’ || GetTop(OPTR)!=’#’){

if (!IsOpt(c)){Push(OPND, c); c = getchar();} //不是运算符则进栈；

else{

switch (Precede(GetTop(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;

}//switch

}//while

Return GetTop(OPND);

}//EvaluateExpression

算法中还调用了两个函数。其中Precede是判定运算符栈的栈顶运算符opt1与读入的运算符opt2之间优先关系的函数；Operate为进行二元运算a opt b的函数，如果是编译表达式，则产生这个运算的一组相应指令并返回存放结果的中间变量名；如果是解释执行表达式，则直接进行该运算，并返回运算的结果。

程序流程图如下：

. 资料. .. .

本文来源：https://www.bwwdw.com/article/peeq.html