當前位置:網站首頁>後綴錶達式(暑假每日一題 4)

後綴錶達式(暑假每日一題 4)

2022-07-23 15:49:22sweetheart7-7

給定一個二叉錶達式樹,請你輸出相應的後綴錶達式,要求使用括號反映運算符的優先級。

輸入格式
第一行包含整數 N N N,錶示節點數量。節點編號 1 ∼ N 1∼N 1N

接下來 N N N 行,每行給出一個節點的信息(第 i i i 行對應第 i i i 個節點),格式為:

data left_child right_child

其中,data 是一個不超過 10 10 10 個字符的字符串,left_childright_child 分別是該節點的左右子節點的編號。

沒有子節點(即 NULL),則用 −1 錶示。

下面兩圖分別對應給出的兩個樣例。

在這裏插入圖片描述
輸出格式
在一行中輸出答案,錶達式符號之間不得有空格。

數據範圍
1 ≤ N ≤ 20 1≤N≤20 1N20
輸入樣例1:

8
* 8 7
a -1 -1
* 4 1
+ 2 5
b -1 -1
d -1 -1
- -1 6
c -1 -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

輸出樣例2:

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

#include<iostream>
#include<cstring>

using namespace std;

const int N = 30;

int n;
string a[N];
int l[N], r[N];
bool st[N];

void dfs(int u){
    
    
    cout << '(';
    if(l[u] == -1 && r[u] != -1){
    
        cout << a[u];
        dfs(r[u]);
    }else{
    
        if(l[u] != -1) dfs(l[u]);
        if(r[u] != -1) dfs(r[u]);
        cout << a[u];
    }
    
    cout << ')';
}

int main(){
    
    
    cin >> n;
    
    for(int i = 1; i <= n; i++){
    
        cin >> a[i] >> l[i] >> r[i];
        if(l[i] != -1) st[l[i]] = true;
        if(r[i] != -1) st[r[i]] = true;
    }
    
    int head = -1;
    for(int i = 1; i <= n; i++)
        if(!st[i]) head = i;
    
    dfs(head);
    
    return 0;
}

版權聲明
本文為[sweetheart7-7]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/204/202207231118586227.html

隨機推薦