nyoj756 重建二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<stdio.h>  
#include<string.h>
typedef struct Tree{
char c;
Tree *lc,*rc;
}tree;
int len_mid;
tree *build(char ch)
{
tree *r=new tree;
r->c=ch;
r->lc=NULL;
r->rc=NULL;
return r;
}
char *find(char *s,char ch)
{
while(*s!=ch && *s!='\0')
s++;
return s;
}
void visit(tree *r)
{
if(r!=NULL)
{
printf("%c",r->c);
visit(r->lc);
visit(r->rc);
}
}
void creat(tree **root,char *last,char *mid ,int len)
{
if(len==0)
{
*root=NULL;
return ;
}
tree *r=build(last[len-1]);
*root=r;
char *p=find(mid,r->c);
int leftlen=strlen(mid)-strlen(p);
int rightlen=len-leftlen-1;
creat(&(r->lc),last,mid,leftlen);
creat(&(r->rc),last+leftlen,p+1,rightlen);
}
int main()
{
char last[30],mid[30];
while(~scanf("%s %s",last,mid))
{
tree *root=NULL;
len_mid=strlen(mid);
creat(&root,last,mid,len_mid);
visit(root);
printf("\n");

}
return 0;
}

我的这个太长了,再给你们看大神的代码。真是一个简洁呀。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<stdio.h>  
#include<string.h>
void ReBuild(char *pre, char *in,char *post, int len)
{
if(len>0)
{
int n =strchr(in,post[len-1])-in;
ReBuild(pre+1,in,post,n);
ReBuild(pre+n+1,in+n+1,post+n,len-n-1);
pre[0]=post[len-1];
}
}
int main()
{
char pre[30],in[30],post[30];
int len;
while(~scanf("%s%s",post,in))
{
len=strlen(post);
ReBuild(pre,in,post,len);
pre[len]=0;
puts(pre);
}
}

我的数据结构的课程设计

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include<stdio.h>  
#include<string.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
template <class T>
class mystack{//自定义栈,方便栈的输出
T sta[500];
int s_top;
public:
mystack(){
s_top=0;
}
void push(T n){
if(s_top>=499)
printf("栈满了,进栈失败!\n");
else
sta[++s_top]=n;
}
void pop(){
if(s_top==0)
{printf("栈为空,不能出栈。\n");exit(1);}
else
--s_top;
}
T top(){
return sta[s_top];
}
void clear(){
s_top=0;
}
bool empty(){
return s_top==0;
}
int size(){
return s_top;
}
void printstack(){
int i;
for(i=1;i<=s_top;i++)
cout<<sta[i]<<" ";
printf(" 大小是:%d\n",s_top);
}
};

mystack<double> ovs;//运算数栈
mystack<char> ops;//操作符栈
char s[1005];
int comp(char);
double calculate(double ,char ,double);
int main()
{
int N;
int i,j;
double num1,num2;
char op;
char w[100];
while(printf("请输入算式(输入\"exit\"退出):"),~scanf("%s",s),strcmp(s,"exit"))
{
ops.push('#');
for(i=0;s[i]!='=';)
{
printf("当前处理:");
if(s[i]>='0' && s[i]<='9')//处理数字
{
j=0;
w[j++]=s[i++];
while((s[i]>='0' && s[i]<='9') || s[i]=='.')
{
w[j++]=s[i++];
}
w[j]='\0';
printf("%s\n",w);
ovs.push(atof(w));
}
else//运算符
{

if(comp(ops.top())<comp(s[i]) || s[i]=='(')
{
printf("%c\n",s[i]);
ops.push(s[i]);
i++;
}
else if(ops.top()=='(' && s[i]==')')
{
printf("%c\n",s[i]);
ops.pop();
i++;
}
else
{
num2=ovs.top(); ovs.pop();
num1=ovs.top(); ovs.pop();
op=ops.top(); ops.pop();
//printf("%lf%c%lf\n",num1,op,num2);

cout<<num1<<" "<<op<<" "<<num2<<endl;
ovs.push(calculate(num1,op,num2));
}
}
printf("运算符当前栈为:");
ops.printstack();
printf("操作数当前栈为:");
ovs.printstack();
printf("\n");

}
while(ovs.size()!=1)//最后只剩下同级运算
{
printf("当前处理:");
num2=ovs.top(); ovs.pop();
num1=ovs.top(); ovs.pop();
op=ops.top(); ops.pop();
printf("%lf%c%lf\n",num1,op,num2);
ovs.push(calculate(num1,op,num2));
}
printf("\n\n运算结果:%s%.2lf\n",s,ovs.top());
ovs.clear();//清空
ops.clear();//清空
}
return 0;

}
int comp(char op)
{
int t;
switch(op)
{
case '*':
case '/':t=3;break;
case '+':
case '-':t=2;break;
case '(':
case ')':t=1;break;
case '#':t=0;break;
default :printf("%c_error!\n",op);exit(1);
}
return t;
}
double calculate(double num1,char op,double num2)
{
double ans;
switch(op)
{
case '*':ans=num1*num2;break;
case '/':ans=num1/num2;break;
case '+':ans=num1+num2;break;
case '-':ans=num1-num2;break;
default :printf("%c_error!\n",op);exit(1);
}
return ans;
}

