表达式求值实验报告.doc

福建农林大学计算机与信息学院
计算机类
课程设计报告

课程名称：
《面向对象程序设计》课程设计
课程设计题目：
表达式求值
姓 名：
吴玲婷
系：
软件工程系
专 业：
软件工程
年 级：
2012
学 号：
3126016054
指导教师：
林敏
职 称：
讲师

2014 年 1 月 1 日

15

目 录
1、课程设计的目的 1
2、课程设计的要求 1
3、课程设计的内容 1
3.1设计的任务 1
3.2设计要求 1
3.3程序的总体结构 2
3.4详细设计 3
3.4.1类的设计 3
3.4.2各模块设计及程序流程 4
3.4.3代码实现 7
4、测试 11
5、总结 12
6、参考文献 12
7、附录 13

题目
1、课程设计的目的
（1）了解并掌握面向对象程序的设计方法，具备初步的独立分析和设计能力；
（2）初步掌握应用面向对象程序进行软件开发的步骤；
（3）提高综合运用所学的理论知识和方法独立分析和解决问题的能力；
（4） 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风；
2、课程设计的要求
（1）设计的课题能够体现面向对象程序设计的思路。
（2）根据自己对数据结构和算法的基本概念、原理和机制的理解，自拟题目和设计内容，选题尽可能结合实际的应用。
3、课程设计的内容
3.1设计的任务
在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。
算法输入：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为简化，规定操作数只能为正整数，操作符为+、-、*、/，用#表示结束。
算法输出：表达式运算结果。
算法要点：设置运算符栈和运算数栈辅助分运析算符优先关系。在读入表达式的字符序列的同时，完成运算符和运算数的识别处理，以及相应运算。
3.2设计要求
用类实现对栈的封装功能，完成表达式求值。
任何一个表达式都是由操作符，运算符和界限符组成的。我们分别用顺序栈来寄存表达式的操作数和运算符。栈是限定于仅在表尾进行插入或删除操作的线性表。顺序栈的存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置，base为栈底指针，在顺序栈中，它始终指向栈底，即top=base可作为栈空的标记，每当插入新的栈顶元素时，指针top增1，删除栈顶元素时，指针top减1。
3.3程序的总体结构
为了实现算符优先算法。可以使用两个工作栈。一个称为OPTR，用以寄存运算符，另一个称做OPND，用以寄存操作数或运算结果。
1.首先置操作数栈为空栈，表达式起始符”#”为运算符栈的栈底元素；
2.依次读入表达式，若是操作符即进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权后作相应的操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为”#”）。
3.用ADT描述
ADT Stack{
数据对象：D={ |∈ElemSet,i=1,2,…，n, n≧0}
数据对象：R1={<>|,,i=2,…，n}
约定端为栈顶，端为栈底。
基本操作：
InitStack(&S)
操作结果：构造一个空栈S。
GetTop(S)
初始条件：栈S已存在。
操作结果：用P返回S的栈顶元素。
Push(&S，ch)
初始条件：栈S已存在。
操作结果：插入元素ch为新的栈顶元素。
Pop(&S)
初始条件：栈S已存在。
操作结果：删除S的栈顶元素。
In(ch)
操作结果：判断字符是否是运算符，运算符即返回1。
Precede(c1, c2)
初始条件：c1,c2为运算符。
操作结果：判断运算符优先权，返回优先权高的。
Operate(a,op,b)
初始条件：a,b为整数，op为运算符。
操作结果：a与b进行运算，op为运算符，返回其值。
num(n)
操作结果：返回操作数的长度。
EvalExpr()
初始条件：输入表达式合法。
操作结果：返回表达式的最终结果。
}ADT Stack
3.4详细设计
3.4.1类的设计
1）.栈的基本功能。
InitStack(Stack *s) 和InitStack2(Stack2 *s)分别构造运算符栈与构造操作数栈，Push(Stack s,char ch) 运算符栈插入ch为新的栈顶元素，Push2(Stack2 *s,int ch) 操作数栈插入ch为新的栈顶元素，Pop(Stack *s) 删除运算符栈s的栈顶元素，用p返回其值，Pop2(Stack2 *s)删除操作数栈s的栈顶元素，用p返回其值，GetTop(Stack s)用p返回运算符栈s的栈顶元素，GetTop2(Stack2 s) 用p返回操作数栈s的栈顶元素。
2）.其它功能分析。
(1)In(char ch) 判断字符是否是运算符功能，运算符即返回1，该功能只需简单的一条语句即可实现，return(ch=='+'||ch=='-'||ch='*'||ch=='/'||ch=='('||ch==')'||ch=='#')。
(2) Precede(char c1,char c2) 判断运算符优先权功能，该函数判断运算符c1,c2的优先权，具体优先关系参照表1。
(3) Operate(int a,char op,int b)操作数用对应的运算符进行运算功能。运算结果直接返回。
(4) num(int n) 求操作数的长度功能，需要用itoa函数把int型转换成字符串型，strlen函数可求字符长度。
(5) EvalExpr()主要操作函数运算功能。分析详见3.4.2。
3.4.2各模块设计及程序流程
1).类的总体结构如下：
Precede(ctemplate
class Stack
{
int stacksize;
T *base;
T *top;
public:
int InitStack()；
void Push(T ch)；
T Pop()；
T GetTop()；
}；
2) 判断运算符优先权，返回优先权高的。
运算符间的优先关系如下：

