PAT甲级2019秋季7-3 A1163 PostfixExpression (25分)

r囧r小猫 2023-02-23 10:55 5阅读 0赞

[算法笔记总目录][Link 1]  
[关键英语单词解释][Link 2]  
**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官网题库，故没有测试集，仅仅是通过了样例，若发现错误，感谢留言指正。  
**题意**  
给出一棵语法树，求它的后序表达式。  
**思路**  
按照题中给出树的方式，用静态节点更好处理，但是不知道根节点是谁，所以在节点中加入父节点的信息，读入结束后从任意一个节点开始向上就能确定根节点。求后序表达式和后序遍历差不多，但是要注意但目运算符的存在，也就是如果子节点只有一个，那么此时应该先输出运算符。

**代码一**

#include<bits/stdc++.h> //万能头文件，说明见算法笔记总目录
    using namespace std;
    struct Node{ 
    	string s;
    	int lchild,rchild,parent=-1;
    }node[30]; 
    string dfs(int root){ 
        if (root == -1)	return "";
    	if (node[root].lchild == -1)
    		return "(" + node[root].s + dfs(node[root].rchild) + ")";
    	else
    		return "(" + dfs(node[root].lchild) + dfs(node[root].rchild) + node[root].s + ")";
    } 
    int main(){ 
    	int n,root=0;
    	scanf("%d",&n);
    	for(int i=1;i<=n;i++){ 
    		cin>>node[i].s>>node[i].lchild>>node[i].rchild;
    		if(node[i].lchild>0)node[node[i].lchild].parent=i;
    		if(node[i].rchild>0)node[node[i].rchild].parent=i;
    	}
    	for(int i=1;i<=n;i++){ 
    		if(node[i].parent == -1) root = i;
    	}
    	cout<<dfs(root);
    	return 0;
    }

**代码二**

#include<bits/stdc++.h>
    using namespace std;
    struct Node{ 
    	string s;
    	int lchild,rchild,parent=-1;
    }node[30]; 
    void dfs(int root){ 
    	if(root == -1) return;
    	printf("(");
    	if(node[root].lchild>0 && node[root].rchild>0){ 
    	 dfs(node[root].lchild);
    	 dfs(node[root].rchild);
    	 cout<<node[root].s;
    	}else{ 
    	 cout<<node[root].s;	
    	 dfs(node[root].lchild);
    	 dfs(node[root].rchild);
    	}
    	printf(")");
    } 
    int main(){ 
    	int n,root=0;
    	scanf("%d",&n);
    	for(int i=1;i<=n;i++){ 
    		cin>>node[i].s>>node[i].lchild>>node[i].rchild;
    		if(node[i].lchild>0)node[node[i].lchild].parent=i;
    		if(node[i].rchild>0)node[node[i].rchild].parent=i;
    	}
    	for(int i=1;i<=n;i++){ 
    		if(node[i].parent == -1) root = i;
    	}
    	dfs(root);
    	return 0;
    }

**代码三（来源于网络）**

#include <iostream>
    #include <vector>
    #include <string>
    using namespace std;
    int n, head = -1;
    struct Node
    { 
    	string val;
    	int l, r;
    }nodes[25];
    string DFS(int root)
    { 
    	if (root == -1)	return "";
    	if (nodes[root].l == -1)//记住，只允许左子树为空，不能右子树为空，不然就不是个算式
    		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 + 1, true);//找到头节点
    	for (int i = 1; i <= n; ++i)
    	{ 
    		string a;
    		int b, c;
    		cin >> a >> b >> c;
    		nodes[i] = {  a,b,c };
    		isHead[(b == -1 ? 0 : b)] = isHead[(c == -1 ? 0 : c)] = false;
    	}
    	for (int i = 1; i <= n && head == -1; ++i)//找到头节点
    		if (isHead[i])head = i;
    	string res = DFS(head);
    	cout << res;
    	return 0;
    }

[Link 1]: https://blog.csdn.net/qq_21480607/article/details/106660085
[Link 2]: https://blog.csdn.net/qq_21480607/article/details/106987591