利用二叉树以及栈对算术表达式实现四则运算等计算功能代码.doc

#include #include #include #include #include using namespace std;bool IsOperator(string mystring) /判断字符串是否是运算符if(mystring = -|mystring = +|mystring = *|mystring = /|mystring = |mystring = %)return true;else return false;bool IsOperator(char ops) /判断一个字符是否是运算符if(ops = +|ops= -|ops= *|ops= /|ops= |ops= %|ops=(|ops=)return true;elsereturn false;bool IsOperand(char ch) /判断是否是数字if (ch=0)&(ch=9)|(ch=.)return true;elsereturn false;bool isok(string exp) /判断输入是否正确char check;int error=0,lb=0,rb=0,numofoperand=0,numofoperator=0;for(int m=0;m=0&expm-1=0&expm+1=9) error+; cout浮点型数据输入有误!lb)error+;cout右括号不可能大于左括号!endl;if(IsOperator(expm+1)&(expm+1=+|expm+1=-|expm+1=*|expm+1=/|expm+1=|expm+1=)|expm+1=%)numofoperator+;m+;if(expm=)rb+;else if(IsOperator(expm+1)|IsOperand(expm+1)error+;cout右括号后不可能直接跟数据或左括号!endl; else if(check=()lb+;if(IsOperator(expm+1)&expm+1=()m+;lb+;else if(IsOperator(expm+1)error+;cout左括号后运算符只能跟左括号!endl;else numofoperator+;if(IsOperator(expm+1)&expm+1=()m+;lb+;else if(IsOperator(expm+1)error+;cout非括号的运算符不能直接接非括号运算符!endl;elseerror+;coutcheck为非法字符!left_child);print(p-right_child); coutdatadata)&!IsOperator(prt-left_child-data)&!IsOperator(prt-right_child-data)float num=0;float num1=atof(prt-left_child-data.c_str();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=/)if(num2=0.0)coutdata=)num=pow(num1,num2);else if(prt-data=%)if(num2=0.0)cout除数为零!运算出错;return 0; else num=(long)num1%(long)num2;stringstream bob;bobdata=suzzy;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);return 1;void clear_help(void)clear_help(root);void clear_help(BinNode *rt)if(rt!=NULL)clear_help(rt-left_child);clear_help(rt-right_child);delete rt;BinNode *build_node(string x)BinNode *new_node;new_node=new BinNode(x);return (new_node);void copy(BinNode *&r1,BinNode* r2)/请注意这里的*&!if(r2=NULL)r1=NULL;elser1=build_node(r2-data);copy(r1-left_child,r2-left_child);copy(r1-right_child,r2-right_child);/*/int main()binary_tree etree;stack NodeStack;stack OpStack;string infix;char choice=y;char c;while(choice=y|choice=Y)coutendlIntroduce the Expression:endl;getline(cin,infix);for(int j=0;jinfix.size();j+)if(infixj= ) infix.erase(j,1); j-;cout 华丽的分割线endl-endl;coutExpression: infixendl;if(isok(infix)for(int i=0;iinfix.size();i+)c=infixi;if(i=0 & c=-) /若开始为负，则把零压入运算数栈，把-压入运算符栈 binary_tree temp; temp.root=build_node(0); NodeStack.push(temp); OpStack.push(-); elseif(IsOperand(c)string tempstring=;tempstring=tempstring+c;while(i+1right_child=temp_tree.root;temp_tree.root=NULL;copy(temp_tree.root,NodeStack.top().root);etree.root-left_child=temp_tree.root;NodeStack.pop();temp_tree.root=NULL;copy(temp_tree.root,etree.root);NodeStack.push(temp_tree);etree.root=NULL;OpStack.push(c); 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()!=()binary_tree temp_tree;string thisstring=;thisstring=thisstring+OpStack.top();OpStack.pop();etree.root=build_node(thisstring);copy(temp_tree.root,NodeStack.top().root); NodeStack.pop();etree.root-right_child=temp_tree.root;temp_tree.root=NULL;copy(temp_tree.root,NodeStack.top().root);etree.root-left_child=temp_tree.root;NodeStack.pop();temp_tree.root=NULL;copy(temp_tree.root,etree.root);NodeStack.push(temp_tree);etree.root=NULL;OpStack.pop();while(!OpStack.empty()binary_tree temp_tree;string thisstring=;thisstring=thisstring+OpStack.top();OpStack.pop();etree.root=build_node(thisstring);copy(temp_tree.root,NodeStack.top().root);NodeStack.pop();etree.root-right_child=temp_tree.root; temp_tree.root=NULL;copy(temp_tree.root,NodeStack.top().root);etree.root-left_child=temp_tree.root;NodeStack.pop();temp_tree.root=NULL;copy(temp_tree.root,etree.root);NodeStack.push(temp_tree);if(!OpStack.empty() etree.root=NULL; coutPostfix traversal:;etree.print();coutendl;etree.