运行结果:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
请输入算式(输入"exit"结束):1+2*3/(3+5)-3=
当前处理:1
运算符当前栈为:# 大小是:1
操作数当前栈为:1 大小是:1


当前处理:+
运算符当前栈为:# + 大小是:2
操作数当前栈为:1 大小是:1


当前处理:2
运算符当前栈为:# + 大小是:2
操作数当前栈为:1 2 大小是:2


当前处理:*
运算符当前栈为:# + * 大小是:3
操作数当前栈为:1 2 大小是:2


当前处理:3
运算符当前栈为:# + * 大小是:3
操作数当前栈为:1 2 3 大小是:3


当前处理:2.000000*3.000000
运算符当前栈为:# + 大小是:2
操作数当前栈为:1 6 大小是:2


当前处理:/
运算符当前栈为:# + / 大小是:3
操作数当前栈为:1 6 大小是:2


当前处理:(
运算符当前栈为:# + / ( 大小是:4
操作数当前栈为:1 6 大小是:2


当前处理:3
运算符当前栈为:# + / ( 大小是:4
操作数当前栈为:1 6 3 大小是:3


当前处理:+
运算符当前栈为:# + / ( + 大小是:5
操作数当前栈为:1 6 3 大小是:3


当前处理:5
运算符当前栈为:# + / ( + 大小是:5
操作数当前栈为:1 6 3 5 大小是:4


当前处理:3.000000+5.000000
运算符当前栈为:# + / ( 大小是:4
操作数当前栈为:1 6 8 大小是:3


当前处理:)
运算符当前栈为:# + / 大小是:3
操作数当前栈为:1 6 8 大小是:3


当前处理:6.000000/8.000000
运算符当前栈为:# + 大小是:2
操作数当前栈为:1 0.75 大小是:2


当前处理:1.000000+0.750000
运算符当前栈为:# 大小是:1
操作数当前栈为:1.75 大小是:1


当前处理:-
运算符当前栈为:# - 大小是:2
操作数当前栈为:1.75 大小是:1


当前处理:3
运算符当前栈为:# - 大小是:2
操作数当前栈为:1.75 3 大小是:2


当前处理:1.750000-3.000000




运算结果:1+2*3/(3+5)-3=-1.25
请输入算式(输入"exit"结束):exit
Press any key to continue

nyoj89 汉诺塔(二)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<stdio.h>  
long long f(int *p,int i,int final){
if(i==0) return 0;
else if(p[i]==final) return f(p,i-1,final);
else return f(p,i-1,6-p[i]-final)+(1LL<<(i-1));
}
int n,start[35],finish[35];//开始所在的柱子和最最终所在的柱子
int main()
{
int T;
int i,n;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(i=1;i<=n;i++)
{
finish[i]=3;
scanf("%d",&start[i]);
}
int k=n;
long long ans=0;
while(k>=1 && start[k]==finish[k]) k--;
if(k>=1)
{
int t=6-start[k]-finish[k];
ans=f(start,k-1,t)+f(finish,k-1,t)+1;
}
printf("%lld\n",ans);
}
return 0;

}

