数据结构课程设计表达式求值问题

目录

1概述................................................................2

1.1目的及意义..................................................................2

2系统分析..........................................................................2

2.1需求分析.....................................................................2

3概要设计..........................................................................2

3.1系统总体结构............................................................2

3.2程序算法图.................................................................2

4详细设计..........................................................................3

4.1中缀表达式转换为后缀表达式.............................................3

4.1.1求运算符优先级函数...............................................4

4.1.2输出队列.............................................................4

4.2后缀表达式的求值........................................................4

5运行与测试........................................................................5

5.1输入5

5.2输出结果：.............................................................5

6总结和心得........................................................................6

6.1心得与问题.................................................................6

6.2总结..................................................................6

参考文献............................................................................6

1概述

1.1目的及意义

我们在很早的时候就开始学习书写及计算表达式，可以说运用起来很熟练了，但有时候

并不想自己计算，交给计算器是时有的事，然而普通的计算器并不懂得优先级，给计算带来

了一定的不便。

本程序实现的目的是将人们习惯的中缀表达式转换为计算机所能理解的后缀表达式以

方便计算，最终得出我们所需要的正确的答案。

2系统分析

2.1需求分析

当我们需要进行一长串的计算时，各种运算符夹杂在一起，通过笔算很容易得出结果。

然而计算机并没有人脑那末聪明，它并不懂得先乘除后加减，有括号要先计算括号里面的，

它只知道从左到右的进行计算，这就造成为了计算机计算的失误，科学的计算是人们非常需

要

的计算工具。

3概要设计

3.1系统总体结构

整个系统结构如图3-1-1所示，结构非常清晰，程序顺序执行，首先提示用户输入需要

计算的表达式，经过转换得到后缀表达式，最后结果将数据显示到主屏幕上即可。

图3.1.1系统总体结构图

3.2程序算法图

本程序所用的数据结构类型是栈和队列。

2/11

首先提示用户输入中缀表达式，再利用程序将中缀表达式转换为后缀表达式，其中数字

入队列，算术运算符入栈。

图3.2.1程序算法图

4详细设计

4.1中缀表达式转换为后缀表达式

将中缀表达式转换为后缀表达式首先需要扫描中缀表达式，当遇到数字时，将其入队列，

当遇到运算符时，若是低优先级则直接入栈，若是高优先级则将低优先级运算符弹出，并

入队列，再将此次运算符入栈，最终形成后缀表达式

图4.1.1后缀表达式的转换

其伪代码算法如下：

switch(c){

caseOtocase:ErQeceQc)

ca^'(*:Rdi(S,c)

case*)t=Rp(S);

if(t!=r('&&t!=T#')

EnQueue(Q,t);

}v^iile(t!=f。&&S->tcp!-l);

ca®*+*||ca®—11ca^**'IIcase71:

while(Priority(c)<=Priority(GetTcp(S)))〃比较优先级

EnQueue(Q,Pop(S))

Push⑸c)

)

3/11

4.1.1求运算符优先级函数

算术运算符入栈时必须考虑运算符的优先级，才干形成正确的后缀表达式，当读到运算

符时，将栈中所有优先级高于或者等于该运算符的运算符弹出，送至输出队列中，再将当前

运算符入栈；当读入左括号时，即入栈；当读到右括号时，将挨近栈顶的第一个左括号上

面的

运算符全部挨次弹出，送至输出队列中，再删除栈中的左括号。

通过返回值的大小代表优先级的大小，其伪代码算法如下：

