算术表达式求值演示-课程设计报告

目 录

第一章 概述„„„„„„„„„„„„„„„„„„„„„„„1 第二章 系统分析„„„„„„„„„„„„„„„„„„„„„1 第三章 概要设计„„„„„„„„„„„„„„„„„„„„„2 第四章 详细设计„„„„„„„„„„„„„„„„„„„„„5 第五章 运行与测试„„„„„„„„„„„„„„„„„„„„13 第六章 总结与心得„„„„„„„„„„„„„„„„„„„„16 参考文献 „„„„„„„„„„„„„„„„„„„„„„„„16

第一章 概述

课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。《数据结构》是一门重要的专业基础课，是计算机理论和应用的核心基础课程。

数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。

在这次的课程设计中我选择的题目是算术表达式求值演示。表达式计算是实现程序设计语言的基本问题之一，也是栈的应用的一个典型例子。设计一个程序，演示用算符优先法对算术表达式求值的过程。深入了解栈和队列的特性，以便在解决实际问题中灵活运用它们，同时加深对这种结构的理解和认识。

第二章 系统分析

1． 以字符列的形式从终端输入语法正确的、不含变量的整数表达式。利用已知的算符优先关系，实现对算术四则混合运算表达式的求值，并仿照教科书的例子在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。

2． 一般来说，计算机解决一个具体问题时，需要经过几个步骤：首先要从具体问题抽象出一个适当的数学模型，然后设计一个解决此数学模型的算法，最后编出程序，进行测试，调试直至得到想要的答案。对于算术表达式这个程序，主要利用栈，把运算的先后步骤进行分析并实现简单的运算！为实现算符优先算法，可以使用两个栈，一个用以寄存运算符，另一个用以寄存操作数和运算结果。

3． 演示程序是以用户于计算机的对话方式执行，这需要一个模块来完成使用者与计算机语言的转化。 4． 程序执行时的命令：

本程序为了使用具体，采用菜单式的方式来完成程序的演示，几乎不用输入什么特殊的命令，只需按提示输入表达式即可。（要注意输入时格式，否者可能会引起一

1

些错误） 5. 测试数据。

第三章 概要设计

一个算术表达式中除了括号、界限符外，还包括运算数据和运算符。由于运算符有优先级别之差，所以一个表达式的运算不可能总是从左至右的循序执行。每次操作的数据或运算符都是最近输入的，这与栈的特性相吻合，故本课程设计借助栈来实现按运算符的优先级完成表达式的求值计算。

算法设计

1、算符的优先级比较函数Compare(char m,char n) 算法的基本思想：

通过已知的算符间的优先关系写出算符的优先级算法。任意两个相继出现的

算符c1和c2之间的优先关系至多是下面3种关系之一：

c1c2 c1的优先权高于c2

算法步骤:

Step1:如果输入符号为“+”或“-”

1.1如果栈顶元素为“(”、“#”,此时栈顶符号优先级低，返回“<” 1.2 否则，栈顶符号优先级高,返回“>” Step2:如果输入符号为“*”或“/”

2.1 如果栈顶元素为“)”、“*”、“/”,此时栈顶符号优先级高，返回“>”

2.2 否则，栈顶符号优先级低,返回“<”

Step3: 如果输入符号为“(”, 则直接返回“<” Step4:如果输入符号为“)”

4.1 如果栈顶元素为“(”,此时优先级同，返回“=” 4.2 否则，栈顶符号优先级高,返回“>” Step5:输入符号为其他

5.1 栈顶元素为“#”,此时优先级同，返回“=” 5.2 否则，栈顶符号优先级高,返回“>”

2、确定如何入栈函数evaluate(SqStack1 &S1,SqStack2 &S2) 算法的基本思想：

2

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

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

Step1:将‘#’入栈，作为低级运算符 Step2:输入不含变量的表达式（以#结束!） Step3:如果c!='#'||GetTop1(S1)!='#'

3.1如果输入的字符如果不是运算符号，则继续输入直到输入的是运算符为止，将非运算符转换成浮点数 3.2 如果输入的是运算符

a、遇到运算符，则将之前输入的操作数进栈 b、比较运算符的优先级

1) 栈顶元素优先级低，则入栈且继续输入 2) 栈顶元素优先级相等，脱括号并接收下一字符 3) 栈顶元素优先级高，则退栈并将运算结果入栈

Step4:显示表达式最终结果

程序包含三个模块

(1) 主程序模块，其中主函数为

