哪位高手帮帮我 我憋了三天 还是大家帮我把 越完全越好 在下实在是学问太少了~~~ 1. 表达式求值。 【基本要求】 1)读入原表达式(括号),创建对应二叉树叉树。 2)对二叉树进行前序遍历、中序遍历、后续遍历(非递归)。 3)后缀表达式和前缀表达式求解原表达式的值。 对非法表达式格式能予以判断。 【选作内容】 原表达式中有三种括号,先作(),再作[],最后是{}。判断括号的优先级别建立二叉树。
怎么说??? 我编了一点点 可是建立树的时候不能够进行括号的判断 就是如果表达式里面有括号就不行了 还有 就是说 不能区分数字和字符呀 怎么才能求值呢??? 要怎么弄呢????? //定义含有三个指针的结点 typedef struct BiTNode{ char data; int op; struct BiTNode *lchild, *rchild, *parent; }BiTNode, *BiTree;
int length; BiTNode *CreatTree(char a[]) { //建立二叉树 BiTNode *t; BiTNode *p; BiTNode *s; BiTNode *q; BiTNode *T; bool cre; cre=false;
/*t=(BiTNode *)malloc(sizeof(BiTNode)); t->lchild=NULL; t->rchild=NULL; t->parent=NULL; */ t=(BiTNode *)malloc(sizeof(BiTNode)); t->lchild=NULL; t->rchild=NULL; t->parent=NULL; t->data=a[0]; t->op=0; p=t; char in; for(int i=1;i<length;i++) { in=a[i]; switch(in) { case '+': t=(BiTNode *)malloc(sizeof(BiTNode)); t->parent =NULL; t->rchild=NULL; t->lchild =NULL; t->data=a[i]; t->op=1; s=p; while(s!=NULL) { q=s; s=s->parent; } q->parent=t; t->lchild=q; //q->rchild =NULL; t->parent =NULL; p=t; break; case '-': t=(BiTNode *)malloc(sizeof(BiTNode)); t->rchild=NULL; t->data=a[i]; t->op=1; s=p; while(s!=NULL) { q=s; s=s->parent; } q->parent=t; t->lchild=q; // q->rchild =NULL; t->parent =NULL; p=t; break;
case '*': t=(BiTNode *)malloc(sizeof(BiTNode)); t->lchild=NULL; t->rchild=NULL; t->data=a[i]; t->op=-1; t->parent =NULL;
if(p->parent ==NULL) { p->parent =t; t->lchild =p; }
else { while(p->parent !=NULL&&p->parent ->op !=1) p=p->parent ; if(p->parent ==NULL) { p->parent =t; t->lchild =p;
} else { p->parent ->rchild =t; t->parent =p->parent ; t->lchild =p; p->parent =t; }
}
p=t; break;
case '/': t=(BiTNode *)malloc(sizeof(BiTNode)); t->lchild=NULL; t->rchild=NULL; t->data=a[i]; t->op=-1; t->parent =NULL;
if(p->parent ==NULL) { p->parent =t; t->lchild =p; }
else { while(p->parent !=NULL&&p->parent ->op !=1) p=p->parent ; if(p->parent ==NULL) { p->parent =t; t->lchild =p;
} else { p->parent ->rchild =t; t->parent =p->parent ; t->lchild =p; p->parent =t; }
}
p=t; break; default:
t=(BiTNode *)malloc(sizeof(BiTNode)); t->lchild=NULL; t->rchild=NULL; t->parent=p; t->data=a[i]; t->op=0; p->rchild=t; p=t; } }
while(p) { T=p; p=p->parent ; } cout<<T->data <<endl; return T; } //CreatTree
以下是1996年高级程序员考试的下午第5题(计算器模拟程序),写的非常的经典,但只有+,-,*和/四个运算,但可以在它的基础上修改获得其他的运算: #include <stdio.h> int add(int x,int y) {return x+y;} int sub(int x,int y) {return x-y;} int mul(int x,int y) {return x*y;} int div(int x,int y) {return x/y;} int (*func[])()={add,sub,mul,div}; int num,curch; char chtbl[]="+-*/()="; char corch[]="+-*/()=0123456789"; int getach() { int i; while(1) { curch=getchar(); if(curch==EOF) return -1; for(i=0;corch[i]&&curch!=corch[i];i++); if(i<strlen(corch)) break; } return curch; }
int getid() { int i; if(curch>='0'&&curch<='9') { for(num=0;curch>='0'&&curch<='9';getach()) num=10*num+curch-'0'; return -1; } else { for(i=0;chtbl[i];i++) if(chtbl[i]==curch) break; if(i<=5) getach(); return i; } }
int cal() { int x1,x2,x3,op1,op2,i; i=getid(); if(i==4) x1=cal(); else x1=num; op1=getid(); if(op1>=5) return x1; i=getid(); if(i==4) x2=cal(); else x2=num; op2=getid(); while(op2<=4) { i=getid(); if(i==4) x3=cal(); else x3=num; if((op1/2==0)&&(op2/2==1)) x2=(*func[op2])(x2,x3); else { x1=(*func[op1])(x1,x2); x2=x3; op1=op2; } op2=getid(); } return (*func[op1])(x1,x2); }
void main(void) { int value; printf("Please input an expression:\n"); getach(); while(curch!='=') { value=cal(); printf("The result is:%d\n",value); printf("Please input an expression:\n"); getach(); } } 不要忘了‘=’号!