数据结构课程设计
设计说明书
算术表达式求值问题
学生姓名白子健
学号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之间的优先关系至多是下面三种关系之一：opt1opt1=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的函数，如果是编译表达式，则产生这个运算的一组相应指令并返回存放结果的中间变量名；如果是解释执行表达式，则直接进行该运算，并返回运算的结果。
