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

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

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

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

4、t;<<endl;cout<<" 二叉树计算器"<<endl;cout<<"*"<<endl;char c;while(choice='y'|choice='Y') cout<<"n请输入表达式:n" cin>>infix; cout<<"-"<<'n' cout<<"表达式为: "<<infix<<

5、9;n' 2.进行简单的四则运算对输入的表达式首先判断正误，然后按照运算的优先级分别进行运行，并且分别输出每步运算的结果。先进行乘方，然后乘除，最后再计算加减，先算括号内后算括号外，正确度一目了然。（1）对于负数也可以进行相应的加减乘除以及乘方的运算。对于负数的运算，也和正数一样，先算括号内的后算括号外的，其次算乘方，再算乘除，最后进行加减的运算。负数的加减乘除：负数的乘方运算：（1） 正指数幂运算：（2） 负指数幂运算： 可以进行小数的计算，对于小数采用浮点数的存储方式和输出方式，计算精度可以取到小数点后五位。小数的加减乘除：小数的运算，依然按照先乘除后加减，先算括号内后算括号外的顺

6、序运算。小数的乘方和开方：（1） 正小数幂次方：（2） 负小数幂次方：（3） 开正小数次方：（4） 开负小数次方：五测试与结论 此报告在C-Free5.0环境下进行测试。C-Free是一款C/C+集成开发环境（IDE）。C-Free中集成了C/C+代码解析器，能够实时解析代码，并且在编写的过程中给出智能的提示。C-Free提供了对目前业界主流C/C+编译器的支持，可以在C-Free中轻松切换编译器。可定制的快捷键、外部工具以及外部帮助文档，使在编写代码时得心应手。完善的工程/工程组管理使你能够方便的管理自己的代码。以下是各种测试用例。注：较为简单和常规的测试用例在上一部分“算法的实现”中已经给

7、出，下面只给出一些具有代表性的测试用例。1.表达式错误的情况在表达式错误的情况下，程序能够运行，但是不能够正常运算，而是给出错误的提示信息，提醒重新输入正确的表达式。下图表示以0作为除数时程序所给的提示信息“Infinity”下图为计算表达式0（-3）时候的输出，由于表达式没有数学意义，所以也就没有正确的结果，因而程序运行后得到的结果是“Infinity”.下图显示的是输入的表达式不符合数学规律时的错误提示信息。下图表示输入表达式中含有不合法的字符，例如字母时候，程序运行时所给的提示信息。下图所示为表达式错误的另外一种情形，即输入的括号多余的情形。下面两个测试用例，为表达式输入错误的情况，在下

8、列两个表达式中，有不合法的运算符，比如表达式前面有运算符或者表达式后面还有运算符。2.所要计算的数据过大或过小的情况当输入的数据很大或者很小时，会致使结果很大或者很小，此时，若是结果的大小超过数据类型的表示范围，那么就会产生错误，并且显示错误信息。若是没有超出数据的表示范围，那么就会用浮点数来表示比较大或者比较小的数据。六.总结与思考七附源代码#include<iostream> #include<cstring>#include<cmath> #include<sstream>#include<stack> /利用stack头文件来

9、构造两个栈用来存储数据和运算符 using namespace std; bool IsOperator(string mystring)/判断参数string是否是运算符 是返回逻辑值true if(mystring="-"|mystring="+"|mystring="/"|mystring="*"|mystring="") return(true); else return(false); bool IsOperator(char ops)/重载 if(ops='+'|op

10、s='-'|ops='*'|ops='/'|ops=''|ops='('|ops=')') return(true); else return(false); bool IsOperand(char ch)/ 验证是否是数 if(ch>='0')&&(ch<='9')|ch='.') return true; else return false; /以上三个是起判断作用的函数 class node_type/结点类 publ

11、ic: string data; /采用字符串形式存储数据 node_type *left_child; /左孩子指针 node_type *right_child; /右孩子指针 node_type(string k) /构造函数 data=k; left_child=NULL; right_child=NULL; ;/以上是二叉树的结点 为二叉树的基本结构 class binary_tree /二叉树类 public:binary_tree(void)root=NULL; /构造函数 建立根节点 node_type *root; /根节点void evaluate(void) /对二叉树的

