A1130 | 中缀表达式、查找根节点

代码：

#include <stdio.h>

#include <memory.h>

#include <math.h>

#include <string>

#include <vector>

#include <set>

#include <stack>

#include <queue>

#include <algorithm>

#include <map>

#define I scanf

#define OL puts

#define O printf

#define F(a,b,c) for(a=b;a<c;a++)

#define FF(a,b) for(a=0;a<b;a++)

#define FG(a,b) for(a=b-1;a>=0;a--)

#define LEN 10000

#define MAX 0x06FFFFFF

#define V vector<int>

using namespace std;

typedef struct inputInfo{

    string d;int l,r;

}inputInfo;

typedef struct Node{

    string d;struct Node * l=NULL;struct Node * r=NULL;

    Node(){}

    Node(string D){d=D;}

}Node;

inputInfo infoArr[];

Node *nodes[];

int used[];

Node * insert_node(int index);

void inOrder(Node* node);

Node * root;

int cnt=;

int main() {

    freopen("d:/input/A1130/1.txt","r",stdin);

    int N,i;

    scanf("%d",&N);

    F(i,,N+){

        char buffer[];

        scanf("%s %d %d",buffer,&infoArr[i].l,&infoArr[i].r);

        infoArr[i].d=buffer;

    }

    F(i,,N+){

        if(!used[i])insert_node(i);

        if(cnt>=N) break;

    }

//    printf("%d %d\n",cnt,i);

    root=nodes[i];

    inOrder(root->l);

    printf("%s",root->d.c_str());

    inOrder(root->r);

    return ;

}

Node * insert_node(int index){

    used[index]=;

    cnt++;

    inputInfo info=infoArr[index];

    Node *node=new Node(info.d);

    int l=info.l,r=info.r;

    if(l>)

    if(used[l]){

        node->l=(nodes[l]);

    }else{

        node->l=insert_node(l);

    }

    if(r>)

    if(used[r]){

        node->r=(nodes[r]);

    }else{

        node->r=insert_node(r);

    }

    nodes[index]=node;

    return node;

}

void inOrder(Node* node){

    if(node){

        bool haveK=(node->l||node->r)?:;

        if(haveK) O("(");

        inOrder(node->l);

        printf("%s",node->d.c_str());

        inOrder(node->r);

        if(haveK) O(")");

    }

}

---

主要的点有两个。首先是中缀表达式：

void inOrder(Node* node){

    if(node){

        bool haveK=(node->l||node->r)?:;

        if(haveK) O("(");

        inOrder(node->l);

        printf("%s",node->d.c_str());

        inOrder(node->r);

        if(haveK) O(")");

    }

}

    inOrder(root->l);

    printf("%s",root->d.c_str());

    inOrder(root->r);

对中序遍历稍加修改，就可以得到像这样的中缀表达式：(a+b)*(c*(-d)) 

---

其次是录入输入信息后怎样不浪费时间，巧妙的找到根节点是哪一行记录。这里我们用nodes数组记录树形结点，用used数组记录是否访问过，用cnt记录形成结点的个数，然后递归调用insert_node，就可以及时找到根节点的记录。

需要进步的点：做题速度太慢。