- 1、本文档共11页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
数据结构课程设计表达式求值问题
目 录
1概述 3
1.1目的及意义 3
2系统分析 3
2.1需求分析 3
3概要设计 3
3.1系统总体结构 3
3.2程序算法图 3
4详细设计 4
4.1中缀表达式转换为后缀表达式 4
4.1.1求运算符优先级函数 5
4.1.2输出队列 5
4.2后缀表达式的求值 5
5运行与测试 6
5.1 输入表达式: 6
5.2 输出结果: 6
6总结和心得 6
6.1心得与问题 6
6.2总结 6
参考文献 7
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 to case 9 :EnQueue(Q,c)
case (: Push(S,c)
case ) to case#: t=Pop(S);
if (t!=( t!=#)
EnQueue(Q,t);
} while (t!=( S-top!=-1);
case + || case -|| case *|| case /:
while (Priority(c)=Priority(GetTop(S))) //比较优先级
EnQueue(Q, Pop(S))
Push(S,c)
}
4.1.1求运算符优先级函数
算术运算符入栈时必须考虑运算符的优先级,才能形成正确的后缀表达式,当读到运算符时,将栈中所有优先级高于或等于该运算符的运算符弹出,送至输出队列中,再将当前运算符入栈;当读入左括号时,即入栈;当读到右括号时,将靠近栈顶的第一个左括号上面的运算符全部依次弹出,送至输出队列中,再删除栈中的左括号。
通过返回值的大小代表优先级的大小,其伪代码算法如下:
switch (op){
case (||case #: return 0;break;
case -||case +:return 1;break;
case *|| case /:return 2;break;
}
4.1.2输出队列
当中缀表达式转换成后缀表达式之后,需要输出后缀表达式,也就是当前队列,只需要让头指针遍历输出数据即可。
其伪代码如下:
x=Q-data[Q-front++];
4.2后缀表达式的求值
由于在将中缀表达式转换为后缀表达式时已经将运算符安排在了合适的位置,在后缀表达式中不仅不需要括号,而且还完全免除了运算符优先规则,仅需从左到右计算即可。
其伪代码如下:
while(!QueueEmpty(Q)) {
ch=DeQueue(Q)
if (ch=0 ch=9)
Push(S,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心得与问题
在本次实验中,遇到的心得:
文档评论(0)