PAT甲级1130.

目录

A1130

题目

样例

样例1

输入:

8
* 8 7
a -1 -1
* 4 1
+ 2 5
b -1 -1
d -1 -1
- -1 6
c -1 -1

输出:

(a+b)*(c*(-d))

样例2

输入:

8
2.35 -1 -1
* 6 1
- -1 4
% 7 8
+ 2 3
a -1 -1
str -1 -1
871 -1 -1

输出:

(a*2.35)+(-(str%871))

思路和坑点

　　思路：
　　根据数据构建二叉树，然后对二叉树使用中序遍历获取中缀表达式，注意括号的处理。

AC代码

#include<bits/stdc++.h>
using namespace std; 
typedef struct node{                  //二叉树结点定义，使用静态数组存储，所以指针为int
    string data;
    int left=-1,right=-1;
}Node;
Node T[25];                           //存储树的数据
string inorder(int root);             //中序遍历获取中缀表达式
int main(){    
#ifdef ONLINE_JUDGE    
#else    
    freopen("1.txt", "r", stdin);    
#endif    
    int n;
    scanf("%d",&n);                     
    if(n==1) {                        //特判 
        string temp;
        cin>>temp;
        cout<<temp;
        return 0;
    }
    bool isroot[25]={0};              //标记根，如果不是根则标记为1，最后剩余的0便是根
    for(int i=1;i<=n;i++){            //读入数据并修改标记
        cin>>T[i].data;
        scanf("%d%d",&T[i].left,&T[i].right);
        if(T[i].left!=-1) isroot[T[i].left]=1;
        if(T[i].right!=-1) isroot[T[i].right]=1;
    }
    int root;                         //查找根
    for(int i=1;i<=n;i++){
        if(isroot[i]==0){
            root=i;break;
        }
    }
    string out=inorder(root);         //遍历获得结果
    cout<<out.substr(1,out.size()-2); //去最外层括号 
    return 0;    
}
string inorder(int root)
{
    if(T[root].left==-1&&T[root].right==-1)    return T[root].data; //单个结点返回数据即可
    else{
        string temp="(";                                            //添加左括号
        if(T[root].left!=-1) temp+=inorder(T[root].left);           //获取左子树的表达式
        temp+=T[root].data;                                         //加上当前结点的值
        if(T[root].right!=-1) temp+=inorder(T[root].right);         //追加右子树的表达式
        temp+=")";                                                  //添加右括号
        return temp;                                                //返回整个表达式
    }
}