switch(cp){

casef(f|lease*#*:O;h®k;

ca^*-f||ca^l/kxeek;

case*11ca^，八return2;teak;

)

4.1.2输出队列

之中缀表达式转换成后缀表达式之后，需要输出后缀表达式，也就是当前队列，只需要

让头指针遍历输出数据即可。

其伪代码如下：

x=Q->data[Q->front-H-];

4.2后缀表达式的求值

由于在将中缀表达式转换为后缀表达式时已经将运算符安排在了合适的位置，在后缀表

达式中不仅不需要括号，而且还彻底免除了运算符优先规则，仅需从左到右计算即可。

其伪代码如下：

while(!QueueEnpty(Q)){

ch=DeQueue(Q)

if(ch>='0'&&ch<=g)

⑸dyU;)〃数字字符到数值的转换

else{

y=Pop(S),x=Pop(S)

switch(ch){

11

case+：Pu^i(Szx+y);break;

case:Rash(S,xf);break;

case:Push(Szx*y);break;

ca^71:Pu±i(S,Wy);break;

)

}

4/11

5运行与测试

5.1输入表达式:

输入一个中缀表达式:

5.2输出结果:

输出后缀表达式及其结果:

5/11

6总结和心得

6.1心得与问题

在本次实验中，遇到的心得：

①为什么有判空队列不需要判空栈？因为当S->top=-l时栈变为空，不需要单独写一

个函数出来判断。

②后缀表达式的求值中，Push(S,ch-，O，)中的ch-。是什么意思？因为输入表达式时数

字是以字符的形式存储的，当进行计算式需要字符到数值的转换。

③中缀表达式转换为后缀表达式时为什么要用Push(S,W)将#压入栈底？

④后缀表达式的求值中，SeqStackvs的作用是什么？为什么不用vs会出错？

⑤调用后缀表达式进行计算时，最终计算结果是放在栈中的，但为什么返回栈顶元素

时总是指向空？因为之前调用了Dequeue(Q),导致front发生了改变，相当于队列

被删除了，所以再调用时就为空了，解决方法有多种，比如复制队列，我采取了一

个简单的方法，在调用了CTPostExp(Q)后不忙着输出后缀表达式，继续调用

CPostExp(Q),在CPostExp(Q)中使用Dequeue(Q)时顺便就将后缀表达式输出，这样

就避免了队列第二次调用时已经被删除的窘境。

6.2总结

本次试验中内存出错的情况比较多，比如在输出后缀表达式时虽然结果正确，但后面还

有不少“烫烫…”，在计算后缀表达式时，返回值总是没有，等等，但通过不断地调试这些

问题都得以解决。

通过本次实验，加强了对栈和队列的存储结构的理解，特别是栈的先进后出的结构有了

更深的了解。

参考文献

[1]苏仕华等.数据结构课程设计.机械工业出版社.2005.05

[2]严蔚敏，吴伟明.数据结构(C语言版).清华大学出版社.2022

[3]谭浩强.C程序设计(第三版).清华大学出版社.2005

附加程序代码：

#include<stdio.h>

♦defineStacksize100

#defineQueueSize100

typedefcharDataType;

typedefstruct

{

6/11

dhardata[100];

intfront,rear;

}SeqQueue;〃定义队列类型

typedefstruct

{

EataTypedata[100];

inttcp;

}SeqStack;〃栈类型的定义

〃初始化队列

voidInitQueue(Seqiieue*Q)

(

Q->front=0;

Q->rear=0;〃头部和尾部份别赋值为0

}

〃清空队列

intQueueEnpty(SeqQueue*Q)

(

returnQ->rear=Q->frcnt;〃队列的头指针等于尾指针

)

〃入队列

voidEnQueue(SeqQueue*Q,DataTypex)

{

if((Q->rear+l)%QueueSize=Q->front)//判断队列是否装满

队列溢出

else

(

Q->data[Q->rear]“

Q->rear=(Q->rear+l)%QueueSize;

)

)

〃输出队列

charDeQueue(SeqQueue*Q)

{

charx;

x=Q->data[Q->front];

Q->front++;

returnx;

}

//祕台化栈

voidInitStack(Sec^tack*S)

(

S->tcp=-l;

}

7/11

〃入栈

voidPush(SeqStack*S,DataTypex)

{

if(S->tcp=StackSize-l)

栈溢出

else

(

S->tc^->tcp^l;//栈顶指针指向新插入的数据

S-X^ta[S->tcp]=x;

)

}

〃出栈

DataTypePop(SeqStack*S)

{

if(S->tcp=-l)

空栈

else

returnS->data[S->tcp-];

}

//取栈顶元素

DataTypeGetTop(SeqStack*S)

(

if(S->tcp=l)

栈空

else

returnS-X^ta[S->tcp];

}

〃求运算符优先级函数

intPriority(EataTypeop)

(

switch(cp)

(

case1(*:

case:retum0;break;

ca^

ca^中l;br^k;

ca^

case'/〔return2;br^k;

)

)

//中缀表达式转换为后缀表达式

voidCTPostExp(Sec^ueue*Q)

SeqStackOS;〃运算符栈

8/11

charczt;

SeqStack*S;

S=&OSf

InitStack(S);

R^(S,'#');〃压入栈底元素#

do〃扫描中缀表达式

(

c=getchar();

switch(c)

{

曰k;〃去除空格符

ca^'01:

casefl*:

ca^*2*:

ca^,3,:

ca^⑷：

ca^r51:

ca^*6,:

ca^7:

ca^8:

ca^9:

EnQueue(Q,c);break;

case'('：RJ©I(S,C);break;

ca^

ca^

do

(

t=Psp(S);

if(t!=»(f

EnQueue(Q,t);

}vhile(t!=*(*&&S->tcpH);break;

case

ca^

ca^

ca^71:

vhile(Priority(c)<=Priority(fetTcp(S)))〃比较优先级

{

t=Pop(S);

EnQueue(Qzt);

)

Push(S,c);

break;

}

}vbile(c!=,#');

9/11

〃后缀表达式的求值

intCPostExp(SeqQueue*Q)

(

SeqStackvs,*S;

charch;

intxzy;

S=&vs;〃有什么用

InitS