数据结构课程设计Word格式文档下载.docx
《数据结构课程设计Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计Word格式文档下载.docx（19页珍藏版）》请在冰点文库上搜索。
需要一台计算机装有visualC++。
4.分析与实现
对于中缀表达式，一般运算规则如下：
（1）先乘方，再乘除，最后加减；
（2）同级运算从左算到右；
（3）先括号内再括号外；
（4）用到的头文件”utility.h”,”lk_stack.h”,”node.h”,”calculator.h”.
根据实践经验，可以对运算符设置统一的优先级，从而方便比较。
表中给出了包括加、减、乘、除、求余、左括号、右括号和分界符的优先级。
运算符
‘=’
‘（’、‘）’
‘+’、‘—’
‘*’、‘/’‘%’
‘^’
优先级
1
2
4
5
上面讨论的的+、—为双目运算符，如为单目运算符，编程实现时，可在前面加上0而转化为双目运算符。
如在+、—的前一个字符（如当前字符不是运算符时，规定用0表示）为‘=’或‘（’，则为单目运算符。
具体实现算法时，可设置两个工作栈，一个为操作栈，一个为操作符栈optr，另外一个为操作数栈opnd,算法基本思路如下：
（1）将optr栈和opnd栈清空，在optr栈中加入一个‘=‘。
（2）从输入流获取一字符ch,循环执行步骤（3）至步骤（5）直到求出表达式的值为止。
（3）取出optr的栈顶optrTop,当optrTop=‘=‘且ch=’=‘时，整个表达式求值完毕，这时opnd栈的栈顶元素为表达式的值。
（4）若ch不是操作符，则字符放回输入流（cin.putback）,读操作数operand；
将operand加入opnd栈，读入下一个字符ch。
（5）如ch是操作符，按如下方式进行处理：
a.如果ch为单目运算符，则在ch前面加上操作数0，也就是将0入opnd栈；
b.如果optrTop与ch不匹配，例如optrTop=‘）‘且ch=’（‘，显示错误信息；
c.如果optrTop=‘（‘且ch=’）‘，则从optr退出栈顶的’（‘，去括号，然后从输入流中读入字符并送入ch；
d.如果ch=’（’活optrTop比ch的优先级低，则ch入optr栈，从输入中取下一字符ch；
e.如果optrTop大于或等于ch的优先级，则从opnd栈退出left和right，从optr栈退出theta,形成运算指令（left）theta（right）,结果如opnd栈。
对于界面处理：
（1）用文件流建立一个小小的界面，美化处理一些操作，文件名为dd.txt
//dd.txt文档内容
*
**
*******
**
*欢迎进入运算界面*
************
*请选择：
*1.开始运算*
*2.退出界面*
对于运算处理：
（1）通过运用栈和队列的特性，实现各种功能。
本类通过一系列的扩展实现各种出现的运算情况处理
//calculator.h
#ifndefCALCULATOR_H
#defineCALCULATOR_H
#include"
lk_stack.h"
template<
classElemType>
classCalculator
{
private:
LinkStack<
ElemType>
opnd;
char>
optr;
charGetChar（）//从输入流中跳过空格，换行符及制表符获取一字符
{
charc;
cin>
>
c;
returnc;
}
intOperPrior（charop）;
//要自己写的函数
voidGet2Operands（ElemType&
left,ElemType&
right）;
ElemTypeOperate（ElemTypeleft,charop,ElemTyperight）;
boolIsOperator（charch）;
public:
Calculator（）{};
virtual~Calculator（）{};
voidRun（）;
};
//使用switch语句
intCalculator<
:
OperPrior（charop）
switch（op）
case'
='
return1;
（'
return2;
）'
+'
return3;
-'
*'
return4;
/'
%'
^'
return5;
}
//调用2次出栈函数，一定要先出右数，再出左数！
voidCalculator<
Get2Operands（ElemType&
right）
opnd.Pop（right）;
opnd.Pop（left）;
//采用switch语句
ElemTypeCalculator<
Operate（ElemTypeleft,charop,ElemTyperight）
returnleft+right;
returnleft-right;
returnleft*right;
returnleft/right;
returnint（left）%int（right）;
//输入数为浮点数，要强制转换为整数！
returnpow（left,right）;
boolCalculator<
IsOperator（charch）
if（ch=='
||ch=='
）
returntrue;
else
returnfalse;
Run（）
optr.Clear（）;
//清空optr栈
opnd.Clear（）;
//清空opnd栈
optr.Push（'
）;
charch;
charpriorChar;
//当前输入的前一个字符，如果不为操作符，则令其值为0
charoptrTop;
ElemTypeoperand;
charop;
priorChar='
;
ch=GetChar（）;
if（!
optr.Top（optrTop））throw"
表达式有错！
"
while（optrTop!
||ch!
if（isdigit（ch）||ch=='
.'
{
cin.putback（ch）;
cin>
operand;
opnd.Push（operand）;
priorChar='
0'
ch=GetChar（）;
}
elseif（!
IsOperator（ch））
throw"
else
if（（priorChar=='
||priorChar=='
）&
&
（ch=='
））
{
opnd.Push（0）;
priorChar='
}
if（optrTop=='
ch=='
||optrTop=='
throw"
elseif（optrTop=='
if（!
optr.Pop（optrTop））throw"
ch=GetChar（）;
elseif（ch=='
||OperPrior（optrTop）<
OperPrior（ch））
optr.Push（ch）;
priorChar=ch;
else
optr.Pop（op））throw"
ElemTypeleft,right;
Get2Operands（left,right）;
opnd.Push（Operate（left,op,right））;
if（!
opnd.Top（operand））throw"
cout<
<
"
运算结果为：
operand<
endl;
#endif
主函数功能：
（1）应用dd.txt建立小小界面;
（2）针对各种出错情况进行智能处理;
（3）实现本次计算基本呢操作
//main主函数
#include"
utility.h"
calculator.h"
intmain（）
//第一部分进行界面处理，通过文件流的方式
chara[100];
ifstreamin（"
dd.txt"
for（inti=1;
i<
19;
i++）
in.getline（a,100）;
cout<
a<
in.close（）;
chard[100];
while（true）//此方法可处理出现的一般不同错误
d;
if（d[0]=='
1'
）break;
elseif（d[0]=='
2'
）{cout<
cout<
已退出界面！
exit（0）;
else
cout<
选择错误，请重新选择！
//第二部分进行运算处理
charc;
请输入表达式：
Calculator<
double>
myCalculator;
输入形式如1（没有括号加减乘除）：
4+5-8+8/2+6*1="
输入形式如2（加括号加减乘除）：
4*（7+1）/2+3-2="
输入形式如3：
+45="
myCalculator.Run（）;
while（true）
endl<
你是否要继续（y,n）?
if（c=='
n'
cout<
运算已经结束,已退出程序！
return0;
elseif（c=='
y'
break;
******你的输入错误，请重新输入：
******"
运行结果：
（1）一般成功运行：
有括号的加减乘除，没有括号的加减乘除，单目运算
（2）跳过空格，制表符，换行符继续运行
（3）选择进入界面输错处理
（4）.输入选择是否继续出错处理
5.课程设计体会与感悟
本次课程设计需要涉及到比较多的知识，为了美化界面用了文件流，让我有加深了对文件流的认识。
算术的操作用了栈，结点类，让我更熟悉了栈后进先出以及其他类的的特点。
1、该程序不只能运算整数，也能处理输入的负数
2、可以一定的处理非法输入
3、几种线性表（队列、栈、数组、链表）从根本上说可以实现同一个功能，只是难易程度的问题，熟悉各线性表的特点有助于快速选择简单的方法。
升级会员 