void main{

}

(2) 表达式求值模块——实现具体求值。 (3) 表达式转换模块——实现转换。

各个函数之间的调用关系

3

输入表达式；

根据要求进行转换并求值； 输出结果；

主函数 数据输入 表达式求值 表达式转换 输出 输出

栈的抽象数据类型定义 ADT SqStack{

数据对象：D={ai| ai ∈ElemSet,i=1,2,3„„，n,n≥0} 数据关系：R1={| ai-1,ai ∈D,i=1,2,3,„„，n}

约定其中ai端为栈底，an端为栈顶。

操作集合：

(1)void InitStack1(SqStack1 &S1);//声明栈建立函数 (2)void InitStack2(SqStack2 &S2);//声明栈建立函数

(3)void evaluate(SqStack1 &S1,SqStack2 &S2);//确定如何入栈函数 (4)void Push1(SqStack1 &S1,char e);//声明入栈函数 (5)void Push2(SqStack2 &S2,float e);//声明入压栈函数 (6)char GetTop1(SqStack1 &S1);//声明取栈顶元素函数 (7)float GetTop2(SqStack2 &S2);//声明取栈顶元素函数 (8)char Pop1(SqStack1 &S1);//声明出栈函数 (9)float Pop2(SqStack2 &S2);//声明出栈函数 (10)char Compare(char m,char n);//声明比较函数

(11)float Operate(float a,char rheta,float b);//声明运算函数 (12)void DispStack1(SqStack1 &S1);//从栈底到栈顶依次输出各元素 (13)void DispStack2(SqStack2 &S2);//从栈底到栈顶依次输出各元素 }ADT SqStack

4

第四章 详细设计

源程序

#include using namespace std;

#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10

typedef struct //运算符栈 {

char *base; char *top;

int stacksize; }SqStack1;

typedef struct //运算数栈 {

float *base; float *top; int stacksize; }SqStack2;

void InitStack1(SqStack1 &S1);//声明栈建立函数 void InitStack2(SqStack2 &S2);//声明栈建立函数

void evaluate(SqStack1 &S1,SqStack2 &S2);//确定如何入栈函数 void Push1(SqStack1 &S1,char e);//声明入栈函数 void Push2(SqStack2 &S2,float e);//声明入压栈函数 char GetTop1(SqStack1 &S1);//声明取栈顶元素函数 float GetTop2(SqStack2 &S2);//声明取栈顶元素函数 char Pop1(SqStack1 &S1);//声明出栈函数 float Pop2(SqStack2 &S2);//声明出栈函数 char Compare(char m,char n);//声明比较函数

float Operate(float a,char rheta,float b);//声明运算函数 void DispStack1(SqStack1 &S1);//从栈底到栈顶依次输出各元素 void DispStack2(SqStack2 &S2);//从栈底到栈顶依次输出各元素

/*主函数*/

void main()

5

{

SqStack1 S1;//定义运算符栈 SqStack2 S2;//定义运算数栈

//freopen(\"data1.in\ //freopen(\"data1.out\

InitStack1(S1);//调用栈建立函数 InitStack2(S2);//调用栈建立函数

evaluate(S1,S2);//调用确定如何入栈函数 cout<<\"按任意键结束!\"</*运算符栈函数*/

void InitStack1(SqStack1 &S1)//构造一个空栈S1 {

S1.base=(char *)malloc(STACK_INIT_SIZE *sizeof(char)); if(!S1.base)cout<<\"存储分配失败！\";//存储分配失败 S1.top=S1.base;

S1.stacksize=STACK_INIT_SIZE; }

void Push1(SqStack1 &S1,char e)//入栈 {

if(S1.top-S1.base>=S1.stacksize)//如果栈满，追加存储空间 {

S1.base=(char

*)realloc(S1.base,(S1.stacksize+STACKINCREMENT)*sizeof(char)); if(!S1.base) cout<<\"存储分配失败！\"; else {

S1.top=S1.base+S1.stacksize;

S1.stacksize=S1.stacksize+STACKINCREMENT; } }

*S1.top=e;S1.top=S1.top+1;//将元素压入栈中，指针上移 }

char GetTop1(SqStack1 &S1)//取栈顶元素

6

