PAT甲级【2019年9月考题】——A1163 PostfixExpression【25】
7-3 Postfix Expression (25 分)
Given a syntax tree (binary), you are supposed to output the corresponding postfix expression, with parentheses reflecting the precedences of the operators.
Input Specification
Each input file contains one test case. For each case, the first line gives a positive integer N(≤20) N(≤20) which is the total number of nodes in the syntax tree. Then N lines follow, each gives the information of a node (the i-th line corresponds to the i-th node) in the format:
data left_child right_child
where data
is a string of no more than 10 characters, left_child
and right_child
are the indices of this node's left and right children, respectively. The nodes are indexed from 1 to N. The NULL link is represented by −1. The figures 1 and 2 correspond to the samples 1 and 2, respectively.
Output Specification
For each case, print in a line the postfix expression, with parentheses reflecting the precedences of the operators.There must be no space between any symbols.
Sample Input 1
8
* 8 7
a -1 -1
* 4 1
+ 2 5
b -1 -1
d -1 -1
- -1 6
c -1 -1
Sample Output 1
(((a)(b)+)((c)(-(d))*)*)
Sample 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)%))+)
【声明】
由于此题还未上PAT官网题库,故没有测试集,仅仅是通过了样例,若发现错误,感谢留言指正。
Solution:
这道题与A1130 Infix Expression如出一辙,只不过换了一下位置。
开始我重建了二叉树,后发现根本不用,因为给出的信息就是一个树的形状
使用DFS遍历,先左,再右,后节点,
唯一注意的就是缺少左孩子节点的情况【不可能只会出现缺少右孩子节点的情况,不然就不是等式】
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int n, head = -;
struct Node
{
string val;
int l, r;
}nodes[];
string DFS(int root)
{
if (root == -) return "";
if (nodes[root].l == -)//记住,只允许左子树为空,不能右子树为空,不然就不是个算式
return "(" + nodes[root].val + DFS(nodes[root].r) + ")";
else
return "(" + DFS(nodes[root].l) + DFS(nodes[root].r) + nodes[root].val + ")";
}
int main()
{
cin >> n;
vector<bool>isHead(n + , true);//找到头节点
for (int i = ; i <= n; ++i)
{
string a;
int b, c;
cin >> a >> b >> c;
nodes[i] = { a,b,c };
isHead[(b == - ? : b)] = isHead[(c == - ? : c)] = false;
}
for (int i = ; i <= n && head == -; ++i)//找到头节点
if (isHead[i])head = i;
string res = DFS(head);
cout << res;
return ;
}
最新文章
- 在android开发中使用multdex的方法-IT蓝豹为你整理
- js中的一些容易混淆的方法!
- Dispose() C# 优化内存
- 20160205 - Windows 10 家庭版没有组策略
- C++可能出错的小细节
- Spring-RMI固定端口
- 在Linux用libcurl.a在链接的时候出错
- C++的虚函数表
- INTERESTING AND OBSCURE INHERITANCE ISSUES WITH CPP
- UVA 10523 Very Easy!!!(大数据加法、乘法)
- 如何解决MySQLAdministrator 启动报错
- POJ2486 - Apple Tree(树形DP)
- tableview刷新某个区域(section)或者某一行(row)
- chapter1-开始(1)
- 用 javascript 判断 IE 版本号
- [google面试CTCI] 1-5.替换字符串中特定字符
- python进程池multiprocessing.Pool和线程池multiprocessing.dummy.Pool实例
- CentOS 7编译OpenWRT
- mybatis级联
- 线程中使用SaveFileDialog不能弹出窗体