1130. Infix Expression (25)

题目:

https://www.patest.cn/contests/pat-a-practise/1130

大概描述:

将一棵语法树,进行展开

特征词:

dfs  中序遍历

使用语言:

C++

解题思想:

先对树进行中序遍历,然后再加括号,需要注意加括号时要进行先前条件的判断,不能是根节点,不能是叶子节点

题目得分:

25

提交次数:

2

时间

inf

代码

#include<cstdio>
#include<vector>
#include<string>
#include<iostream>
#include<cstring>
const int MAXI = 30;
using namespace std;
string ans;
struct p{
 string a;
 int left;
 int right;
};
vector<struct p> m;

//对于一个已知结构的树进行中序遍历
//直接用dfs进行中序遍历

//前序
void qiand(int t){
 //printf("t = %d",t);
 if(t != -1){
 cout << m[t].a;
 }
 if(m[t].left != -1){
 qiand(m[t].left);
 }
 if(m[t].right != -1){
 qiand(m[t].right);
 }

}
//h后序
void houd(int t){
 if(m[t].left != -1){
 houd(m[t].left);
 }
 if(m[t].right != -1){
 houd(m[t].right);
 }
 cout << m[t].a;
}
//中序
int mm;
void zhongd(int t){
 if( t != mm&& (m[t].left != -1||m[t].right != -1))
 cout << "(";
 if(m[t].left != -1){

 zhongd(m[t].left);
 }
 cout << m[t].a;
 if(m[t].right != -1){

 zhongd(m[t].right);
 }
if( t != mm&& (m[t].left != -1||m[t].right != -1))
 cout << ")";
}
//进行序的遍历时,要注意的就是你先要处理的是那一部分,你要明白大体的思路按思路写
int sign[MAXI];
int main(){
 memset(sign,-1,sizeof(sign));
 int m1 = 0;
 scanf("%d",&m1);
 int i = 0;
 struct p pp;
 string s;
 int b,c;
 m.push_back(pp);
 for(i = 0;i < m1;i++){
 cin >>s >>b>>c;
 pp.a = s;
 if(b != -1 ){
 sign[b] = 1;
 }
 if(c != -1){
 sign = 1;
 }
 pp.left = b;
 pp.right = c;
 m.push_back(pp);
 }//这种结构形式更加有方便一些
 //printf("read finished\n");
 //接下来对建好的树进行遍历,首先确定头节点
 int to = 0;
 for(i = 1;i <= m1;i++){
 if(sign[i] != 1){
 to = i;
 break;
 }
 }
 mm = to;
 // printf("to%d\n",to);
 //qiand(to );
 //printf("\n");
 //houd(to);
 //printf("\n");
 zhongd(to);
}

运行结果

25

 成长

这一题让我哭了

真的

感觉一辈子都不会做的题目,规则那么复杂,都看不懂,从很久开始就做的,做了很久很久,还是什么都不懂,感觉一辈子都是跟在别人后面的跟屁虫。那么久那么久。

可终究还是做出来了,用的是我自己的方法。突然能流下眼泪。

刚刚开始题目看不懂什么鬼,查阅资料,又是乱七八糟的,后来就想我自己就直接对它进行中遍历,又忘了中序遍历如何写,只好从前序,后序,中序都写了一遍,等写好后就试着加“(”,“)”,慢慢地有了点感觉,终于终于,修改了几遍后,加对了,希望明天如果在考场有些题目太复杂,可以先写一些简单的,或许会改的很麻烦,但是这也是一个可以尝试的好思路。

加油,fighting!!!

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注