AcWing 4274. 后缀表达式(模拟树 + 树的后序遍历)
原题链接
简单
C++ 代码
#include <iostream>
using namespace std;
struct treeNode{
string val;
int left;
int right;
};
const int N = 25;
int n;
treeNode g[N];
bool st[N];
string dfs(const int& u)
{
if (u != -1)
{
if ((g[u].val == "-" || g[u].val == "+") && g[u].left == -1)
return "(" + g[u].val + dfs(g[u].right) + ")";
string res = "(";
res += dfs(g[u].left) + dfs(g[u].right);
res += g[u].val + ")";
return res;
}
else return "";
}
int main()
{
cin >> n;
for (int i = 1; i <= n; ++ i)
{
cin >> g[i].val >> g[i].left >> g[i].right;
if (g[i].left != -1) st[g[i].left] = true;
if (g[i].right != -1) st[g[i].right] = true;
}
for (int i = 1; i <= n; ++ i)
{
if (!st[i])
{
cout << dfs(i);
break;
}
}
return 0;
}