{

char e;

if(S1.top==S1.base)cout<<\"\\n\\\运算符栈已空!\\n\"; else e=*(S1.top-1); return e; }

void DispStack1(SqStack1 &S1)//从栈底到栈顶依次输出各元素 {

char e,*p;

if(S1.top==S1.base)cout<<\" \"; else {

p=S1.base;

while(pe=*p; p++;

cout<char Pop1(SqStack1 &S1)//出栈 {

char e;

if(S1.top==S1.base)cout<<\"\\n\\\运算符栈已空!\\n\"; e=*(--S1.top); return e; }

/*运算数栈函数*/

void InitStack2(SqStack2 &S2)//构造一个空栈S2 {

S2.base=(float *)malloc(STACK_INIT_SIZE *sizeof(float)); if(!S2.base)cout<<\"存储分配失败！\";//存储分配失败 S2.top=S2.base;

S2.stacksize=STACK_INIT_SIZE; }

void Push2(SqStack2 &S2,float e)//入栈 {

7

if(S2.top-S2.base>=S2.stacksize)//栈满，追加存储空间 {

S2.base=(float

*)realloc(S2.base,(S2.stacksize+STACKINCREMENT)*sizeof(float)); if(!S2.base)cout<<\"存储分配失败！\"; else {

S2.top=S2.base+S2.stacksize;

S2.stacksize=S2.stacksize+STACKINCREMENT; } }

*S2.top=e;S2.top=S2.top+1;//将元素e入栈，指针上移 }

void DispStack2(SqStack2 &S2)//从栈底到栈顶依次输出各元素 {

float e,*p;

if(S2.top==S2.base)cout<<\" \"; else {

p=S2.base;

while(pe=*p; p++;

cout<float GetTop2(SqStack2 &S2)//取栈顶元素 {

float e;

if(S2.top==S2.base) cout<<\"\\n\\运算数栈已空!\"; else e=*(S2.top-1); return e; }

float Pop2(SqStack2 &S2)//出栈 {

float e;

if(S2.top==S2.base)cout<<\"\\n\\运算数栈已空!\";

8

e=*(--S2.top); return e; }

/*确定如何入栈函数*/

void evaluate(SqStack1 &S1,SqStack2 &S2) {

char c; float t,e;

int n=0,i=1,j=0,k=0,l=0; char ch[STACK_INIT_SIZE]; int s=1;

int flag=0,flag2=0; float p1,p2; char ch1;

Push1(S1,'#');//将'#'入栈，作为低级运算符

cout<<\"●请输入不含变量的表达式（以#结束!）：\\n \"; cin>>ch; c=ch[0];

cout<<\"\\n●对表达式求值的操作过程如下：\"

<<\"\\n________________________________________________________________________________\\n\"

<<\"步骤\运算符栈S1\运算数栈S2\输入字符\\主要操作\"; while(c!='#'||GetTop1(S1)!='#') {

cout<<\"\\n________________________________________________________________________________\\n\"; cout<DispStack1(S1);cout<<\"\\\"; DispStack2(S2); cout<<\"\\\"; if(flag==1) {

k--; flag=0; } if(flag2) {

9

k+=flag2; flag2=0; }

