后缀表达式每个结点只有三种情况
- 左右孩子都有
$(+dfs(lchild)+dfs(rchild)+data+)$
先左孩子在右孩子再加上自己的符号
- 只有右孩子
$(+data+dfs(rchild)+)$
先加上自己的符号在加上右孩子
一般来说只有正负号会出现这种情况
- 一个孩子都没有
$(+data+)$
只用返回自己就行
需要一个额外数组来表示某个结点是不是别人的孩子
用来找到根节点
#include<iostream>
#include<cstring>
using namespace std;
const int N=25;
int n;
string s[N];
int l[N],r[N];
int f[N];//f[i] 表示i是否是其他结点的孩子
string dfs(int k){
//不会出现只有左孩子没有右孩子的情况
if(~l[k])return "("+dfs(l[k])+dfs(r[k])+s[k]+")";//有左孩子一定就有右孩子
if(~r[k])return "("+s[k]+dfs(r[k])+")";//只有右孩子
return "("+s[k]+")";//一个孩子都没有
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>s[i]>>l[i]>>r[i];
if(l[i])f[l[i]]=true;
if(r[i])f[r[i]]=true;
}
int root=0;//找到根节点 根节点一定不是某个结点的儿子
for(int i=1;i<=n;i++)
if(!f[i]){
root=i;
break;
}
cout<<dfs(root);
return 0;
}