当前位置:网站首页>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;}
边栏推荐
猜你喜欢
随机推荐
什么是Nacos?
PAT tree DP (memory search) class a, 1079, 1090, 1106
2022-7-15 第五组 瞒春 学习笔记
PAT Class A 1145 Hash - Average Lookup Time
第五章-5.2-指示器随机变量
2022-07-13 第五小组 瞒春 学习笔记
2022-07-28 第六小组 瞒春 学习笔记
this beta version of Typora is expired, please download and install a newer version.Typora的保姆级最新解决方法
codeforces Linova and Kingdom
Redis的5中数据类型总结
DOM - page rendering process
(数学基础)第三章-3.2-标准记号和常用函数
为什么四个字节的float表示的范围比八个字节的long表示的范围要广
只出现一次的数字||| —— 哈希映射、异或位运算+分治思想
解决(An error happened during template parsing (template: “class path resource [templates/...]
Redis6
延时函数-定时器
【JS执行机制】
【 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
2022-07-10 第五小组 瞒春 学习笔记