for(l=0;lfor(j=k;ch[j]!='\\0';j++) cout<if(ch[k]!='#'&&flag!=1) {k++;flag=0;} as:

if(!(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')'||c=='#'))

{//输入的字符如果不是运算符号，则继续输入直到输入的是运算符为止，将非运算符转换成浮点数

if(!(c=='.')&&n>=0) {

e=float(c-48); n++;

if(n==1)t=e;

else if(n>1)t=t*10+e; c=ch[s++]; }

if(n==-1) {

e=float(c-48); t=t+e/10; c=ch[s++]; }

if(c=='.') {

n=-1;

c=ch[s++]; }

if((c>='0'&&c<='9')||c=='.') {

flag2++; goto as; }

if(c<'0'||c>'9') {

Push2(S2,t); }

cout<<\"\\Push2(S2,\"<10

else//输入的是运算符 {

n=0;//非运算型数据计数器清零

switch(Compare(GetTop1(S1),c))//比较运算符的优先级 {

case '<'://栈顶元素优先级低，则入栈且继续输入 Push1(S1,c);

cout<<\"\\Push1(S1,\"<case '='://栈顶元素优先级相等，脱括号并接收下一字符 Pop1(S1);

cout<<\"\\Pop1(S1)\"; c=ch[s++]; break;

case '>'://栈顶元素优先级高，则退栈并将运算结果入栈 p1=Pop2(S2); p2=Pop2(S2); ch1=Pop1(S1);

Push2(S2,Operate(p2,ch1,p1));

cout<<\"\\Operate(\"<cout<<\"\\n________________________________________________________________________________\\n\";

cout<cout<<\"#\"<<\"\\\"<<\"RETURN(GETTOP(S2))\";

cout<<\"\\n________________________________________________________________________________\\n\";

if(S2.top-1==S2.base)//显示表达式最终结果

cout<<\"\\n●表达式的结果为：\"<char Compare(char m,char n)//运算符的优先级比较 {

11

if(n=='+'||n=='-')//输入符号为\"+\"、\"-\" {

if(m=='('||m=='#')return '<';//栈顶元素为\"(\"、\"#\此时栈顶符号优先级低，返回\"<\"

else return '>';//否则，栈顶符号优先级高,返回\">\" }

else if(n=='*'||n=='/')//输入的符号为\"*\"、\"/\" {

if(m==')'||m=='*'||m=='/')return '>';//栈顶元素为\")\"、\"*\"、\"/\此时栈顶符号优先级高，返回\">\"

else return '<';//否则，栈顶符号优先级低,返回\"<\" }

else if(n=='(')return'<';//输入的符号为\"(\则直接返回\"<\" else if(n==')')//输入的符号为\")\" {

if(m=='(')return'=';//栈顶元素为\"(\此时优先级同，返回\"=\" else return '>';//否则，栈顶符号优先级高,返回\">\" }

else //输入符号为其他 {

if(m=='#')return'=';//栈顶元素为\"#\此时优先级同，返回\"=\" else return '>';//否则，栈顶符号优先级高,返回\">\" } }

float Operate(float a,char theta,float b)//运算函数 {

float tmp=0;

if (theta=='+')tmp=a+b;//从运算符栈取出的符号为\"+\"，则运算数栈的两元素相加，并返回 else if(theta=='-')tmp=a-b;//从运算符栈取出的符号为\"-\"，则运算数栈的两元素相减，并返回 else if(theta=='*')tmp=a*b;//从运算符栈取出的符号为\"*\"，则运算数栈的两元素相乘，并返回

else if(theta=='/') //从运算符栈取出的符号为\"/\"，则运算数栈的两元素相除，并返回 {

if(b==0) cout<<\"\\n表达式出错!除数不能为0!\\n\"; else tmp=a/b; }

return tmp; }

12

第五章 运行与测试

1．结构分析:

栈中的数据节点是通过数组来存储的。因为在C语言中数组是用下标从零开始的，因此我们在调用他们的数据是要特别注意。指针变量的值要么为空(NULL)，不指向任何结点；要么其值为非空，即它的值是一个结点的存储地址。注意，当P为空值时，则它不指向任何结点，此时不能通过P来访问结点，否则会引起程序错误。如果输入的数字不符合题目要求，则会产生错误结果。 2．算法的时空分析：

时间和空间性能分析：时间上，对于含n个字符的表达式，无论是对其进行合法性检测还是对其进行入栈出栈操作n次，因此其时间复杂度为O(n)。空间上，由于是用数组来存储输入的表达式，用栈来存储运算中的数据和运算符，而栈的本质也用到的数组，数组在定义时必须确定其大小。在不知表达式长度的情况下确定数组的长度确非易事，此时极易造成空间的浪费，因此空间性能不是很好。

3．用户使用说明：

1．使用环境：Visual C++ 6.0.

2．操作要求：程序运行后,用户根据提示输入0—9之间的数字或者是字符以进入相应的功能处理函数。程序调用建表功能函数后，用户将按照规定的方式输入你所要计算的表达式，最后可以计算出结果。

4. 上机调试

1、语法错误：计算器的设计虽然不是很难，但由于设计一个好的计算器要考虑很多问题而且还用到的栈，因此比较的繁琐以至使源程序相当的长，也因此导致了很多的语法错误和逻辑错误。这些错误主要有指针空间的分配，指针的错误指向，等号与赋值号的混淆，大括号的不正确匹配，头文件的不正确包含，变量的不定义便使用或局部变量全局使用„„但语法错误不像逻辑错误那样很难发现，它可以根据编译环境的提示和一些经验便可以很快解决。

1程序初步完成以后，进行测试发现出现死循环，观察显示结果发现，2、逻辑错误：○

栈中的数据和运算符一直都没有出栈。既然没有出栈，那么根据以前程序调试的经验，

13

该问题应该出在栈的出栈操作中，于是找到进行出栈操作的函数，经仔细检查发现，原来将return语句写到了top—语句的前面去了，而return语句有跳出的作用，当它一旦执行，其后的语句都会被忽略而得不到执行。因此将它们调换顺序，正确写法见源程序。2再次调试程序，输入一个测试表达式（如1+2*5#），发现结果是10，而且通过将栈中○

的数据进行显示发现1并未出栈，而操作符栈的“+”未进行运算便出了栈。通过步步跟踪来走程序发现，原来错误出在优先级判断的条件语句里面，在取出栈顶元素与刚读入的运算符进行比较时，当刚读入的运算符优先级高于栈顶的运算符时，直接将刚读入的运算符入栈，而刚从栈顶取出的一个运算符却抛之不管，当然会出错，因此应将刚取出3经过以上的修改，用一些简单的表达式进行的先入栈，然后将刚读入的运算符入栈。○

测试发现能得出正确结果，但当输入像-7+1#或-（1+2*3）#这样的开头带负号的表达式时，程序计算的结果与实际相差甚远。因此应将开始的“-”作为负号而不是减号，并进4当输入的计算数据超过9时（如12+56#），计算结果又出错，通过输行特殊的处理。○

出栈中的数据进行观察发现栈将12分成了1和2，将56分成了5和6进行分别存储。这显然是错误的。通过检查程序发现输入语句用的是c=getchar()，该输入语句每次只能得到一个字符，12是两个字符1和2，因此会出现上面的情况。于是将输入改为字符串输5通入并存入一个字符数组中，然后将字符串转换成相应的运算符和数据以参与计算。○过上面的更改，运行程序发现已经能接受大于9的数据以参与运算了；但当输入一些特殊非运算用符和字母时，又出现了意想不到的错误结果，因此程序采用了相应的算法，在使用刚输入的表达式字符串前，进行严格的检测。 5. 程序运行测试

14

6. 结果分析

以上调试结果是正确的。能够实现各个符号优先级先后顺序的运算，根据符号优

先级（、）、+、-、*、/ ，如此顺序进行运算，实现了基本表达式运算的功能。 a. 可以完成四则混合运算 b. 可以完成实数的四则运算 c. 可以检查表达式的输入是否正确 d. 演示表达式的求值的操作过程

15

第六章 总结与心得

数据结构的研究不仅涉及到计算机硬件的研究，而且和计算机软件的研究有着更密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。在研究信息检索时也必须考虑如何组织数据，以便使查找和存取数据元素更为方便。

在课程设计中，应该力求算法简明易懂，而易于转换为上机程序；如果程序反复多次使用，则应该尽可能选用快速的算法；如果待解决的问题数据量极大，机器的存储空间较小，则在编写算法时应该考虑如何节省空间。以后在编写程序时就应该注意到所编写程序的时间复杂度，以及是否运用了良好的算法，而不能只是像以前编写程序时单纯使用C语言的知识，要充分考虑程序的性能，争取编写出更优良的程序来。

经过两个星期的实际操作和搜索相关资料，终于让我完成了任务。让我对《数据结构》C语言有了更进一步的认识和了解，也让我知道，要想学好它要重在实践，理论与实际应用相结合，提高了自己组织数据及编写大型程序的能力，培养了基本的、良好的程序设计技能以及合作能力。通过实际操作，我也发现我的好多不足之处：

(1)用栈的结构来解决表达式的求值，首先要解决的问题是如何将人们习惯书写的表达式转换成计算机容易处理的表达式。开始有些茫然，后来通过结合课本和同学的帮助完成了该课题。

(2)对一些看似简单的东西掌握不够熟练，比如由于函数的调用参数问题不熟而造成了调试的困难。对于语法的掌握也欠缺成熟，需要进一步掌握。

(3)栈的结构理解不够清晰，造成了设计程序时理不清头绪，需要对数据结构有更深层次的理解。

参考文献:

[1] 严蔚敏、吴伟民主编 《数据结构》（C语言版） 清华大学出版社 2002 [2] 殷人昆等著 《数据结构》（C++版） 清华大学出版社 2001 [3] 金远平著 《数据结构》（C++描述） 清华大学出版社 2005 [4] 许卓群等著 《数据结构与算法》 高等教育出版社 2004 [5] Frank M.Carrano 等著 《数据结构与Ｃ++高级教程》 清华大学出版社 2004 [6] 严蔚敏、吴伟民 《数据结构习题集》（C语言版）清华大学出版社 2002

16