+
-
*
/
(
)
#
+
>
<
<
<
<
>
>
-
>
>
<
<
<
>
>
*
>
>
>
>
<
>
>
/
>
>
>
>
<
>
>
(
<
<
<
<
<
=

)
>
>
>
>

>
>
#
<
<
<
<
<

=
表 1
算法伪代码如下：
char Precede(char c1,char c2)
{
static char array[49]={
'>', '>', '<', '<', '<', '>', '>',
'>', '>', '<', '<', '<', '>', '>',
'>', '>', '>', '>', '<', '>', '>',
'>', '>', '>', '>', '<', '>', '>',
'<', '<', '<', '<', '<', '=', '!',
'>', '>', '>', '>', '!', '>', '>',
'<', '<', '<', '<', '<', '!', '='}; //用一维数组存储49种情况
switch(c1)
{
/* i为下面array的横标 */
case '+' : i=0;break;
case '-' : i=1;break;
case '*' : i=2;break;
case '/' : i=3;break;
case '(' : i=4;break;
case ')' : i=5;break;
case '#' : i=6;break;
}
switch(c2)
{
/* j为下面array的纵标 */
case '+' : j=0;break;
case '-' : j=1;break;
case '*' : j=2;break;
case '/' : j=3;break;
case '(' : j=4;break;
case ')' : j=5;break;
case '#' : j=6;break
}
return (array[7*i+j]); /* 返回运算符array[7*i+j]为对应的c1,c2优先关系*/
}
3. int EvalExpr()主要操作函数。算法概要流程图：

利用该算法对算术表达式3*(7-2)求值操作过程如下：
步骤
OPTR栈
OPND栈
输入字符
主要操作
1
#

