|
#2
perfect2006-12-07 10:48
|
请各位赐教 ：
想用二叉树实现一个计算器的程序 ，该怎么实现那 ？
例如：
输入：1+2*(2+6) 然后输入‘=’，
输出 ：17
二叉数是怎么设计呢那 ？
最好是有c++的源程序的（由于是新手）。
2 回复
|
|
#3
xiechong2012-12-28 20:24
#include <iostream>
#include <string> #include <sstream> #include <stack> #include <cmath> using namespace std; bool IsOperator(string mystring) //判断字符串是否是运算符 { if(mystring == "-"||mystring == "+"||mystring == "*"||mystring == "/") return true; else return false; } bool IsOperator(char ops) //判断一个字符是否是运算符 { if(ops == '+'||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; } bool judge(string exp) //判断输入是否正确 { char check; int error=0,lb=0,rb=0,numofoperand=0,numofoperator=0; for(int m=0;m<exp.size();m++) { check=exp[m]; if(IsOperand(check)) { if(check=='.')//判断浮点型数据是否正确 { if(!(exp[m-1]>='0'&&exp[m-1]<='9')&&(exp[m+1]>='0'&&exp[m+1]<='9')) { error++; cout<<"浮点型数据输入有误!!!"<<endl; } } numofoperand++; } else if(IsOperator(check)) { if(check==')') { rb++; if(rb>lb) { error++; cout<<"右括号不可能大于左括号!!!"<<endl; } if(IsOperator(exp[m+1])&&(exp[m+1]=='+'||exp[m+1]=='-'||exp[m+1]=='*'||exp[m+1]=='/'||exp[m+1]==')')) { numofoperator++; m++; if(exp[m]==')') rb++; } else if(IsOperator(exp[m+1])||IsOperand(exp[m+1])) { error++; cout<<"右括号后不可能直接跟数据或左括号!!!"<<endl; } } else if(check=='(') { lb++; if(IsOperator(exp[m+1])&&exp[m+1]=='('||exp[m+1]=='-')//左括号右边只能是数字或者"-"号 { m++; m++; lb++; } else if(IsOperator(exp[m+1])) { error++; cout<<"左括号后运算符只能跟左括号!!!"<<endl; } } else { numofoperator++; if(IsOperator(exp[m+1])&&exp[m+1]=='(') { m++; lb++; } else if(IsOperator(exp[m+1])) { error++; cout<<"非括号的运算符不能直接接非括号运算符!!!"<<endl; } } } else { error++; cout<<check<<"为非法字符!!!"<<endl; } } if((error==0)&&(lb==rb)&&(numofoperand!=0)&&(numofoperator!=0)) return true; else return false; } bool addition(char OperatorA,char OperatorB) //A和B的优先级相同时返回TRUE. { if(OperatorA==OperatorB||(OperatorA=='*'&&OperatorB=='/')||(OperatorA=='/'&&OperatorB=='*')||(OperatorA=='+'&&OperatorB=='-')||(OperatorA=='-'&&OperatorB=='+')) return true; else return false; } bool TakesPrecedence(char OperatorA,char OperatorB) //按照优先级用if从最优至最后从上至下排列，从而达到比较A与B的优先级 { if(OperatorA=='(') return false; else if(OperatorB=='(') return false; else if(OperatorB==')') return true; else if(addition(OperatorA,OperatorB)) return false; else if((OperatorA=='*')||(OperatorA=='/')) return true; else if((OperatorB=='*')||(OperatorB=='/')) return false; else if((OperatorA=='+')||(OperatorA=='-')) return true; else return true; } //****************************************************************************// class BinNode{ public: string data; BinNode *left_child; BinNode *right_child; BinNode(string k) //构造函数 { data=k; left_child=NULL; right_child=NULL; } }; class binarytree//树的类 { public: BinNode *root; //根节点 binarytree(void){root=NULL;} //构造函数 void print(void){print(root);} void print(BinNode *p) { if(p!=NULL) { print(p->left_child); print(p->right_child); cout<<p->data<<" "; } } void evaluate(void){evaluate(root);} bool evaluate(BinNode *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()); 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) { cout<<"除数为零!!!运算出错"; return 0; } else num=num1/num2; } stringstream bob; bob<<num; string suzzy(bob.str()); prt->data=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; else { r1=build_node(r2->data); copy(r1->left_child,r2->left_child); copy(r1->right_child,r2->right_child); } } //******************************************************************************************* int main() { binarytree etree;//创建树 stack<binarytree> NodeStack;//创建栈 stack<char> OpStack; string exp;//声明字符串 char choice='y';//choice为选择是否继续运行程序的判断 char c;//为下面创建二叉树进行取字符 while(choice=='y'||choice=='Y') { cout<<"请输入一个有效的表达式:"<<endl; getline(cin,exp); cout<<" "<<endl<<"-----------------------------"<<endl; if(judge(exp))//如果判断出表达式没有错误，则进行创建二叉树并计算 { cout<<"表达式格式正确"<<endl; for(int i=0;i<exp.size();i++) { c=exp[i]; if(i==0 && c=='-') //若开始为负，则把零压入运算数栈，把'-'压入运算符栈 { binarytree temp; temp.root=build_node("0"); NodeStack.push(temp); OpStack.push('-'); } else if(IsOperand(c))//若是操作数，则判断下一位是不是操作数，并且将整个数据创建一个子树并压栈 { string tempstring=""; tempstring=tempstring+c; while(i+1<exp.size()&&IsOperand(exp[i+1])) //当当前位置的下一位也是操作数时，将整个数字放在一个临时数据串中 { tempstring+=exp[++i]; } binarytree temp;//为这个数据创建一个子树 temp.root=build_node(tempstring); NodeStack.push(temp);//将子树的根节点指针压栈 } else if(c=='+'||c=='-'||c=='/'||c=='*')//如果是操作符 { if(OpStack.empty())//如果栈空，则直接压栈 OpStack.push(c); else if(OpStack.top()=='(')//如果栈顶是左括号，则压栈 OpStack.push(c); else if(TakesPrecedence(c,OpStack.top()))//判断栈顶字符和当前字符的优先级，当c优先级高或者个优先级相同时，将c压栈 OpStack.push(c); else//其他普通情况 { while(!OpStack.empty()&&(TakesPrecedence(OpStack.top(),c)||addition(OpStack.top(),c)))//这里将在一般情况下，对已经压栈的操作数和操作符进行创建子树处理，并将当前字符压栈 { binarytree 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.push(c); } } else if(c=='(') //若中间遇到括号，则判断下一位是否为'-' { OpStack.push(c); if(exp[i+1]=='-') { binarytree temp; temp.root=build_node("0"); NodeStack.push(temp); OpStack.push('-'); i++; } } else if(c==')')//如果遇到右括号，则创建子树，直到与左括号匹配成功，这里和前一步骤的操作基本相同 { while(OpStack.top()!='(') { binarytree 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())//如果栈非空，则继续进行出栈、判断、计算，直到栈空，栈中的结果为最终的计算结果 { binarytree 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; } //cout<<"Postfix traversal:"; //etree.print(); //cout<<endl; etree.evaluate(); cout<<"表达式计算结果:"<<exp<<"="<<etree.root->data<<endl; cout<<"------------------------------------------------"<<endl; cout<<endl<<"是否继续计算下一个表达式<y/n>:"; cin>>choice; getchar(); } else { cout<<"**************************"<<endl; cout<<"错误：表达式有误"<<endl; cout<<endl<<"是否继续计算下一个表达式<y/n>:"; cin>>choice; getchar(); } } return 0; } |
1