Expression du suffixe (une question par jour pendant les vacances d'été 4)

Sweetheart 7 - 7 2022-07-23 15:49:26 阅读数:500

expressiondusuffixeunequestion

Compte tenu d'un arbre d'expression binaire,Veuillez afficher l'expression suffixe appropriée,Les parenthèses sont nécessaires pour refléter la priorité de l'opérateur.

Format d'entrée
La première ligne contient un entier N N N,Indique le nombre de noeuds.Numéro du noeud 1 ∼ N 1∼N 1N.

Et puis... N N N D'accord,Chaque ligne donne des informations sur un noeud(No i i i La ligne correspond à la ligne i i i Noeuds),Le format est:

data left_child right_child

Parmi eux,data C'est pas plus que 10 10 10 Chaîne de caractères,left_child Et right_child Sont les numéros des noeuds enfants gauche et droit de ce noeud.

Pas de noeud enfant(C'est - à - dire: NULL),Oui. −1 Représentation.

Les deux figures suivantes correspondent respectivement aux deux exemples donnés.

Insérer la description de l'image ici
Format de sortie
Afficher les réponses en une seule ligne,Il ne doit pas y avoir d'espace entre les symboles d'expression.

Champ d'application des données
1 ≤ N ≤ 20 1≤N≤20 1N20
Exemple d'entrée1:

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

Exemple de sortie1:

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

Exemple d'entrée2:

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

Exemple de sortie2:

(((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;
}
Copyright:Cet article est[Sweetheart 7 - 7]Établi,Veuillez apporter le lien original pour réimprimer,remercier。 https://fra.fheadline.com/2022/204/202207231118586227.html