| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
同学们帮忙吧,WA,原因不明!!!(程序如下)//关键1:建立数组tree储存数链 。本题输入实际上是二叉树的顺序访问。tree[i]表示i+1层的数。
// 凡遇'(' 指针p加一,凡遇')'指针p减一,凡遇数则储存到*p中。
// 用sum计数,表示访问至当前位置数链之和。
//关键2:判断什么位置是leaf。观察发现,当且仅当出现 ")()"的时候为leaf。
//关键3:注意处理空树情况
#include <iostream>
#include <string.h>
using namespace std;
const int MAX=10000;
int tree[MAX];
char Ahead3[4];
//设置当前位置前面三个字符
inline void setAhead3(char chNow)
{
Ahead3[0]=Ahead3[1];
Ahead3[1]=Ahead3[2];
Ahead3[2]=chNow;
}
void main()
{
int num,
*p;
char chNow;
while(cin.eof()!=1)
{
//初始化
cin>>num;
p=tree;
Ahead3[0]=Ahead3[1]='*';
Ahead3[2]='(';
Ahead3[3]='\0';
int sum=0;
cin>>chNow;
//处理空树情况
cin>>chNow;
if(chNow==')') {
cout<<"no"<<endl;
continue;
}
while(1)
{
setAhead3(chNow);
if(chNow=='(')
p++;
else if(chNow=='-')
{
cin>>*p;
*p=0-*p;
sum+=*p;
}
else if(chNow>='0' && chNow<='9')
{
while(chNow>='0' && chNow<='9')
{
*p=(*p)*10+(chNow-'0');
cin>>chNow;
}
sum+=*p;
continue;
}
else if(chNow==')')
{
sum-=*p;
*p=0;
p--;
if( strcmp( Ahead3,")()" )==0 && sum==num)
{
//is leaf && sum==num
while(p>=tree)
{
cin>>chNow;
if(chNow==')')
{
*p=0;
p--;
}
if(chNow=='(')
p++;
}
cout<<"yes"<<endl;
break;
}
//p回到tree-1仍未break,说明答案为no
if(p==tree-1) {
cout<<"no"<<endl;
break;
}//end if
}//end of if(chNow==')')
cin>>chNow;
}//end of while(1)
}//end of while(cin.eof()!=1)
}//end of main
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator