数据结构课程设计共6个

#include<iostream> #include<string> #include<stack> #include"Tree.h" //////////////////////Checks if expression if ok//////////////// bool isok(string exp) //此函数验证式子是否正确，即是否符合运算规则。 { char check; int error=0; int lb=0; int rb=0; if(exp.size()==1)return false; else if((IsOperator(exp[0])||IsOperator(exp[exp.size()-1]))&&exp[0]!='('&&exp[exp.size()-1]!=')') //此处若不加，在遇到某些式子时，会出现非法操作。 return false; for(int m=0;m<exp.size();m++) { check=exp[m]; if(IsOperand(check)); //如果是数字，跳过，不管。 else if(IsOperator(check)) { if(check==')') { 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++; } else if(IsOperator(exp[m+1])) error++; } else if(check=='(') { lb++; if(exp[m+1]=='(') { m++; lb++; } else if(IsOperator(exp[m+1])) error++; } else { if(IsOperator(exp[m+1])&&exp[m+1]=='(') { m++; lb++; } else if(IsOperator(exp[m+1])) error++; } } else error++; } if(error==0&&lb==rb) return(true); else return(false); } //////////////////////////////////////////////////////////////////// int main() //主函数开始 { binary_tree etree; stack<binary_tree>NodeStack; stack<char>OpStack; string infix; char choice='y'; char c; while(choice=='y'||choice=='Y') { cout<<"\n\n请输入表达式，不要带空格;\n"; cin>>infix; cout<<"--------------------------------------------------------------------------------"<<'\n'; cout<<"表达式为: "<<infix<<'\n'; if(isok(infix)) { for(int i=0;i<infix.size();i++) { c=infix[i]; if(IsOperand(c)) { string tempstring; tempstring=tempstring+c; while(i+1<infix.size()&&IsOperand(infix[i+1])) { tempstring=tempstring+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(TakesPrecedence(c,OpStack.top())) OpStack.push(c); else { while(!OpStack.empty()&&(TakesPrecedence(OpStack.top(),c)||addition(OpStack.top(),c))) { 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.push(c); } } else if(c=='(') OpStack.push(c); 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; } } cout<<"打印结点如下: "; etree.print(); binary_tree temp; copy(temp.root,etree.root); cout<<'\n'; cout<<"结点个数为："<<etree.counter()<<'\n'; cout<<"以下是，中间的计算结果："<<'\n'; etree.evaluate(); cout<<'\n'; cout<<"结果是: "; cout<<etree.root->data<<'\n'; cout<<"--------------------------------------------------------------------------------"<<'\n'; cout<<"是不是要进行二叉树排序，并显示？若是升序点A，若是降序点B,若不是点C。"<<'\n'; char c1; cin>>c1; if(c1=='A'||c1=='a') { binary_tree temp1; copy(temp1.root,temp.order().root); //此处代码无需再改 temp1.inprint(temp1.root);//前边程序有错,此处TEMP1为空.所以没有输出. } else if(c1=='B'||c1=='b') { binary_tree temp1; copy(temp1.root,temp.order().root); temp1.deprint(temp1.root); } cout<<"\n\nRun Program again?Enter<y/n>:"; cin>>choice; } else { cout<<"************************************************"<<'\n'; cout<<"ERROR:Invalid Expression"<<'\n'; cout<<"************************************************"<<'\n'; cout<<"\n\nRun Program again?Enter<y/n>:"; cin>>choice; } } return 0; }