欢迎访问我的Uva题解目录哦 https://blog.****.net/richenyunqi/article/details/81149109

题目描述

题意解析

你的任务是将多叉树转化为括号表示法。如图6-16所示，每个结点用除了“-”、“|”和空格
的其他字符表示，每个非叶结点的正下方总会有一个“|”字符，然后下方是一排“-”字符，恰好覆盖所有子结点的上方。单独的一行“#”为数据结束标记。

算法设计

直接在二维字符数组里递归即可，无须建树。注意对空树的处理，以及结点标号可以是
任意可打印字符。具体实现可见代码。

C++代码

#include<bits/stdc++.h>
using namespace std;
pair<int,int>find_range(int i,int j,vector<string>&tree){//查找连续-字符的首末位置
    int start=j,last=j;
    while(start>=0&&tree[i][start]=='-')
        --start;
    while(last<tree[i].size()&&tree[i][last]=='-')
        ++last;
    return {start+1,last-1};
}
void DFS(int i,int j,vector<string>&tree){//递归输出
    printf("%c(",tree[i][j]);
    if(i+1<tree.size()&&j<tree[i].size()&&tree[i+1][j]=='|'){
        pair<int,int>p=find_range(i+2,j,tree);
        for(int k=p.first;k<tree[i+3].size()&&k<=p.second;++k)
            if(tree[i+3][k]!=' '&&tree[i+3][k]!='#')
                DFS(i+3,k,tree);
    }
    printf(")");
}
int main(){
    int T;
    scanf("%d%*c",&T);
    while(T--){
        vector<string>tree;
        string line;
        while(getline(cin,line)&&line!="#")
            tree.push_back(line);
        printf("(");
        if(!tree.empty()){
            int i=tree[0].size()-1;
            DFS(0,i,tree);
        }
        puts(")");
    }
    return 0;
}