当前位置:网站首页>PAT Class A 1130 Infix Expressions
PAT Class A 1130 Infix Expressions
2022-08-02 17:06:00 【keyboard sonata】
Given a syntactic binary tree, please output the corresponding infix expression, and use parentheses to reflect the precedence of operators.
Input format
The first line contains the integer N representing the number of summary points of the binary tree.Next N lines, each giving information about a node in the following format (line i corresponds to node i):
data left_child right_child
where data is a string with a length not exceeding 10, left_child and right_child are the left and right child node numbers of the node respectively.All nodes are numbered from 1 to N, NULL is represented by -1.
The following two figures correspond to Example 1 and Example 2, respectively.
11.JPG 222.JPG
Output format
Please output the infix expression on one line, and use parentheses to reflect the operator's precedence.Please note that there should be no extra parentheses and no spaces between any symbols.
Data Range
1≤N≤20
Input Example 1:
8
* 8 7
a -1 -1
* 4 1
+ 2 5
b -1 -1
d -1 -1
- -1 6
c -1 -1
Example output 1:
(a+b)*(c*(-d))
Example input 2:
8
2.35 -1 -1
* 6 1
- -1 4
% 7 8
+ 2 3
a -1 -1
str -1 -1
871-1 -1
Sample output 2:
(a*2.35)+(-(str%871))
Solution 1:
#include using namespace std;const int N = 30;string a[N];int n, l[N], r[N], f[N];int root;void dfs(int u){if(u > n) return;if(u == -1) return;if(!((l[u] == -1 && r[u] == -1) || u == root)) cout << '(';dfs(l[u]);cout << a[u];dfs(r[u]);if(!((l[u] == -1 && r[u] == -1) || u == root)) cout << ')';}int main(){cin >> n;memset(l, -1, sizeof l);memset(r, -1, sizeof r);memset(f, -1, sizeof f);for(int i = 1; i <= n; i ++ ){cin >> a[i];cin >> l[i] >> r[i];if(l[i] != -1) f[l[i]] = i;if(r[i] != -1) f[r[i]] = i;}root = 1;while(f[root] != -1) root = f[root];dfs(root);return 0;}
Solution 2:
#include using namespace std;const int N = 30;string a[N];int n, l[N], r[N], f[N];bool is_leaf[N];int root;string dfs(int u){string left, right;if(l[u] != -1){left = dfs(l[u]);if(!is_leaf[l[u]]) left = "(" + left + ")";}if(r[u] != -1){right = dfs(r[u]);if(!is_leaf[r[u]]) right = "(" + right + ")";}return left + a[u] + right;}int main(){cin >> n;memset(l, -1, sizeof l);memset(r, -1, sizeof r);memset(f, -1, sizeof f);for(int i = 1; i <= n; i ++ ){cin >> a[i];cin >> l[i] >> r[i];if(l[i] != -1) f[l[i]] = i;if(r[i] != -1) f[r[i]] = i;if(l[i] == -1 && r[i] == -1) is_leaf[i] = true;}root = 1;while(f[root] != -1) root = f[root];cout << dfs(root);return 0;}
边栏推荐
- JSP技术
- vite.config.ts 引入 `path` 模块注意点!
- 李开复花上千万投的缝纫机器人,团队出自大疆
- lammps学习(二)联合原子模型聚乙烯拉伸
- 2022-07-27 第六小组 瞒春 学习笔记
- 《数字经济全景白皮书》银行业智能风控科技应用专题分析 发布
- Typora永久使用,彻底解决This beta version of Typora is expired.
- PAT tree DP (memory search) class a, 1079, 1090, 1106
- vite.config.ts introduces the `path` module Note!
- IPtables 和binlog
猜你喜欢
this beta version of Typora is expired, please download and install a newer version.Typora的保姆级最新解决方法
【Leetcode字符串--字符串变换/进制的转换】HJ1.字符串最后一个单词的长度 HJ2.计算某字符出现次数 HJ30.字符串合并处理
马甲包接入过程记录
第六章-6.1-堆-6.2-维护堆的性质-6.3-建堆
Servlet基础详解
告别手摇织布机的AI时代
XGBoost 和随机森林在表格数据上优于深度学习?
2022年低压电工考试试题及在线模拟考试
How to check the WeChat applet server domain name and modify it
容器中的Cgroup
随机推荐
5000mAh大电池!华为全新鸿蒙手机今晚亮相:更流畅更安全
lammps学习(一)单晶硅纳米磨削
“绿色低碳+数字孪生“双轮驱动,解码油气管道站升级难点 | 图扑软件
2022-07-28 第六小组 瞒春 学习笔记
2022-07-16 第五小组 瞒春 学习笔记
【QMT】给QMT量化交易软件安装和调用第三方库(举例通达信pytdx,MyTT,含代码)
散列表简述
【 Leetcode string, the string transform/hexadecimal conversion 】 HJ1. The length of the string last word HJ2. Calculation of a certain number of characters appear HJ30. String merging processing
单例模式(singleton pattern)
PAT Class A 1078 Hash
JS本地存储(附实例)
页面返回顶部和固定导航栏js基础案例
XML技术
【Untitled】
2022-07-26 第六小组 瞒春 学习笔记
第五章-5.2-指示器随机变量
状态码以及访问百度过程
使用 docker 搭建 redis-cluster 集群
DOM - page rendering process
Typora永久使用,彻底解决This beta version of Typora is expired.