数据结构表达式求值(中缀)实验.doc

江西理工大学软件学院

《数据结构》课程设计报告

2012—2013学年第一学期

课程名称 数 据 结 构
设计题目 表达式求值
专业班级
姓 名
学 号
指导教师

2012年 11 月 30日

目 录

一．设计题目…………………………………………………….…..……………..3

二．需求分析………………………………………………..………………..…….3

2.1问题描述……………………………………………………………..……..3
2.2表达式程序分析…………………………………………………..………..3

三．概要设计…………………………………………………..……..…………….3

3.1基本思想……………………………………………………..……………..3
3.2栈的抽象数据类型定义…………………………………..………………..4

四．基本算法…………………………………………………………….....………4

4.1基本操作思想………………………………………………………………4
4.2基本操作……………………………………………………………………5

五．测试结果………………………………………………………………………7

六．源代码…………………………………………………………………………8

七．心得体会………………………………………………………………………12
一 设计题目
表达式求值（中缀）

二 需求分析
2.1 问题描述：在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行，在程序设计时，借助栈实现。
2.2 表达式求值程序分析：主要利用栈和数组，把运算的先后步骤进行分析并实现简单的运算，以字符列的形式从终端输入语法的正确的、不含变量的整数表达式。利用已知的算符优先关系，实现对算术四则运算的求值，在求值中运用栈、运算栈、输入字符和主要操作的变化过程。该程序相当于一个简单的计算机计算程序，只进行简单的加减乘除和带括号的四则运算。

三 概要设计
3.1 基本思想（中缀表达式求值）
要把一个表达式翻译成正确求值的一个机器指令序列，或者直接对表达式求值，首先要能够正确解释表达式，要了解算术四则运算的规则即：
a先乘除后加减；
b从左到右计算；
c 先括号内，后括号外。
下表定义的运算符之间的关系:

b
a
+
-
*
/
（
）
#
+
>
>
<
<
<
>
>
_
>
>
<
<
<
>
>
*
>
>
>
>
<
>
>
/
>
>
>
>
<
>
>
(
<
<
<
<
<
=

)
>
>
>
>

>
>
#
<
<
<
<
<

=
为了实现运算符有限算法，在程序中使用了两个工作栈。分别是：运算符栈OPTR,操作数栈OPND.
基本思想：

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

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

3.2 栈的抽象数据类型的定义：

ADT Stack{
数据对象：D={ai| ai∈IntegerSet，i=1，2，…，n，n≥0}
数据关系：R1={〈ai-1，ai〉|ai-1， ai∈D， i=1，2，…，n}
约定an端为栈顶，ai端为栈底
四．操作算法

4.1基本操作思想：
InitStack(&S)
操作结果：构造一个空栈S。
DestroyStack(&S)
初始条件：栈S已存在。
操作结果：栈S被销毁。
ClearStack(&S)
初始条件：栈S已存在
操作结果：将S清为空栈。
StackEmpty（S）
初始条件：栈S已存在。
操作结果：若栈S为空栈，则返回True，否则返回False。
StackLength（S）
初始条件：栈S已存在。
操作结果：返回S的元素个数，即栈的长度。
GetTop（S，&e）
初始条件：栈S已存在且非空。
操作结果：用e返回S的栈顶元素。
Push（&S，e）
初始条件：栈S已存在。
操作结果：插入元素e为新的栈顶元素。
Pop（&S，&e）
初始条件：栈S已存在且非空。
操作结果：删除S的栈顶元素，并用e返回其值。
StackTraverse（S，visit（））
初始条件：栈S已存在且非空。
操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit（）。一旦visit（）失败，则操作失败。
}ADT Stack

