转载自：http://www.cnblogs.com/nanke/archive/2011/09/19.html
题意：
去掉题目背景，给你一个串，转化为一棵树，输出先序遍历节点的顺序；
分析：
整个串由节点名字，'('、')'、',' 组成，遇到一个括号时，当前左括号是当前括号内节点的父节点，括号内用','隔开的是兄弟节点，整体就是一颗树；
若要将该串转化为树，再进行一次DFS的话，我想应该会超时吧。所以第一感觉就是用栈模拟整个串来遍历该树，用队列来保存遍历节点的顺序，用数组应该会更快吧，不过不知道大概会有多大，所以就偷一下懒，直接用队列了。
队列是用来保存遍历节点的顺序的，而栈保存的是当前遍历到的节点的父节点
模拟的过程：
1）：模拟过程一遍给节点名字编号；
2）：当遇到 '(' 时，表示当前节点有子节点，所以把当前节点同时压入栈，和队列；
3）：当遇到 ')' 时，表示当前父节点的所以子节点已经遍历完，所以将当前节点压入队列，当时要再次访问父节点，所以将当前父节点也压入队列，而且，要弹出栈；当然，这时还要考虑一个问题：就是 ')'前面是否也为一个 ')'，若是，则不需要将当前节点压入队列，因为已经压入过了；
4）：当遇到 ',' 时，表示遍历到了一个叶节点，将当前节点压入队列，当时要再次访问父节点；同上，此时还要考虑一个问题，就是','前面是否为一个‘）’，若是，则不需要将当前节点压入队列，同样，也是因为压入过了；
#include<iostream> |
#include<string> |
#include<stack> |
#include<queue> |
using namespace std; |
stack<int> fstack; |
queue<int> Q; |
char s[1000010]; |
struct name |
{ |
char str[11]; |
}na[50001]; |
int main() |
{ |
int cas,n,num; |
char str1[11]; |
scanf("%d",&cas); |
while(cas--) |
{ |
while(!fstack.empty()) |
fstack.pop(); |
while(!Q.empty()) |
Q.pop(); |
scanf("%s",s); |
int len=strlen(s); |
num=0; |
int j=0; |
for(int i=0;i<len;i++) |
{ |
if(s[i]>='a'&&s[i]<='z') |
str1[j++]=s[i]; |
else |
{ |
if(j!=0) |
{ |
str1[j]='\0'; |
j=0; |
strcpy(na[++num].str,str1); |
} |
if(s[i]=='(') |
{ |
fstack.push(num); |
Q.push(num); |
} |
else if(s[i]==',') |
{ |
|
if(s[i-1]!=')') |
Q.push(num); |
Q.push(fstack.top()); |
} |
else { |
if(s[i-1]!=')') |
Q.push(num); |
Q.push(fstack.top()); |
fstack.pop(); |
} |
} |
} |
if(num==0) |
{ |
str1[j]='\0'; |
printf("1\n%s\n\n",str1); |
continue; |
} |
printf("%d\n",num); |
for(int i=1;i<=num;i++) |
printf("%s\n",na[i].str); |
while(!Q.empty()) |
{ |
if(Q.front()==1&&Q.size()==1)//所有子节点已经遍历，只剩根节点 |
break; |
printf("%d ",Q.front()); |
Q.pop(); |
printf("%d\n",Q.front()); |
} |
puts(""); |
} |
return 0; |
} |