数据结构课程设计报告书表达式求值问题.docx
- 文档编号:10929410
- 上传时间:2023-05-28
- 格式:DOCX
- 页数:17
- 大小:18.72KB
数据结构课程设计报告书表达式求值问题.docx
《数据结构课程设计报告书表达式求值问题.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计报告书表达式求值问题.docx(17页珍藏版)》请在冰点文库上搜索。
数据结构课程设计报告书表达式求值问题
南通大学计算机学院
《数据结构课程设计报告书》
题目:
表达式求值问题
专业:
计算机科学与技术
班级:
学号:
姓名:
指导教师:
开始日期:
2013.1.14完成日期:
2013.1.16
1.问题的描述和分析
1.1问题描述
表达式有中缀、后缀、前缀三种表示方式,中缀式的计算按运算符的优先级及括号优先原则,相同级别从左到右进行运算。
而前缀式和后缀式没有括号给运算带来方便。
本设计的主要任务是进行表达式的转换及不同表达式的计算。
1.2问题分析
表达式是字符型数据,在程序中涉及表达上的转换,可用数组和栈来存储表达式。
程序中关键要处理好在不同形式表达中字符的顺序,对操作符优先级的比较以及在中转前、中转后过程中对括号的处理。
2.概要设计
2.1系统模块划分
要求:
描述整个系统的模块划分,最后以图的形式展现,并简单介绍每个模块的功能。
例如:
图2-1系统模块图
2.2ADT(抽象数据类型)描述
本程序要用到栈,对栈的操作包含在头文件“SqStack.h”中。
ADTStack
数据对象:
Dai|ai∈ElementSet,i1,2…,n,n≥0
数据关系:
Rai-1,ai|ai-1,ai∈D,i2,…n
基本操作:
SqStack
创建一个空栈
Push
将一个元素压入栈中
Pop
将栈顶元素出栈
StackEmpty
判断栈是否为空要求
3.详细设计
3.1ADT基本操作算法设计
3.1.1ADT操作1
中缀表达式求值
SqStackOP20;//操作符栈
SqStackOD20;//操作数栈
读入表达式操作数或操作符C,如果C是操作数,OP.PushC,如果C是操作符,把它与栈顶元素的优先级比较case'':
OP.Pushc;case'':
xOP.Pop;如果是大于,从操作符栈里退出两个元素进行运算。
重复上述过程直到把表达式扫描完,操作数栈的栈顶元素为计算结果
3.1.2ADT操作2
中缀转后缀
SqStackOP20
从左向右读取表达式,读到操作数把它输出,读到操作符,把它与栈顶元素的优先级比较case'':
OP.Pushc;case'':
xOP.Pop;case'':
postexp[i++]OP.Pop;
3.1.3ADT操作3
中缀转前缀
SqStackST20;
SqStackSP20;
SqStackOP20;
将中缀式入栈再依次从栈中读取元素,如果是操作数把它加入一个数组中ifC'’OP.PushC;如果是运算符,则:
如果栈空或栈顶是闭括号或此元素的优先级大于等于栈顶元素此操作符入栈,否则,栈顶运算符出栈并加入数组中;如果是开括号,栈中元素逐个出栈加入数组中,直到遇到闭括号。
最后数组中的元素序列为中缀式的逆序,将数组中的元素入栈再出栈就得到中缀式。
3.1.4ADT操作4
后缀求值
SqStackOD20;//操作数栈
c*postexp++;
whilec!
'\0'
ifc'0'&&c'9'||c'.'//为操作数
i0;
do
z[i++]c;
c*postexp++;
whilec'0'&&c'9'||c'.';
z[i]'\0';
datofz;//将字符串数组转为符点型存于d
OD.Pushd;
ifInc//遇到运算符从栈中退出两个元素进行运算
bOD.Pop;
aOD.Pop;
OD.PushOperatea,c,b;
c*postexp++;
c*postexp++;
vOD.Pop//计算结果
3.1.5ADT操作5前缀式求值SqStackST20;SqStackOD20;
while*preexp!
'\0'
ST.Push*preexp++;//利用栈得到前缀表达式的逆序
while!
ST.StackEmpty
xST.Pop;
ifx'0'&&x'9'||x'.'
k0;
do
z[k++]x;//得到一个数的逆序xST.Pop;
whilex'0'&&x'9'||x'.';k--;
forp0;k0;p++,k--//将逆转的数变回原数
s[p]z[k];
datofs;
OD.Pushd;
ifInx//遇到操作符从栈中退出两个元素运算
aOD.Pop;
bOD.Pop;
OD.PushOperatea,x,b;
vOD.Pop;//计算结果
3.2功能模块设计
3.2.1登录模块
(1)界面设计
截取界面图片
(2)处理流程设计
用程序流程图表示
3.2.2录入模块
(1)界面设计
截取界面图片
(2)处理流程设计
用程序流程图表示
……….
4.运行和调试
4.1运行和测试
1、显示菜单界面
2、输入一个表达式
3、中缀表达式求值
4、由中缀表达式求后缀表达式
5、后缀表达式求值
6、由中缀表达式求前缀表达式
7、前缀表达式求值
8、显示各种形式的表达式
4.2调试记录与收获
1、在求前缀表达式时要对表达式串进行两次逆序,刚开始用数组实现总出错,后来改用栈来实现串的逆序,过程比用数组简单、清晰的多了。
2、刚开始输出的前缀表达式中有括号,后来经过改变程序中的括号改变了条件,就不再有括号出现。
3、前缀表达式求值时结果出现错误,是因为没有把所有的字符型数字转换成浮点型,后来加上一个do…while循环,结果就正确了。
4、在前缀表达式求值时,只能进行一位整数的运算,是因为将前缀表达式逆序时也将一个数逆序了,可以设置一个数组将数字再次逆序,这样就行了。
设计体会与收获:
通过这次课程设计,我学会了与表达式相关的一些操作,如设计不同形式的表达式以及对其求值,并且在不断调试过程中学习了一些知识。
但这个程序仍然存在很多不足,只能实现少部分功能,所以说明我掌握的东西还很少,能力太低,还要不断学习才行。
源程序:
#include//cout,cin
#include"process.h"//exit
#include"stdio.h"//EOF,NULL
#include//atof
#include"SqStack.h"
charpause;
charPrecedechart1,chart2//算符的优先级比较charf;switcht2case'+':
case'-':
ift1''||t1''f'';elsef'';break;case'*':
case'/':
ift1'*'||t1'/'||t1''f'';elsef'';break;case'':
ift1''cout"表达式有误!
"endl;exit0;elsef'';break;case'':
switcht1case'':
f'';break;case'':
cout"表达式有误!
"endl;exit0;default:
f'';break;case'':
switcht1case'':
f'';break;case'':
cout"表达式有误!
"endl;exit0;default:
f'';returnf;
intIncharc//判断c是否为运算符switchccase'+':
case'-':
case'*':
case'/':
case'':
case'':
case'':
return1;default:
return0;
doubleOperatedoublea,chartheta,doubleb//实施一次运算doublec;switchthetacase'+':
ca+b;break;case'-':
ca-b;break;case'*':
ca*b;break;case'/':
ca/b;returnc;
doubleVal_Expchar*exp//中缀表达式求值。
设OPTR和OPND分别为运算符栈和运算数栈SqStackOP20;SqStackOD20;chartheta;doublea,b,d;charc,x;//存放由键盘接收的字符charz[6];//存放符点数字符串inti;OP.Push'';//是表达式结束标志c*exp++;xOP.GetTop;whilec!
''||x!
''ifInc//是7种运算符之一switchPrecedex,ccase'':
OP.Pushc;//栈顶元素优先权低c*exp++;break;case'':
xOP.Pop;//脱括号并接收下一字符c*exp++;break;case'':
thetaOP.Pop;//退栈并将运算结果入栈iftheta''||theta''
cout"表达式有误!
";exit0;
bOD.Pop;
ifb0
cout"表达式有误!
"endl;exit0;
ifOD.StackEmpty
cout"表达式有误!
"endl;exit0;
aOD.Pop;OD.PushOperatea,theta,b;elseifc'0'&&c'9'||c'.'//c是操作数i0;doz[i]c;i++;c*exp++;whilec'0'&&c'9'||c'.';z[i]'\0';datofz;//将字符串数组转为符点型存于dOD.Pushd;else//c是非法字符cout"表达式有误!
"endl;;exit0;xOP.GetTop;dOD.GetTop;returnd;
voidCreatePreExpchar*exp,char*&preexp//由中缀式求前缀式
charx;
chars[20];
intj0,i0,k0;
SqStackST20;
SqStackSP20;
SqStackOP20;
while*exp!
''//利用栈得到中缀式的逆序
ST.Push*exp++;
while!
ST.StackEmpty
xST.Pop;
ifx'0'&&x'9'||x'.'
s[j++]x;
ifx''
OP.Pushx;
whilex'+'||x'-'||x'*'||x'/'
s[j++]'';
ifOP.StackEmpty||OP.GetTop''||Precedex,OP.GetTop''||Precedex,OP.GetTop''
OP.Pushx;
break;
else
s[j++]OP.Pop;
ifx''
whileOP.GetTop!
''
s[j++]OP.Pop;
OP.Pop;
while!
OP.StackEmpty
s[j++]'';
s[j++]OP.Pop;
s[j]'\0';
whiles[i]!
'\0'
SP.Pushs[i++];
while!
SP.StackEmpty
preexp[k++]SP.Pop;//再次求逆序得到前缀式
preexp[k]'\0';
cout"前缀表达式为:
"preexpendl;
voidCreatePostExpchar*exp,char*&postexp
//由中缀式求后缀式
charc,x;
inti0;
SqStackOP20;
OP.Push'';//是表达式结束标志c*exp++;
whilec
ifc'0'&&c'9'||c'.'
postexp[i++]c;
c*exp++;
ifInc//是7种运算符之一
postexp[i++]'';xOP.GetTop;
switchPrecedex,c
case'':
OP.Pushc;//栈顶元素优先权低c*exp++;break;case'':
xOP.Pop;//脱括号并接收下一字符c*exp++;break;case'':
postexp[i++]OP.Pop;//运算符出栈输出break;
postexp[i]'\0';
//while
cout"后缀表达式为:
"postexpendl;
doubleVal_PostExpchar*postexp
//后缀表达式求值
inti;
charz[6];
doublev0,d0,a,b;
charc;
SqStackOD20;
c*postexp++;
whilec!
'\0'
ifc'0'&&c'9'||c'.'//为操作数
i0;
do
z[i++]c;
c*postexp++;
whilec'0'&&c'9'||c'.';
z[i]'\0';
datofz;//将字符串数组转为符点型存于d
OD.Pushd;
ifInc//c为运算符
bOD.Pop;
aOD.Pop;
OD.PushOperatea,c,b;
c*postexp++;
c*postexp++;
vOD.Pop;
returnv;
doubleVal_PreExpchar*preexp//前缀表达式求值
intk,p0;
charz[6],s[6];
charx;
doublev,d0,a,b;
SqStackST20;SqStackOD20;
while*preexp!
'\0'
ST.Push*preexp++;//利用栈得到前缀表达式的逆序
while!
ST.StackEmpty
xST.Pop;
ifx'0'&&x'9'||x'.'
k0;
do
z[k++]x;xST.Pop;
whilex'0'&&x'9'||x'.';k--;
forp0;k0;p++,k--
s[p]z[k];
datofs;
OD.Pushd;
ifInx
aOD.Pop;
bOD.Pop;
OD.PushOperatea,x,b;
vOD.Pop;
returnv;
//主函数
voidmain
charexp[20];
char*postexp,*preexp;
postexpnewchar[20];preexpnewchar[20];
*postexp'\0';
*preexp'\0';//charc;
doublev1,v2;
system"cls";//执行系统命令cls,清屏
intchoice;do
//显示主菜单
cout"--------*菜单*-------\n";
cout"1-创建表达式\n";
cout"2-表达式求值\n";
cout"3-求后缀表达式\n";
cout"4-后缀表达式求值\n";
cout"5-求前缀表达式\n";
cout"6-前缀表达式求值\n";
cout"7-显示表达式\n";
cout"8-退出\n";
cout"请选择菜单:
";
cinchoice;
switchchoice
case1:
//创建表达式
cout"请输入表达式,以结束"endl;
cinexp;
cin.getpause;
system"pause";
break;
case2:
//表达式求值
v1Val_Expexp;
coutexp;
coutv1endl;
cin.getpause;system"pause";
break;
case3:
//求后缀表达式
CreatePostExpexp,postexp;
cin.getpause;
system"pause";
break;
case4:
//后缀表达式求值
v1Val_PostExppostexp;
coutpostexp""v1endl;
cin.getpause;
system"pause";
break;case5:
//求前缀表达式
CreatePreExpexp,preexp;
system"pause";
cin.getpause;
break;case6:
//前缀表达式求值v2Val_PreExppreexp;coutpreexp""v2endl;cin.getpause;
system"pause";
break;
case7:
//显示表达式
coutendl;
cout"中缀表达式为:
";
coutexpendl;
CreatePostExpexp,postexp;
CreatePreExpexp,preexp;
cin.getpause;
system"pause";
break;
case8:
//退出
cout"结束运行,Bye-Bye!
"endl;
break;
////0>.
cout"Invalidchoice\n";
break;
whilechoice!
8;
//endmain
头文件SqStack.h中的内容:
//顺序栈类定义
templateclassSqStack
private:
T*base;//栈底指针
inttop;//栈顶
intstacksize;//栈容量
public:
SqStackintm;//构建函数
~SqStackdelete[]base;top0;stacksize0;//析构函数
voidPushTx;//入栈
TPop;//出栈
TGetTop;//获取栈顶元素
intStackEmpty;//测栈空
voidClearStack;//清空栈
voidStackTop;//返回栈顶指针
voidStackTranverse;//显示栈中元素
;
//顺序栈类实现
template
SqStack:
:
SqStackintm
basenewT[m];
ifbaseNULL
cout"栈创建失败,退出!
"endl;
exit1;
stacksizem;
top-1;
template
voidSqStack:
:
PushTx
iftopstacksize-1throw"栈满,无法入栈";
top++;
base[top]x;
//cout"top:
"topendl;
template
TSqStack:
:
Pop
Tx;
iftop-1throw"栈空,不能出栈";
xbase[top--];
//cout"top:
"topendl;
returnx;
template
TSqStack:
:
GetTop
iftop-1throw"栈空,栈顶无元素";
//cout"top:
"topendl;
returnbase[top];
template
intSqStack:
:
StackEmpty
iftop-1
return1;
else
return0;
template
voidSqStack:
:
ClearStack
top-1;
template
voidSqStack:
:
StackTop
//返回栈顶指针
cout"栈顶top"top;
template
voidSqStack:
:
StackTranverse
intitop;whilei0coutbase[i--]'\t';coutendl;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 报告书 表达式 求值 问题