C++与数据结构专题设计三简易计算器

1、C+当数据结构专题设计 简易计算器 目录 一 .问题描述2 二 .具体要求2 三 .数据结构3 四 .设计与实现3 1 .系统首页：4 2 .进行简单的四则运算5 五 .测试与结论11 1 .表达式错误的情况12 2 .所要计算的数据过大或过小的情况15 六 .总结与思考17 七 .附源代码17 一.问题描述 由键盘输入一算术表达式，以中缀形式输入，试编写程序将中缀表达式转换成一棵二叉表达式树，通过对该的后序遍历求出计算表达式的值。 二.具体要求 a.要求对输入的表达式能判断出是否合法。不合法要有错误提示信息。 b.将中缀表达式转换成二叉表达式树。 c.后序遍历求出表达式的值 三.数据结构 一

2、棵表达式树，它的树叶是操作数，如常量或变量名字，而其他的结点为操作符。 a.建立表达式树。 二叉树的存储采用了链式存储。 当要创建二叉树时，先从表达式尾部向前搜索， 找到第一个优先级最低的运算符， 建立以这个运算符为数据元素的根结点。 注意到表达式中此运算符的左边部分对应的二叉绮为根结点的左子树，右边部分对应的是二叉绮为根结点的右子树，根据地这一点，可用递归调用自己来完成对左右子树的构造。 b.求表达式的值。求值时同样可以采用递归的思想，对表达式进行后序遍历。 先递归调用自己计算左子树所代表的表达式的值， 再递归调用自己计算右子树代表的表达式的值， 最后读取根结点中的运算符， 以刚才得到的左右

3、子树的结果作为操作数加以计算，得到最终结果。 四.设计与实现 为了使用二叉树实现表达式的顺序运算，我们分别构造了结点类,用来作为二叉树的基本结构，后构造二叉树类，构造函数并建立根节点，先对二叉树的根节点进行运算，再通过对当前节点的左孩子右孩子节点进行判断、计算、删除，以一个递归调用函数即后序遍历，从根节点开始计算，如果子树中不为空且不为数据则先遍历左子树然后遍历右子树然后计算根节点，从而实现按照运算符优先级顺序完成表达式计算的功能。并在每次计算完成后询问操作者意愿从而决定是否进行下一次运算。 以下介绍程序功能的实现： 1 .系统首页: 功能提示，输入待计算的表达式，以完成计算: 相应代码: s

4、ystem(cls); * 二叉树计算器endl; *charc; while(choice=y|choice=Y)(cout * endl; cout cout * endl; coutinfix; cout n;cout”表达式为：infixn; 2 .进行简单的四则运算 对输入的表达式首先判断正误，然后按照运算的优先级分别进行运 行，并且分别输出每步运算的结果。先进行乘方，然后乘除，最后再 计算加减，先算括号内后算括号外，正确度一目了然。 1P1P：5 5 学习 K+K+粕未 二叉树计算器 MHJCJOCXHMXMM：MJOTM：MEMKKJflffMM：NKMJCXMXJCKMlCJf

5、fMM：JCXJtMlCMlgMJtMlCXMJtMJCJClfIffXME，JtMiMiffMJtMIt 请输入表达式； 13+2513+25- -36*2/9)263/9)2 是否要重新运行?输入小八: irr式的是 达间果 表中72结 76 是否要重新运彳 C 榆入CN二Y 请输入表达式： - -1212*56”*56”- -24/624/6 是否要重新运行?输入： inin (1)对于负数也可以进行相应的加减乘除以及乘方的运算。对 于负数的运算，也和正数一样，先算括号内的后算括号外的，其 次算乘方，再算乘除，最后进行加减的运算 S3S3口将习”+小专道阖出砂法谕名工冉/是否要重新运行?