要想解决这道题,我们先来分析一下。
开始,找出最大的盘子(也就是编号最大),设为k。那么k必须移动。
那么在移动k之前,假设k要从1移动到2,由于比k大的不需要移动,所以可以看做不存在,编号比k小的既不能在在1,也不能在2上,换句话说这时候1上只有k盘子,由于最后还需要移动k盘子,换句话说我们写一个函数f(p,i, finl),盘子的初始柱子编号数组是p,如果这样则这题的答案就是f(start, k-1, 6-start[k]-finsh[k], )+ f(finish, k-1, 6-start[k]-finsh[k]) +1(仔细理解下),注意最后一个步骤是吧i-1个盘子整体从一个柱子移动到另一个柱子,这个需要2^(i-1)-1步。加上那个多出来的一步。所以就是2^i-1步。
于是便有了这个函数f:

1
2
3
4
5
long long f(int *p,int i,int final){  
if(i==0) return 0;
else if(p[i]==final) return f(p,i-1,final);
else return f(p,i-1,6-p[i]-final)+(1LL<<(i-1));//移位运算符算2的多少次方比较快,由于总数很大,需要用long long 保存。
}

——————参考自《算法竞赛入门经典》

nyoj267 中缀式变后缀式(二叉树)(下)

这个题我前几天只是做了表达式变换部分,今天把求值部分加进去了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include<stdio.h>  
#include<string.h>
#include<stdlib.h>
#include<stack>
using namespace std;
typedef struct Tree
{
char c;//如果不是叶节点,则是操作符,用字符存
char ss[25];//由于要输出原来的输入,这里保存着
double n;//字符串转换后的值
Tree *liftchild,*rightchild;
}tree;
stack <tree*> ops;
stack <tree*> ovs;
tree *Root;
char s[1005];
int p(char ch)
{
switch(ch)
{
case '*':
case '/':return 2;
case '+':
case '-':return 1;
case '(':
case ')':return 0;
case ';':return -1;
default :printf("%c_error!\n",ch);exit(1);
}
}
tree *_build(char *s)
{
tree *root=new tree;
strcpy(root->ss,s);
root->liftchild=NULL;
root->rightchild=NULL;
return root;
}
tree *build(char ch)
{
tree *root=new tree;
root->c=ch;
root->liftchild=NULL;
root->rightchild=NULL;
return root;
}
double calcu(double n1,char op,double n2)
{
switch(op)
{
case '*':return n1*n2;
case '/':return n1/n2;
case '+':return n1+n2;
case '-':return n1-n2;
default :printf("%c_error!",op);return 0;
}
}
void visit(tree * r)
{
if(r!=NULL)
{
visit(r->liftchild);
visit(r->rightchild);
if(r->liftchild==NULL && r->rightchild==NULL)
{ printf("%s",r->ss); r->n=atof(r->ss);}//叶节点必定是数字
else
{ printf("%c",r->c); r->n=calcu(r->liftchild->n,r->c,r->rightchild->n);}//遍历的时候计算。
}
}


int main()
{

int i,j;
int N;
scanf("%d",&N);
char w[100];
while(N--)
{
scanf("%s",s);//1-2*3-4/5=
for(i=0;s[i]!='=';)
{
if(s[i]>='0' && s[i]<='9')
{
j=0;
while((s[i]>='0' && s[i]<='9') || s[i]=='.')
{
w[j++]=s[i++];
}
w[j]='\0';
//printf("[%lf]",atof(w));
ovs.push(_build(w));
}
else
{
if(ops.empty() || s[i]=='(' || p(ops.top()->c)<p(s[i]) )
ops.push(build(s[i])),i++;
else if(ops.top()->c=='(' && s[i]==')')
ops.pop(),i++;
else//p(ops.top())>=p(s[i])
{
ops.top()->rightchild=ovs.top();ovs.pop();
ops.top()->liftchild=ovs.top();ovs.pop();
Root=ops.top();ops.pop();
ovs.push(Root);
}
}

}
while(ovs.size()!=1)
{
ops.top()->rightchild=ovs.top();ovs.pop();
ops.top()->liftchild=ovs.top();ovs.pop();
Root=ops.top();ops.pop();
ovs.push(Root);
}
Root=ovs.top();ovs.pop();
while(!ops.empty())
ops.pop();
visit(Root);
printf("=\n%.2lf\n\n",Root->n);
}
return 0;
}

我觉得不是很难,只要表达式求值你会了,这题也是小意思。

