BIT2013年上机第三题

题目要求

3. 编写程序：输入表达式，出相应二叉树的先遍历结果

输入： a+b*(c -d) -e/f

输出： -+a*b -cd/ef

解题思路

一个编程题没有思路是没有任何解决办法的，所以正要的是培养解题的思路。

我素来很讨厌这样的题目，总感觉有种胆怯在里面。这次看了刘汝佳的算法竞赛入门经典的表达式树，感觉真的是绝妙极了。

下次可以深入的思考一下，如果换成struct或者用class来表示结点呢？

中序遍历结果呢，后序遍历呢？

......

代码如下：

主要代码是书本上的

#include<iostream>#include<string>using namespace std;const int maxn = 1000;int lch[maxn],rch[maxn]; //每个节点的左右孩子编号char op[maxn]; //节点的字符int cnt = 0; //节点数//s的[x,y)作为范围int build_tree(char *s,int x,int y){	int c1=-1,c2=-1,p=0,u;//c1,c2分别记录出现在括号外的最右边的加减号和乘除号	//当前表达式的长度为1，则直接为一棵树	if(y-x==1){		u = cnt++; //第u个节点		lch[u]=rch[u]=-1;		op[u]=s[x];		return u;	}	//p==0表示在括号外	for(int i=x;i<y;i++){		switch(s[i]){			case '(':p++;break;			case ')':p--;break;			case '+':			case '-':				if(p==0) c1 = i;				break;			case '*':			case '/':				if(p==0) c2 = i;				break;		}	}	if(c1<0) c1 = c2; //括号外没有+或者-，则选择括号外的*或/	if(c1<0) return build_tree(s,x+1,y-1); //括号外也没有*或/,说明表达式被一个括号括住，去括号	u=cnt++;	lch[u]=build_tree(s,x,c1);	rch[u]=build_tree(s,c1+1,y);	op[u]=s[c1];	return u;}void display(int a){	for(int i=0;i<cnt;i++){		cout<<op[i]<<" ";	}}int length(char *s){	int i=0;	while(s[i]!='/0'){		i++;	}	return i;}int main(){	char s[maxn];	cin>>s;	//cout<<" "<<length(s);	display(build_tree(s,0,length(s)));	cout<<endl;	return 0;}