12、根节点进行运算 evaluate(root); void evaluate(node_type *prt)/重载 当参数为二叉树的运算符结点时/且左孩子和右孩子不是运算符时对二叉树进行运算 if(IsOperator(prt->data)&&!IsOperator(prt->left_child->data)&&!IsOperator(prt->right_child->data) float num=0; float num1=atof(prt->left_child->data.c_str();/将data转换成ch

13、ar型数据 然后用atof将char转换成浮点数 float num2=atof(prt->right_child->data.c_str(); if(prt->data="+") num=num1+num2; else if(prt->data="-") num=num1-num2; else if(prt->data="*") num=num1*num2; else if(prt->data="/") num=num1/num2; else if(prt->data=&

14、quot;") num=pow(num1,num2); cout<<num<<'t'/对每个结点计算后的中间结果 stringstream bob;/定义一个流对象 bob<<num;/将数据存到bob对象里 string temp(bob.str(); /将bob里的数据转换成string然后赋值给temp prt->data=temp;/将计算的结果赋值给当前结点 prt->left_child=NULL; /然后删除左右孩子结点 prt->right_child=NULL; else if(prt->l

15、eft_child=NULL&&prt->right_child=NULL);/如果左后孩子都为空则不作操作 else evaluate(prt->left_child); evaluate(prt->right_child); evaluate(prt);/如果不满足上面的条件 则先运算左孩子 再运算右孩子 再运算本身 /上述函数为一个递归调用 即后序遍历 /从根节点开始计算 如果子树中不为空且不为数据则先遍历左子树然后遍历右子树然后计算根节点 ;/以上为二叉树类以及其中包含的功能函数 node_type *build_node(string x) /建立结

16、点函数并将x存入结点的数据域里 node_type *new_node; new_node=new node_type(x); return(new_node); bool calculator1(char OperatorA,char OperatorB) /判断运算符A和B优先级是否相等 if(OperatorA=OperatorB|(OperatorA='*'&&OperatorB='/')|(OperatorA='/'&&OperatorB='*')|(OperatorA='+

17、9;&&OperatorB='-')|(OperatorA='-'&&OperatorB='+') return true; else return false; bool calculator2(char OperatorA,char OperatorB) /判别符号的优先级。A>B，返回为TRUE,A<=B返回false if(OperatorA='(') return false; else if(OperatorB='(') return false; else

18、if(OperatorB=')') return true; else if(calculator1(OperatorA,OperatorB) return false; else if(OperatorA='') return true; else if(OperatorB='') return false; else if(OperatorA='*')|(OperatorA='/') return true; else if(OperatorB='*')|(OperatorB='/

19、9;) return false; else if(OperatorA='+')|(OperatorA='-') return true; else return false; /采用了中序遍历的算法来将二叉树r1拷贝到r2 bool isok(string infix)/此函数验证式子是否正确，即是否符合运算规则。 char temp;/临时字符变量 int error=0;/错误标记 int lb=0; /左括号的个数 int rb=0;/右括号的个数 if(infix.size()=1 && infix0!='-')/式子的

20、长度为1且第一个为负号 return false;else if(IsOperator(infix0)&& infix0!='-' |/如果第一个是运算符且不为左括号则表达式错误 IsOperator( infixinfix.size()-1)&&infix0!='('&&infixinfix.size()-1!=')')/如果最后一个字符是运算符且第一个和最后一个不是括号则表达式错误 return false; for(int m=0;m<infix.size();m+) temp=infi

21、xm; if(m=0 && temp='-' && (isdigit(infix1)!=0 | infix1='(' ) )temp=infix+m;/如果是负数 if(IsOperand(temp); /如果是数字则不进行操作 else if(IsOperator(temp) if(temp=')') rb+; if(IsOperator(infixm+1)&&(infixm+1='+'|infixm+1='-'|infixm+1='*'|infix

22、m+1='/'|infixm+1=''|infixm+1=')') m+; if(infixm=')') rb+; else if(IsOperator(infixm+1) error+; else if(temp='(') lb+; if(infixm+1='(') m+; lb+; else if(IsOperator(infixm+1)&&infixm+1!='-') error+; else if(IsOperator(infixm+1)&&i

23、nfixm+1='(') m+; lb+; else if(IsOperator(infixm+1) error+; else error+; if(error=0&&lb=rb) /如果没有错误且左右括号匹配则返回逻辑真 return(true); else return(false); int main()binary_tree tree; stack<binary_tree> NodeStack;/运算数栈 stack<char> OpStack;/运算符栈 string infix;char choice='y's

24、ystem("cls");char c;while(choice='y'|choice='Y') cout<<"n请输入表达式:n" cin>>infix; cout<<"-"<<'n' cout<<"表达式为: "<<infix<<'n' if(isok(infix) for(int i=0;i<infix.size();i+) c=infixi;if(i=0

25、&& c='-') /若开始为负，则把零压入运算数栈，把'-'压入运算符栈binary_tree temp; temp.root=build_node("0"); NodeStack.push(temp);/将运算数压入数栈 OpStack.push('-');/将运算符压入符栈 elseif(IsOperand(c) string tempstring; tempstring=c; while(i+1<infix.size()&&IsOperand(infixi+1) tempstrin

26、g+=infix+i; binary_tree temp; temp.root=build_node(tempstring); NodeStack.push(temp); else if(c='+'|c='-'|c='*'|c='/'|c='') if(OpStack.empty() OpStack.push(c); else if(OpStack.top()='(') OpStack.push(c); else if(calculator2(c,OpStack.top() OpStack.push

27、(c); else while(!OpStack.empty()&&(calculator2(OpStack.top(),c)|calculator1(OpStack.top(),c) string temp; temp=OpStack.top(); OpStack.pop();tree.root=build_node(temp);tree.root->right_child=NodeStack.top().root;NodeStack.pop();tree.root->left_child=NodeStack.top().root; NodeStack.pop()

28、; NodeStack.push(tree); tree.root=NULL; OpStack.push(c); else if(c='(') /若中间遇到括号，则判断下一位是否为'-'OpStack.push(c); if(infixi+1='-')binary_tree temp;temp.root=build_node("0"); NodeStack.push(temp);OpStack.push('-');+i; else if(c=')') while(OpStack.top()!='(') string temp; temp=OpStack.top(); OpStack.pop();/将栈顶内容取出然后作出栈操作 tree.root=build_node(temp);tree.root->right_child=NodeStack.top().root;NodeStack.pop(); tree.root->left_child=NodeStack.top().ro