4274 后缀表达式 PAT 1162
作者:
NikoNairre
,
2023-11-28 17:11:28
,
所有人可见
,
阅读 78
#include <iostream>
using namespace std;
const int N = 30;
string val[N];
int l_tr[N], r_tr[N]; //left and right collide with std::left, std::right, avoid use
bool has_father[N];
int n;
int find_root() //find the tree root, it don't have father node
{
int root = 0;
for (int i = 1; i <= n; i++ ) {
if (!has_father[i]) root = i;
}
return root;
}
void dfs(int root)
{
if (root == -1) return;
cout << "("; //according to the question, each step must have brackets, begin with one, and end with another
if (l_tr[root] != -1 and r_tr[root] != -1) {
dfs(l_tr[root]); //normally do postorder recursion
dfs(r_tr[root]);
cout << val[root]; //visit root val
}
else if (l_tr[root] == -1 and r_tr[root] == -1) { //reach a leave node
cout << val[root]; //cout node
}
else if (l_tr[root] == -1 and r_tr[root] != -1) { //the condition a node '-' only has right child
cout << val[root]; //int this condition, visit root first and dfs later
dfs(r_tr[root]);
}
cout << ")";
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++ ) {
string v; int l, r;
cin >> v >> l >> r;
val[i] = v;
l_tr[i] = l, r_tr[i] = r;
if (l != -1) has_father[l] = true;
if (r != -1) has_father[r] = true;
}
int root = find_root();
dfs(root);
return 0;
}