Powered by:NEFU AB-IN

Link

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;
  }