3*(7-2)#
Push(OPND,’3’)
2
#
3
*(7-2)#
Push(OPTR,’*’)
3
#*
3
(7-2)#
Push(OPNR,’(’)
4
#*(
3
7-2)#
Push(OPND,’7’)
5
#*(
3 7
-2)#
Push(OPNR,’-’)
6
#*(-
3 7
2)#
Push(OPND,’2’)
7
#*(-
3 7 2
)#
Operate(‘7’,’-’,’2’)
8
#*(
3 5
)#
Pop(OPTR)
9
#*
3 5
#
Operate(‘3’,’*’,5’)
10
#
15
#
Return(GetTop2(OPND))
表2
算法伪代码如下：
int EvalExpr()//主要操作函数
{
char c,theta,x; int m;
int a,b,i=0;
while(*ptr!='#'||OPTR.GetTop()!='#')
{
c = *ptr;
if(!In(c)) //不是运算符
{
sscanf(ptr,"%d",&m);
OPND.Push(m);
while(!In(*ptr))
ptr++;
}
else
switch(Precede(OPTR.GetTop(),c))
{
case '<': //栈顶元素优先级低
OPTR.Push(c);
*ptr++;
break;
case '=': //脱括号并接受下一字符
x=OPTR.Pop();
*ptr++;
break;
case '>': //退栈并将运算结果入栈
theta=OPTR.Pop();
b=OPND.Pop();
a=OPND.Pop();
OPND.Push(Operate(a,theta,b));
break;
}
}
3.4.3代码实现
#include
#include
#include
include
#define NULL 0
#define OK 1
#define ERROR -1
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 20
using namespace std;
/* 定义字符类型栈 */
template
class Stack
{
int stacksize;
T *base;
T *top;
public:
int InitStack()
{
base=(T *)malloc(STACK_INIT_SIZE*sizeof(T));
if(!base) return ERROR;
top=base;
stacksize=STACK_INIT_SIZE;
return OK;
}
void Push(T ch) //运算符栈插入ch为新的栈顶元素
{
*(++top)=ch;
}
T Pop() //删除运算符栈s的栈顶元素，用p返回其值
{
return *(top--);
}
T GetTop()//用p返回运算符栈s的栈顶元素
{
return *top;
}
};
/* 定义整型栈 /
/* ----------------- 全局变量--------------- */
Stack OPTR;/* 定义运算符栈*/
Stack OPND; /* 定义操作数栈 */
char expr[255] = ""; /* 存放表达式串 */
char *ptr = expr;

int In(char ch) //判断字符是否是运算符，运算符即返回1
{
return(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#');
}

/* 判断运算符优先权，返回优先权高的 */

char Precede(char c1,char c2)
{
int i=0,j=0;
static char array[49]={
'>', '>', '<', '<', '<', '>', '>',
'>', '>', '<', '<', '<', '>', '>',
'>', '>', '>', '>', '<', '>', '>',
'>', '>', '>', '>', '<', '>', '>',
'<', '<', '<', '<', '<', '=', '!',

'>', '>', '>', '>', '!', '>', '>',
'<', '<', '<', '<', '<', '!', '='};
switch(c1)
{
/* i为下面array的横标 */
case '+' : i=0;break;
case '-' : i=1;break;
case '*' : i=2;break;
case '/' : i=3;break;
case '(' : i=4;break;
case ')' : i=5;break;
case '#' : i=6;break;
}

switch(c2)
{
/* j为下面array的纵标 */
case '+' : j=0;break;
case '-' : j=1;break;
case '*' : j=2;break;
case '/' : j=3;break;
case '(' : j=4;break;
case ')' : j=5;break;
case '#' : j=6;break;
}
return (array[7*i+j]); /* 返回运算符 */
}
/*操作函数 */
int Operate(int a,char op,int b)
{
switch(op)
{
case '+' : return (a+b);
case '-' : return (a-b);
case '*' : return (a*b);
case '/' : return (a/b);
}
return 0;
}
int EvalExpr()//主要操作函数
{
char c,theta,x; int m;
int a,b,i=0;
while(*ptr!='#'||OPTR.GetTop()!='#')
{
c = *ptr;
if(!In(c))
{
sscanf(ptr,"%d",&m);
OPND.Push(m);
while(!In(*ptr))
ptr++;
}
else
switch(Precede(OPTR.GetTop(),c))
{
case '<':
OPTR.Push(c);
*ptr++;
break;
case '=':
x=OPTR.Pop();
*ptr++;
break;
case '>':
theta=OPTR.Pop();
b=OPND.Pop();
a=OPND.Pop();
OPND.Push(Operate(a,theta,b));
break;
}
}
return OPND.GetTop();
}
int main( )
{

cout<<"请输入正确的表达式以'#'结尾:";
do{
gets(expr);
}while(!*expr);
OPTR.InitStack();
OPND.InitStack();
OPTR.Push('#'); /* 将#压入运算符栈 */
cout<<"表达式结果为:"<本知识有较深刻的了解，同时要求程序设计者有较强的思维和动手能力和更加了解编程思想和编程技巧。
这次课程设计让我有一个深刻的体会，那就是细节决定成败，编程最需要的是严谨，如何的严谨都不过分，往往检查了半天发现错误发生在某个括号，分号，引号，或者数据类型上。就像我在写EvalExpr()函数时，忘了指针的地址符值不用加*号，这一点小小的错误也耽误了我几十分钟，所以说细节很重要。
程序设计时，也不要怕遇到错误，在实际操作过程中犯的一些错误还会有意外的收获，感觉课程设计很有意思。在具体操作中这学期所学的数据结构的理论知识得到巩固，达到课程设计的基本目的，也发现自己的不足之出，在以后的上机中应更加注意，同时体会到C和C++语言具有的语句简洁，使用灵活，执行效率高等特点。发现上机的重要作用，特别算术表达式有了深刻的理解。

最后，感谢老师给予我们这次课程设计的机会，祝老师身体健康，工作顺利！
6、参考文献
1、《C++面向对象程序设计》 杜茂康 李昌兵 曹慧英 王永 编著
2、《算法与数据结构》 宁正元 赖贤伟 编著
3、《程序设计基础教程》 黄思先 刘必雄 主编
7、附录
表达式求值
在用高级语言编写的源程序中，一般都会有表达式。如何正确解释执行表达式是高级语言解释程序要处理的一个基本问题。作为栈应用的一个典型例子，我们讨论表达式的求值问题。
解释程序处理的表达式是一个字符序列，例如：
(5*(12-3)+5)/2
一般的表达式由操作数、运算符和界限符组成，称为三种单词。其中，操作数可以是直接量、常量、变量和函数引用等；运算符可以是算术运算符、关系运算符和逻辑运算符等；界限符有括号、分号等。
为了简化问题，只讨论一类简单的算术表达式，在这种算术表达式中，操作数只有直接量；运算符只有加(+)、减(-)、乘(*)、除(/) 4种；界限符只有括号。
表达式的求值规则是大家所熟悉的：先括号内后括号外；先再乘除、后加减；同级运算符从左往右计算。例如，上面提到的那个算术表达式，它的求值过程如下：
12-3=9 →R1
5*R1=45 →R2
R2+5=50 →R3
R3/2=25
其中，R1、R2、R3，表示中间结果。
当表达式中包含多个运算符时，各运算符号的计算顺序与它们的排列顺序一般是不相同的。因此，解释程序在从左往右扫描表达式时，不能遇到一个运算符就立刻进行相应的计算，否则将会得出错误的结果。
为了正确计算表达式的值，解释程序在工作时，要用到两个栈：一个是操作数栈，用于暂存操作数 (包括中间结果)；另一个是运算符栈，用于暂存运算符和括号。下面给出的算法就用了这样两个栈。
算法的基本思想是:
1．初始操作数栈置空，运算符栈以“#”为初始栈底元素；
2． 从左往右扫描以字符序列形式给出的算术表达式，在扫描过程中，对所遇字符进行单词种类的识别，根据所识别的单词种类，分以下几种情况处理。
（1）若是操作数，就将它转换成实数值，压人操作数栈中，继续扫描。
（2）若是运算符（ch）就将它与运算符栈的栈顶元素(pop)比较优先级，分三种情况：
Ⅰ.pop ch,则弹出运算符栈的栈顶元素，从操作数栈弹出两个操作数，进行一次计算，将计算结果压人操作数栈；
若ch是“#”，运算符栈顶元素也为“#”，整个求值过程结束 。此时操作数栈只有一个元素，它就是所求结果 。