6、输入：y y 请输入表达式； - -12+(15/912+(15/933- -2 2 震达式为?- -12*12*A Aa a 中间的算结果：- -12125270477252704772 结果是二寸 是否要重新运行?输入(Y/N(Y/N： 负数的加减乘除:E3E3- -D D：XgXg c+c+1,1,exe,exe, cztczt 叵痉 果40结 二算 -流是达间2果表中T结 E3E3。；学习专期即卧未命名 LoeLoe 请输入表达式; 需藉结晶 - -12*12*+L1- -2 2 结果是 128128 是否要重新运行?输入丫川： 负数的乘方运算: (1) 正指数哥运算: d dDADA

7、 学习+宙期设计惘未命名LEX- 回 S3S3 是否要重新运行?输入 4/4/心;y y 请输入表达式： 5A A2 2 .算25:式的是达间果虑中T结 是否要重新运行?输入 (2)负指数哥运算: 可以进行小数的计算，对于小数采用浮点数的存储方式和输出 方式，计算精度可以取到小数点后五位。 小数的加减乘除: 小数的运算，依然按照先乘除后加减，先算括号内后算括号外的顺序运算D：1，学习 F+守或凌计、恢夫拿名l.exe是否要重新运行苫输丫川 X 少 请输入表达式士 1 1.J25*1.45.J25*_502.4.074.07 中间的计算结具,2.G54474.104472.G54474.1044

8、7- -0.765530.76553 结果是 t t- -1.014331.01433 是否要重新运行?输入 小数的乘方和开方： (1)正小数哥次方： r 口D学习 q 炉专题设计甲 n n 丰含11 皿 Q Q 件否要重新贬吁?输入 d d 而好请输入袤达式 I I 1.2343.44 l.J2b.b3Z2.4bl.J2b.b3Z2.4b- -4.H74.H7 中间的计算结果; 1.2343,41.2343,4 2.051222.05122 若果是:2 2- -6613366133 是否要重新运吁?输入(Y(Y，NXNX (4)开负小数次方:E,OiVE,OiV 学2G+有班*- -EAEA

9、 未翁生 l.exfl.exf 是否要重新运仃？输 A4A4 NmNm 丫请输入表达式; L234L234 气- -2.3?32.3?3 需1诂间.3果表由T结 ：1,2341,234A A( (- -2*3312*331 算结枭 0.6126830.612683 是否要重新运行?输入“八 1”1” (3)开正小数次方: 是否要重新运彳产输入 4 4 小 X1 1 请输入表达式; U.lbB.SU.lbB.S 是否要重新运行孑轴八Y/NY/N： 杲 4 果钻 -算式的 达间4果表中电结 r S3笛：字事工+博蹬tt刚未能ELEKE 是否要重新运行?输入V 清榆人走达式二 0.160.16A A

10、 0.5 是否要重新运行?输入： IH 五.测试与结论 此报告在C-Free5.0环境下进行测试。C-Free是一款C/C+噪成开发环境（IDE）。C-Free中集成了C/C+弋码解析器，能够实时解析代码，并且在编写的过程中给出智能的提示。C-Free提供了对 目前业界主流C/C+瑞译器的支才I,可以在C-Free中轻松切换编译器。可定制的快捷键、外部工具以及外部帮助文档，使在编写代码时得心应手。完善的工程/工程组管理使你能够方便的管理自己的代码。 以下是各种测试用例。注：较为简单和常规的测试用例在上一部分”算法的实现”中已经给出，下面只给出一些具有代表性的测试用例。 1.表达式错误的情况 -

11、*5臬2.结E:1昇2 :式的是达间,5果-0结 在表达式错误的情况下，程序能够运行，但是不能够正常运 算，而是给出错误的提示信息，提醒重新输入正确的表达式。 下图表示以0作为除数时程序所给的提示信息“Infinity” ”射表达式：g g 1 1 表达式为 t t-i/e 中间的 M M 算结果： 1nfLnlty0 结果是； 足否要重薪运行7输工 n 下图为计算表达式0八（-3）时候的输出，由于表达式没有数学意义，所以也就没有正确的结果，因而程序运行后得到的结果是aInfinity: 下图显示的是输入的表达式不符合数学规律时的错误提示 信息。 Z:Use01Administr&tc

12、r.Dmsmop又.忸:计苴号,exe 请输入表达式二 表达式无: 中间的计算结里， - -1515HaHHaH 结果是:WNWN 是否要重新运行?输入： 下图表示输入表达式中含有不合法的字符， 例如字母时候,程序运行时所给的提示信息。2121CtCt UsersUsers AdministratorAdministrator DetktopDetktopLL视计算瞩 ewew 豆否要重新运厅才输入*”J J 清输入表这式： a.+La.+L 麦达式为 Bt*XA*!WM*MWM*M- -*W*W- -MM/: 是否要重新运行?谕入 CNCN 卜二 9 9 请输入表达式， m979n?$9?9

13、?m979n?$9?9?.99999*3 中间的计算结果；InfinitInfinitv v 结果是(frfinity(frfinity 是否要重新运行?输入YN= = 六.总结与思考 七.附源代码 #include #include #include #include #include利用stack头文件来构造两个栈用来存储数 据和运算符 usingnamespacestd; boolIsOperator(stringmystring)判断参数string是否是 运算符是返回逻辑值true ( if(mystring=-|mystring=+|mystring=/|mystring= =*|

14、mystring=A) return(true); else return(false); ) boolIsOperator(charops)重载 ( if(ops=+110Ps=-110Ps=*110Ps=/110Ps=八|ops=( |ops=) return(true); else return(false); ) boolIsOperand(charch)/验证是否是数 ( if(ch=0)&(chdata)&!IsOperator(prt-left_child-data)&!IsOperator(prt-right_child-data) ( floatnum

15、=0; floatnum1=atof(prt-left_child-data.c_str();/# data转换成char型数据然后用atof将char转换成浮点数 floatnum2=atof(prt-right_child-data.c_str(); if(prt-data=+) num=num1+num2; elseif(prt-data=-) num=num1-num2; elseif(prt-data=*) num=num1*num2; elseif(prt-data=/) num=num1/num2; elseif(prt-data=A) num=pow(num1,num2); c

16、outnumt;/对每个结点计算后的中间结果 stringstreambob;/定义个流对象 bobdata=temp;/将计算的结果赋值给当前结点prt-left_child=NULL;/然后删除左右孩子结点 prt-right_child=NULL; else if(prt-left_child=NULL&prt-right_child=NULL);如果左后孩子 都为空则不作操作 else evaluate(prt-left_child); evaluate(prt-right_child); evaluate(prt);/如果不满足上面的条件则先 运算左孩子再运算右孩子再运算本身

17、 /上述函数为一个递归调用即后序遍历 /从根节点开始计算如果子树中不为空且不为数据则先 遍历左子树然后遍历右子树然后计算根节点 ); /以上为二叉树类以及其中包含的功能函数 node_type*build_node(stringx) 建立结点函数并将x存入结点的数据域里 ( node_type*new_node; new_node=newnode_type(x); return(new_node); )boolcalculator1(charOperatorA,charOperatorB) 判断运算符A和B优先级是否相等 ( if(OperatorA=OperatorB|(OperatorA=

18、*&OperatorB=/ )|(OperatorA=/&OperatorB=*)|(OperatorA=+&Operator B=-)|(OperatorA=-&OperatorB=+) returntrue; else returnfalse; ) boolcalculator2(charOperatorA,charOperatorB)/判 别 符 号 的 优 先 级 。AB,返 回 为TRUE,A=Bg回false if(OperatorA=() returnfalse; elseif(OperatorB=() returnfalse; elseif(Op

19、eratorB=) returntrue; elseif(calculator1(OperatorA,OperatorB) returnfalse; elseif(OperatorA=，A，) returntrue; elseif(OperatorB=A)returnfalse;elseif(OperatorA=*)|(OperatorA=/)returntrue; elseif(OperatorB=*)|(OperatorB=/)returnfalse; elseif(OperatorA=+)|(OperatorA=-)returntrue; else returnfalse; /采用了中序

20、遍历的算法来将二叉树r1拷贝到r2 boolisok(stringinfix)此函数验证式子是否正确，即是否 符合运算规则。 chartemp;临时字符变量 interror=0;/错误标记 intlb=0;左括号的个数 intrb=0;/右括号的个数 if(infix.size()=1&infix0!=-)/式子的长度为1且第一个 为负号 returnfalse; else if( ( IsOperator(infix0)&infix0!=-|/如果第一个是运 算符且不为左括号则表达式错误 IsOperator(infixinfix.size()-1)& infix0

21、!=(&infixinfix.size()-1!=)/如果最后一个字符 是运算符且第一个和最后一个不是括号则表达式错误 returnfalse; for(intm=0;minfix.size();m+) temp=infixm; if(m=0&temp=-&(isdigit(infix1)!=0| infix1=() temp=infix+m;/如果是负数 if(IsOperand(temp); /如果是数字则不进行操作 elseif(IsOperator(temp) ( if(temp=) ( rb+; if ( IsOperator(infixm+1)& (

22、infixm+1=+|infixm+1=-| infixm+1=*|infixm+1=/| infixm+1=A，|infixm+1=,) ) ( m+; if(infixm=)rb+; )else if(lsOperator(infixm+1) error+; elseif(temp=() ( lb+; if(infixm+1=() m+; lb+; else if(lsOperator(infixm+1)&infixm+1!=-) error+; else ( if(lsOperator(infixm+1)&infixm+1=() m+; lb+; ) else if(Is

23、Operator(infixm+1) error+; ) ) else error+; ) if(error=0&lb=rb)/如果没有错误且左右括号匹配 则返回逻辑真 return(true); else return(false); ) intmain() binary_treetree; stackNodeStack;/M算数栈 stackOpStack;/运算符栈 stringinfix; charchoice=y; system(cls); charc; while(choice=y|choice=Y) ( coutinfix; cout n; cout”表达式为：infix

24、n; if(isok(infix) ( for(inti=0;iinfix.size();i+) ( c=infixi; if(i=0&c=-)/若开始为负，则把零压入运算数 栈，把-压入运算符栈 ( binary_treetemp; temp.root=build_node(0); NodeStack.push(temp);将运算数压入数栈 OpStack.push(-);将运算符压入符栈 ) else if(IsOperand(c) ( stringtempstring; tempstring=c; while(i+1right_child=NodeStack.top().root; NodeStack.pop(); tree.root-left_child=NodeStack.top().root; NodeStack.pop(); NodeStack.push(tree); tree.root=NULL; OpStack.push(c); if(infixi+1=-) binary_treetemp; temp.root=build_node(0); NodeStack.push(temp); OpStack.push(-); +i; ) elseif(c=) ( while(OpStack.top()!=() ( OpStack.push(