nyoj267 中缀式变后缀式(二叉树)(上)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include<stdio.h>  
#include<stdlib.h>
#include<stack>
using namespace std;
typedef struct Tree
{
char c;
char ss[50];
Tree *liftchild,*rightchild;
}tree;
stack <tree*> ops;
stack <tree*> ovs;
tree *Root;
char s[1005];
int p(char ch)
{
switch(ch)
{
case '*':
case '/':return 2;
case '+':
case '-':return 1;
case '(':
case ')':return 0;
case ';':return -1;
default :printf("%c_error!\n",ch);exit(1);
}
}
tree *_build(char *s)
{
tree *root=new tree;
strcpy(root->ss,s);
root->liftchild=NULL;
root->rightchild=NULL;
return root;
}
tree *build(char ch)
{
tree *root=new tree;
root->c=ch;
root->liftchild=NULL;
root->rightchild=NULL;
return root;
}
void visit(tree * r)
{
if(r!=NULL)
{
visit(r->liftchild);
visit(r->rightchild);
if(r->liftchild==NULL && r->rightchild==NULL)
printf("%s",r->ss);
else
printf("%c",r->c);
}
}
int main()
{

int i,j;
int N;
scanf("%d",&N);
char w[100];
while(N--)//1-2*3-4/5
{
scanf("%s",s);
for(i=0;s[i]!='=';)
{
if(s[i]>='0' && s[i]<='9')
{
j=0;
while((s[i]>='0' && s[i]<='9') || s[i]=='.')
{
w[j++]=s[i++];
}
w[j]='\0';
//printf("[%lf]",atof(w));
ovs.push(_build(w));
}
else
{
if(ops.empty() || s[i]=='(' || p(ops.top()->c)<p(s[i]) )
ops.push(build(s[i])),i++;
else if(ops.top()->c=='(' && s[i]==')')
ops.pop(),i++;
else//p(ops.top())>=p(s[i])
{
ops.top()->rightchild=ovs.top();ovs.pop();
ops.top()->liftchild=ovs.top();ovs.pop();
Root=ops.top();ops.pop();
ovs.push(Root);
}
}

}
while(ovs.size()!=1)
{
ops.top()->rightchild=ovs.top();ovs.pop();
ops.top()->liftchild=ovs.top();ovs.pop();
Root=ops.top();ops.pop();
ovs.push(Root);
}
Root=ovs.top();ovs.pop();
while(!ops.empty())
ops.pop();
visit(Root);
printf("=\n");
}
return 0;
}

这本来是南阳理工oj的第267题,我只是完成了表达式的转换部分。
下面的这个是个位数操作数的中缀变后缀,是栈和队列写的。其实和上面的差不多,但是上面的二叉树建立了之后可以先序遍历中序遍历后序遍历变成各种形式的式子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<stdio.h>//栈和队列  
#include<stdlib.h>
#include<queue>
#include<stack>
using namespace std;
stack <char> ops;
queue <char> ovs;
int p(char);
int main()
{
char s[10005];
int i,k;
int N;
scanf("%d",&N);
while(N--)// 1+2*(3-4)/5=
{
scanf("%s",s);
ops.push('=');
for(i=0;;)
{
if(s[i]>='0' && s[i]<='9')
{
ovs.push(s[i]);i++;
}
else
{
if(s[i]=='\0')
{
while(!ops.empty())
{
ovs.push(ops.top());
ops.pop();
}
break;
}
else if(s[i]==')')
{
while(ops.top()!='(')
{
ovs.push(ops.top());ops.pop();
}
ops.pop();
i++;
}
else if(s[i]=='(' || p(s[i]) > p(ops.top()))
{
ops.push(s[i]);i++;
}
else //(s[i]!='=' && p(s[i])<= p(ops.top()) )
{
ovs.push(ops.top());
ops.pop();
}
}
}
while(ovs.size()!=1)
printf("%c",ovs.front()),ovs.pop();
printf("\n");
ovs.pop();
while(!ops.empty())
ops.pop();

}
return 0;

}
int p(char c)
{
switch(c)
{
case '*':
case '/':return 2;
case '+':
case '-':return 1;
case '(':
case ')':
case '=':return 0;
default :printf("%c_error!",c);exit(1);
}
}

有待完善。