BFS+数据处理 Under the Trees UVa

题意：将多叉树转化为括号表示法，每个非叶结点的正下方都有一个'|'然后下方是一排'-'和字符，恰好覆盖所有子结点的正上方，单独的一行‘#’为数据的结束标志

解题思路：用gets将字符数组输入，本题不用建树，直接用广度优先递归求解，同时注意对空树的处理(需要单独判断)，以及结点的符号不一定是字母，也可以是其他的符号(用isspace()判断是不是空格，并且单独判断是不是换行符'')

笔记：gets是从标准的输入接收一行字符，遇到' '时结束，但不接收' '，把 ' '留存输入缓冲区；把接收的一串字符存储在形式参数指针指向的空间，并在最后自动添加一个''(因为不知道堆栈的大小，所以不安全)。fgets是从文件或标准输入接收一串字符，遇到' '时结束，把' '也作为一个字符接收；把接收的一串字符存储在形式参数指针指向的空间，并在' '后再自动添加一个''。

代码：

 1 #include<stdio.h>
 2 #include<cctype>
 3 #include<string.h>
 4 #include<iostream>
 5 using namespace std;
 6 const int maxn=210;
 7 int m;
 8 int n;
 9 char str[maxn][maxn];
10 
11 void dfs(int r,int c){　　　　　　　　　　　　//广度优先搜索遍历字符串
12     printf("%c(",str[r][c]);
13     if(r+1<m&&str[r+1][c]=='|'){
14         int t=-1;
15         for(int i=c;i>=0;i--){
16             if(str[r+2][i]=='-')    t=i;
17             else break;
18         }
19         if(t>=0){
20             for(int i=t;;i++){
21                 if(str[r+2][i]=='-'&&str[r+3][i]!=''){
22                     if(!isspace(str[r+3][i]))　　　　　　//判断是否为空格，头文件<cctype>
23                         dfs(r+3,i);
24                 }
25                 else break;
26             }
27         }
28     }
29     printf(")");
30 }
31 
32 int main(){
33     freopen("in.txt","r",stdin);
34     scanf("%d",&n);
35     getchar();
36     while(n--){
37         memset(str,'',sizeof(str));
38        m=0;
39        while(1){
40             gets(str[m]);
41             if(str[m][0]=='#')  break;
42             m++;
43        }
44        printf("(");
45        if(m){　　　　　　　　　　　　　　　　　　　　　　　　//单独判断是否为空树
46             int len=strlen(str[0]);
47             for(int i=0;i<len;i++){
48                 if(!isspace(str[0][i])){
49                     dfs(0,i);
50                     break;
51                 }
52             }
53         }
54     printf(")
");
55 
56     }
57     return 0;
58 }