二叉树四则运算

二叉树四则运算一．程序代码#includeiostream#includestring#includecmath#includesstream#includestackusingnamespacestd;boolIsOperator(stringmystring){if(mystring==-||mystring==+||mystring==/||mystring==*||mystring==^)return(true);elsereturn(false);}boolIsOperator(charops){if(ops==+||ops==-||ops==*||ops==/||ops==^||ops=='('||ops==')')return(true);elsereturn(false);}classnode_type{public:stringdata;node_type*left_child;node_type*right_child;node_type(stringk){data=k;left_child=NULL;right_child=NULL;}};classbinary_tree{public:node_type*root;binary_tree(void){rrot=NULL;}voidprint(void){print(root);}voidprint(node_type*p);voidevaluate(void){evaluate(root);}voidevaluate(node_type*prt){if(IsOperator(prt-data)&&!IsOperator(prt-left_child-data)&&!IsOperator(prt-right_child-data)){intnum=0;intnum1=atoi(prt-left_child-data.c_str());intnum1=atoi(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==^)num=pow(num1,num2);stringstreambob;bobnum;stringsuzzy(bob.str());prt-data=suzzy;prt-left_child=NULL;prt-right_child=NULL;}elseif(prt-left_child==NULL&&prt-right_child==NULL);else{evaluate(prt-left_child);evaluate(prt-right_child);evaluate(prt);}}voidclear_help(void){clear_help(root);}coidclear_help(node_type*rt){if(rt!=NULL){clear_help(rt-left_child);clear_help(rt-right_child);deletert;}}};node_type*build_node(stringx){node_type*new_node;new_node=newnode_type(x);return(new_node);}voidbinary_tree::print(node_type*p){if(p!=NULL){print(p-left_child);print(p-right_child);coutp-data;}}boolIsOperand(charch){if((ch='0')&&(ch='9'))returntrue;elsereturnfalse;}boolTakesPrecedence(charOperatorA,charOperatorB){if(OperatorA=='(')returnfalse;elseif(OperatorB=='(')returnfalse;elseif(OperatorB==')')returntrue;elseif((OperatorA=='^')&&(OperatorB=='^'))returnfalse;elseif(OperatorA=='^')returntrue;elseif(OperatorB=='^')returnfalse;elseif((OperatorA=='*')&&(OperatorA=='/'))returntrue;elseif((OperatorB=='*')&&(OperatorB=='/'))returnfalse;elsereturntrue;}voidcopy(node_type*&r1,node_type*r2){if(r2==NULL)r1=NULL;else{r1=build_node(r2-data);copy(r1-left_child,r2-left_child);copy(r1-right_child,r2-right_child);}}boolisok(stringexp){charcheck;interror=0,lb=0,rb=0;copy(r1-left_child,r2-left_child);copy(r1-right_child,r2_right_child);}}boolisok(stringexp){charcheck;interror=0,lb=0,rb=0;for(intm=0;mexp.size();m++){check=exp[m];if(IsOperand(ckeck)){}elseif(IsOperator(check)){if(chek==')'){rb++;if(IsOperator(exp[m+1])&&(exp[m+1]==+||exp[m+1]==-||exp[m+1]==*||exp[m+1]==/||exp[m+1]==^||exp[m+1]==')')){m++;if(exp[m]==')')rb++;}elseif(IsOperator(exp[m+1]))error++;}elseif(check=='('){lb++;if(IsOperator(exp[m+1])&&exp[m+1]=='('){m++;lb++;}elseif(IsOperator(exp[m+1])&&exp[m+1]=='('){m++;lb++;}elseif(IsOperator(exp[m+1]))error++;}else{if(IsOperator(exp[m+1])&&exp[m+1]=='('){m++;lb++;}elseif(IsOperator(exp[m+1]))error++;}}elseerror++;}if(error==0&&lb==rb)return(true);elsereturn(false);}intmain(){binary_treeetree;stackbinary_treeNodeStack;stackcharOpStack;stringinfix;charchoice='y';charc;while(choice=='y'||choice=='Y'){cout\n\nIntroducetheExpression(nospaces):;cinubfixlcout------------------endl;coutExpression:infixendl;if(isok(infix)){for(inti=0;iinfix.size();i++){c=infix[i];if(IsOperand(c)){stringtempstring;tempstring=tempstring+c;if(i+1infix.size()&&IsOperand(infix[i+1])){while(i+1infix.size()&&IsOperand(infix[i+1]))tempstring=tempstring+infix[++i];}binary_treetemp;temp.rrot=build_node(tempstring);NodeStack.push(temp);}elseif(c=='+'||c=='-'||c=='*'||c=='/'||c=='^'){if(OpStack.empty())OpStack.push(c);elseif(OpStack.top()=='(')OpStack.push(c);elseif(TakesPrecedence(c,OpStack.top()))OpStack.push(c);else{while(!OpStack.empty()&&TakesPrecedence(OpStack.top(),c)){binary_treetemp_tree;stringthisstring=;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.push(c);}}elseif(c=='(')OpStack.push(c);elseif(c==')'){while(OpStack.top()!='('){binary_treetemp_tree;stringthisstring=;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_treetemp_tree;stringthisstring=;thisstring=thisstring+OpStack.top();OpStack.pop();etree.root=build_node(thisstring);copy(temp_tree.root,NodeStack.top().