工大数据结构第三章作业

const char& Match(const char &ch1,const char &ch2) { int i=0,j=0; while(opera[i]!=ch1) i++; while(opera[j]!=ch2) j++; return match[i*7+j]; }

class TNode {

public: TNode(string str=\ strcpy(id,str.c_str()); bit=b; left=l; right=r; parent=p; } TNode(const char ch,TNode *l=NULL,TNode *r=NULL,TNode *p=NULL){ id[0]=ch; id[1]=0; bit=0; left=l; right=r; parent=p; } const TNode& operator=(const TNode& tn){ strcpy(id,tn.id); bit=tn.bit; left=tn.left; right=tn.right; parent=tn.parent; } char id[MAXSIZE]; int bit; TNode *parent,*left,*right; };

int ReadExpr(char *str,char *expr,int start,int bit,int &length) { length=0; if(str[start]==0){ expr[0]=0; return 0; } else if(str[start]=='*'||str[start]=='/'||str[start]=='('||str[start]==')'||str[start]=='@'){

expr[0]=str[start]; expr[1]=0; length=1; return 2; } else if(bit||isdigit(str[start])||str[start]=='.'){ //read a digit string int b=0; int k=0; //index for expr while(str[start]=='+'||str[start]=='-'){ //read sign if(str[start]=='-') b++; start++; length++; } if(b%2) expr[k++]='-'; while(isdigit(str[start])||str[start]=='.'){ expr[k++]=str[start++]; length++; } expr[k]=0; return 1; } else if(str[start]=='+'||str[start]=='-'){ //read a oper '+' or '-' int b=0; while(str[start]=='+'||str[start]=='-'){ if(str[start]=='-') b++; start++; length++; } if(b%2) expr[0]='-'; else expr[0]='+'; expr[1]=0; return 2; } else return -1; //error }

TNode *Translate(const string &str) //translate a expression string to a expression tree { char substr[MAXSIZE]; Stack cstk; Stack tstk; char *tempstr=new char[str.length()+2]; int start=0,bit=1; int t,length; strcpy(tempstr,str.c_str());

tempstr[str.length()]='@'; tempstr[str.length()+1]=0; cstk.push('@'); t=ReadExpr(tempstr,substr,start,bit,length); while(cstk.top()!='@'||substr[0]!='@'){ if(t==1){ //is a digit string TNode *np=new TNode(substr,1); tstk.push(np); bit=0; } else if(t==2){ //is a oper if(substr[0]=='(') bit=1; else bit=0; char tch=cstk.top(); if(Match(tch,substr[0])=='>'){ TNode *right=tstk.top(); tstk.pop(); TNode *left=tstk.top(); tstk.pop(); TNode *np=new TNode(tch,left,right); left->parent=np; right->parent=np; tstk.push(np); cstk.pop(); continue; } else if(Match(tch,substr[0])=='<') cstk.push(substr[0]); else cstk.pop(); } start+=length; t=ReadExpr(tempstr,substr,start,bit,length); } delete[] tempstr; return tstk.top(); }

void print(TNode *root) { if(root->left){ print(root->left); print(root->right); cout<id; } else cout<id; }

void prints(TNode*); double solve(TNode*); void printExpr(string str) { TNode *root=Translate(str); cout<<\后缀式:\ print(root); cout<

cout<<\中缀式:\ prints(root); cout<<\}

void prints(TNode *root) //将逆波兰式用中缀形式打印出来 { if(root->left==NULL) cout<id; //is a leaf else if(root->parent==NULL){ prints(root->left); cout<id; prints(root->right); } else if(root->parent->left==root&&Match(root->id[0],root->parent->id[0])=='>'){ prints(root->left); cout<id; prints(root->right); } else if(root->parent->right==root){ if(Match(root->parent->id[0],root->id[0])=='<'||root->parent->id[0]=='+'){ prints(root->left); cout<id; prints(root->right); } else{ cout<<\ prints(root->left); cout<id; prints(root->right); cout<<\ } } else{ cout<<\ prints(root->left); cout<id; prints(root->right);