摘要
Title: 4274. 后缀表达式
Tag: 后缀表达式
Memory Limit: 64 MB
Time Limit: 1000 ms

4274. 后缀表达式

题意

第一行包含整数 N，表示节点数量。节点编号 1∼N。
接下来 N 行，每行给出一个节点的信息（第 i 行对应第 i 个节点），格式为：
data left_child right_child
其中，data 是一个不超过 10 个字符的字符串，left_child 和 right_child 分别是该节点的左右子节点的编号。
没有子节点（即 NULL），则用 −1 表示。
思路

结论：表达式树的x序遍历等价于 x缀表达式

后缀表达式：
- 若是二元运算符，则正常后序遍历
- 注意负号，则为先序遍历 （特征：当一个节点为-，且左边没有儿子）

代码

/*
* @Author: NEFU AB-IN
* @Date: 2022-06-21 09:49:36
* @FilePath: \ACM\Acwing\4274\4274.cpp
* @LastEditTime: 2022-06-21 10:24:53
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define SZ(X) ((int)(X).size())
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(0);                                                                                                        \
    cout.tie(0);
#define DEBUG(X) cout << #X << ": " << X << endl;
typedef pair<int, int> PII;

const int INF = INT_MAX;
const int N = 1e6 + 10;

signed main()
{
    IOS;
    int n;
    cin >> n;

    vector<int> ls(n + 1), rs(n + 1);
    vector<string> e(n + 1);
    vector<int> deg(n + 1); // 入度

    for (int i = 1; i <= n; ++i)
    {
        string s;
        int l, r;
        cin >> s >> l >> r;
        if (l != -1)
            ls[i] = l, deg[l]++;
        if (r != -1)
            rs[i] = r, deg[r]++;
        e[i] = s;
    }
    int root = 1;
    for (int i = 1; i <= n; ++i)
    {
        if (!deg[i])
        {
            root = i;
            break;
        }
    }
    function<void(int)> dfs = [&](int u) {
        cout << "(";
        if (ls[u] && rs[u])
        {
            dfs(ls[u]);
            dfs(rs[u]);
            cout << e[u];
        }
        else if (!ls[u] && !rs[u])
        {
            cout << e[u];
        }
        else
        {
            cout << e[u];
            dfs(rs[u]);
        }

        cout << ")";
    };

    dfs(root);

    return 0;
}

4274. 后缀表达式

题意

思路

代码