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

1/1数据结构课程设计表达式求值问题名目

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)

1概述

1.1目的及意义

我们在很早的时候就开头学习书写及计算表达式，可以说运用起来很娴熟了，但有时候并不想自己计算，交给计算器是时有的事，然而一般的计算器并不懂得优先级，给计算带来了肯定的不便。

本程序实现的目的是将人们习惯的中缀表达式转换为计算机所能理解的后缀表达式以便利计算，最终得出我们所需要的正确的答案。

2系统分析

2.1需求分析

当我们需要进行一长串的计算时，各种运算符夹杂在一起，通过笔算很简单得出结果。然而计算机并没有人脑那么聪慧，它并不懂得先乘除后加减，有括号要先计算括号里面的，它只知道从左到右的进行计算，这就造成了计算机计算的失误，科学的计算是人们特别需要的计算工具。

3概要设计

3.1系统总体结构

整个系统结构如图3-1-1所示，结构特别清晰，程序挨次执行，首先提示用户输入需要计算的表达式，经过转换得到后缀表达式，最终结果将数据显示到主屏幕上即可。

图3.1.1系统总体结构图

3.2程序算法图

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

首先提示用户输入中缀表达式，再利用程序将中缀表达式转换为后缀表达式，其中数字入队列，算术运算符入栈。

图3.2.1程序算法图

4具体设计

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

将中缀表达式转换为后缀表达式首先需要扫描中缀表达式，当遇到数字时，将其入队列，当遇到运算符时，若是低优先级则直接入栈，若是高优先级则将低优先级运算符弹出，并入队列，再将此次运算符入栈，最终形成后缀表达式

图4.1.1后缀表达式的转换

其伪代码算法如下：

switch(c){

case'0'tocase'9':EnQueue(Q,c)

case'(':Push(S,c)

case')'tocase'#':t=Pop(S);

if(t!='('

}while(t!='('

case'+'||case'-'||case'*'||case'/':

while(Priority(c)data[Q->front++];

4.2后缀表达式的求值

由于在将中缀表达式转换为后缀表达式时已经将运算符支配在了合适的位置，在后缀表达式中不仅不需要括号，而且还完全免除了运算符优先规章，仅需从左到右计算即可。

其伪代码如下：

while(!QueueEmpty(Q)){

ch=DeQueue(Q)

if(ch>='0')//数字字符到数值的转换

else{

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

switch(ch){

case'+':Push(S,x+y);break;

case'-':Push(S,x-y);break;

case'*':Push(S,x*y);break;

case'/':Push(S,x/y);break;

}

}

5运行与测试5.1输入表达式：

输入一个中缀表达式：

5.2输出结果：

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

6总结和心得

6.1心得与问题

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

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

个函数出来推断。

②后缀表达式的求值中，Push(S,ch-'0')中的ch-‘0’是什么意思？由于输入表达式时数

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

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

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

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

时总是指向空？由于之前调用了Dequeue(Q)，导致front发生了转变，相当于队列被删除了，所以再调用时就为空了，解决方法有多种，比如复制队列，我实行了一个简洁的方法，在调用了CTPostExp(Q)后不忙着输出后缀表达式，连续调用CPostExp(Q)，在CPostExp(Q)中使用Dequeue(Q)时顺便就将后缀表达式输出，这样就避开了队列其次次调用时已经被删除的窘境。

6.2总结

本次试验中内存出错的状况比较多，比如在输出后缀表达式时虽然结果正确，但后面还有许多“烫烫…”，在计算后缀表达式时，返回值总是没有，等等，但通过不断地调试这些问题都得以解决。

通过本次试验，加强了对栈和队列的存储结构的理解，尤其是栈的先进后出的结构有了更深的了解。

chardata[100];

intfront,rear;

}Seueue;//定义队列类型

typedefstruct

{

DataTypedata[100];

inttop;

}SeqStack;//栈类型的定义

//初始化队列

voidInitQueue(Seueue*Q)

{

Q->front=0;

Q->rear=0;//头部和尾部分别赋值为0

}

//清空队列

intQueueEmpty(Seueue*Q)

{

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

}

//入队列

voidEnQueue(Seueue*Q,DataTypex)

{

if((Q->rear+1)%QueueSize==Q->front)//推断队列是否装满printf("队列溢出");

else

{

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

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

}

}

//输出队列

charDeQueue(Seueue*Q)

{

charx;

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

Q->front++;

returnx;

}

//初始化栈

voidInitStack(SeqStack*S)

{

S->top=-1;

}

//入栈

voidPush(SeqStack*S,DataTypex)

{

if(S->top==StackSize-1)

printf("栈溢出");

else

{

S->top=S->top+1;//栈顶指针指向新插入的数据

S->data[S->top]=x;

}

}

//出栈

DataTypePop(SeqStack*S)

{

if(S->top==-1)

printf("空栈");

else

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

}

//取栈顶元素

DataTypeGetTop(SeqStack*S)

{

if(S->top==-1)

printf("栈空");

else

returnS->data[S->top];

}

//求运算符优先级函数

intPriority(DataTypeop)

{

switch(op)

{

case'(':

case'#':return0;break;

case'-':

case'+':return1;break;

case'*':

case'/':return2;break;

}

}

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

voidCTPostExp(Seueue*Q)

{

SeqStackOS;//运算符栈

charc,t;

SeqStack*S;

S=

InitStack(S);

Push(S,'#');//压入栈底元素#

do//扫描中缀表达式

{

c=getchar;

switch(c)

{

case'':break;//去除空格符

case'0':

case'1':

case'2':

case'3':

case'4':

case'5':

case'6':

case'7':

case'8':

case'9':

EnQueue(Q,c);break;

case'(':Push(S,c);break;

case')':

case'#':

do

{

t=Pop(S);

if(t!='('

}while(t!='('break;

case'+':

case'-':

case'*':

case'/':

while(Priority(c)='0'//数字字符到数值的转换

else

{

y=Pop(S);

x=Pop(S);

switch(ch)

{

case'+':Push(S,x+y);break;

case'-':Push(S,x-y);break;

case'*':Push(S,x*y);break;

case'/':Push(S,x/y);break;

}

}

}

printf("\n");

printf("最终结果为：");

printf("%d\n",GetTop(S));

return