4.2 基本操作
中缀表达式求值，在转换和计算中主要用到了下列几个函数
1) char Precede(char t1, char t2)
作用：判断运算符t1和t2的优先关系。
如：case '+':
case '-':
if(t1=='('|| t1=='#')
f='<'; //t1t2
break;
2）bool IsOperator(char c)
作用：判断c是否为7种运算符之一
bool IsOperator(char c) //判断c是否为7种运算符之一
{
switch(c)
{
case '+':
case '-':
case '*':
case '/':
case '(':
case ')':
case '#':
return true;
default:
return false;
}
}
3）int Operate(int a, char oper, int b)
作用：
int Operate(int a, char oper, int b)
{
switch(oper)
{
case '+':
return a+b;
case '-':
return a-b;
case '*':
return a*b;
default:
break;
}
return a/b;
}
4）int EvaluateExpression()
作用：中缀表达式求值的算法
int EvaluateExpression()
{
stack OPTR, OPND;//设置操作数栈和操作符栈
int a,b,d,x;
char c;
OPTR.push('#');
c=getchar();
x=OPTR.top();

while(c!='#'||x!='#')
{
if(IsOperator(c))
{
switch(Precede(x,c))
{
case'<':
OPTR.push(c);
c = getchar();
break;
case'=':
x=OPTR.top();
OPTR.pop();
c = getchar();
break;
case'>':
x=OPTR.top();
OPTR.pop();

b=OPND.top();
OPND.pop();

a=OPND.top();
OPND.pop();

OPND.push(Operate(a,x,b));
}
}
else if(c>'0'&&c<='9')
{
d=0;
while(c>='0'&&c<='9')
{
d = d*10+c-'0';
c = getchar();
}
OPND.push(d);
}
else
{
cout << "出现非法字符" << endl;
exit( 0 );
}
x=OPTR.top();
}
x=OPND.top();

if(OPND.empty())
{
cout << "表达式不正确#" << endl;
exit( 0 );
}
return x;
}

五 测试结果

六．源代码 中缀表达式求值.cpp

#include
#include
using namespace std;

int EvaluateExpression();

int main()
{
cout << "请输入算术表达式,负数要用(0--正数)表示\n";
cout << EvaluateExpression() << endl;
return 0;
}

char Precede(char t1, char t2)
{ //判断t1,t2两符号的优先关系('#'用'#'代替)
char f;
switch(t2)
{
case '+':
case '-':
if(t1=='('|| t1=='#')
f='<'; //t1t2
break;
case '*':
case '/':
if(t1=='*'||t1=='/'||t1==')')
f='>'; //t1>t2
else
f='<'; //t1
cout << "缺乏左括号" << endl;
exit( 0 );
default: f='>'; //t1>t2
}
break;
case '#':
switch(t1)
{
case '#':
f= '='; //t1=t2
break;
case '(':
cout << "缺乏右括号" << endl;
exit( 0 );
default: f='>'; //t1>t2
}
}
return f;
}

bool IsOperator(char c) //判断c是否为7种运算符之一
{
switch(c)
{
case '+':
case '-':
case '*':
case '/':
case '(':
case ')':
case '#':
return true;
default:
return false;
}
}

int Operate(int a, char oper, int b)
{ //做运算a theta b,返回运算结果
switch(oper)
{
case '+':
return a+b;
case '-':
return a-b;
case '*':
return a*b;
default:
break;
}
return a/b;
}

int EvaluateExpression()
{
stack OPTR, OPND;//设置操作数栈和操作符栈
int a,b,d,x;
char c;
OPTR.push('#');
c=getchar();
x=OPTR.top();

while(c!='#'||x!='#')
{
if(IsOperator(c))
{
switch(Precede(x,c))
{
case'<':
OPTR.push(c);
c = getchar();
break;
case'=':
x=OPTR.top();
OPTR.pop();
c = getchar();
break;
case'>':
x=OPTR.top();
OPTR.pop();

b=OPND.top();
OPND.pop();

a=OPND.top();
OPND.pop();

OPND.push(Operate(a,x,b));
}
}
else if(c>='0'&&c<='9')
{
d=0;
while(c>='0'&&c<='9')
{
d = d*10+c-'0';
c = getchar();
}
OPND.push(d);
}
else
{
cout << "出现非法字符" << endl;
exit( 0 );
}
x=OPTR.top();
}
x=OPND.top();

if(OPND.empty())
{
cout << "表达式不正确#" << endl;
exit( 0 );
}
return x;
}

} while(i错误发生在某个括号，分号，引号，或者数据类型上。
程序设计时，也不要怕遇到错误，在实际操作过程中犯的一些错误还会有意外的收获，感觉课程设计很有意思。在具体操作中这学期所学的数据结构的理论知识得到巩固，达到课程设计的基本目的，也发现自己的不足，在以后的上机中应更加注意，同时体会到C++具有的语句简洁，使用灵活，执行效率高等特点。

我通过这次的课程设计，进一步熟悉掌握栈的定义和应用，比如构造空栈，清空栈，求栈的大小，压栈和出栈操作，栈的遍历等等。对于算符优先算法、中缀变后缀的算法、后缀表达式求值的算法以及中缀表达式求值的算法都有了更深刻的理解，现在我已经能够应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，整合程序段，编写程序求解表达式求值的问题。初步掌握了设计的一般步骤与方法，提高了综合运用所学的理论知识和方法独立分析和解决问题的能力。

12 / 12