个人练习-PAT甲级-1130 Infix Expression

题目链接https://pintia.cn/problem-sets/994805342720868352/problems/994805347921805312

题目大意：根据表达式树得到中序表达式。

思路是中序遍历。

值得注意的点是什么时候要括号什么时候不加。

在叶子节点仅为一个string时不加
在根节点这一层的递归不用加

实际上所有的非叶节点都是运算符，那么考虑-a,a-e两种情况，发现只要是运算符右儿子非空就需要加括号。如下代码中判断符号看flag即可

    bool flag = (idx != root) && (right != -1);

    if (flag == false) {
        Inorder(left);
        cout << tree[idx].data;
        Inorder(right);
    }
    else {
        printf("(");
        Inorder(left);
        cout << tree[idx].data;
        Inorder(right);
        printf(")");
    }

完整代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;


class Node{
public:
    string data;
    int left, right;
};


vector tree;
vector parent;
int root;


void Inorder(int idx) {
    if (idx == -1)
        return;

    int left = tree[idx].left;
    int right = tree[idx].right;

    bool flag = (idx != root) && (right != -1);

    if (flag == false) {
        Inorder(left);
        cout << tree[idx].data;
        Inorder(right);
    }
    else {
        printf("(");
        Inorder(left);
        cout << tree[idx].data;
        Inorder(right);
        printf(")");
    }

}


int main() {
    int N;
    scanf("%d", &N);
    tree.resize(N+1);
    parent.resize(N+1, 0);

    for (int i = 1; i <= N; i++) {
        cin >> tree[i].data >> tree[i].left >> tree[i].right;
        if (tree[i].left != -1)
            parent[tree[i].left] = i;
        if (tree[i].right != -1)
            parent[tree[i].right] = i;
    }

    for (int i = 1; i <= N; i++) {
        if (parent[i] == 0) {
            root = i;
            break;
        }
    }

    Inorder(root);

    return 0;
}

个人练习-PAT甲级-1130 Infix Expression

C/C++/C#相关栏目本月热门文章