AcWing 1623. 中缀表达式
原题链接
简单
作者:
嘉_8
,
2023-12-01 15:45:12
,
所有人可见
,
阅读 47
C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef pair<string, bool> PSL;
const int N = 50;
int l[N], r[N];
string e[N];
bool st[N]; // 用于查找根节点
int n;
// 将子结果进行包装
string getS(const PSL & psl) {
string s = psl.first;
if(psl.second) s = "(" + s + ")";
return s;
}
// 返回的第二个值用于告诉调用者。“我”需不需要被括号包装
// 观察题目可知:如果子节点是个树就需要被包装
pair<string, bool> dfs(int u) {
if(u == -1) return {"", false};
string res = getS(dfs(l[u])) + e[u] + getS(dfs(r[u]));
return {res, l[u] != -1 || r[u] != -1};
}
int main() {
cin >> n;
for(int i = 1;i <= n;i ++) {
string s;
int a, b;
cin >> s >> a >> b;
l[i] = a, r[i] = b, e[i] = s;
st[a] = st[b] = true;
}
int root;
for(int i = 1;i <= n;i ++)
if(!st[i]) {
root = i;
break;
}
cout << dfs(root).first;
return 0;
}