Fișierul intrare/ieșire	postinfix.in, postinfix.out	Sursă	Concurs IQ Academy | Clasa a 10-a | Șiruri de caractere
Autor	din folclor	Adăugată de	Teodor Plop • teodor94
Timp de execuție pe test	1 sec	Limită de memorie	16384 KB
Scorul tău	N/A	Dificultate	N/A

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Postinfix (clasa a 10-a)

Se dă un șir de caractere ce reprezintă scrierea postfix (Forma Inversă Poloneză) a unei expresii aritmetice. Să se afișeze scrierea infix a acesteia.

Descriere

Forma infix a unei expresii este forma cu care suntem cu toții obișnuiți:

• operand1 OPERATOR operand2
• A + B
• A * B

Forma postfix se obține prin scrierea operatorului în urma operanzilor:

• operand1 operand2 OPERATOR
• AB+
• AB*

Exemplu pas cu pas

Avem forma infix:

• A * (B + C / D)

Construim forma postfix pas cu pas. Pentru simplitate, vom ignora spațiile: A*(B+C/D).

• Pasul 1. Avem doi termeni: A * (B+C/D). Operația de înmulțire se mută la final.
  • A(B+C/D)*
• Pasul 2: În interiorul parantezei, avem doi termeni: B + C/D. Operația de adunare se mută la final.
  • A(BC/D+)*
• Pasul 3: C/D devine CD/
  • ABCD/+*

Alte exemple

• A + B = AB+
• A + B – C = AB+C-
• A – B * C = ABC*-
• (A – B) / C = AB-C*
• (A + B) * (C + D) = AB+CD+*

Date de intrare

Fișierul de intrare postinfix.in conține pe o singură linie șirul de caractere ce reprezintă notația postfix a unei expresii.

Date de ieșire

În fișierul de ieșire postinfix.out se va găsi un șir de caractere reprezentând notația infix a expresiei.

Restricții

• 1 ≤ lungimea sirului ≤ 100.000
• Operanzii expresiei sunt formați dintr-o singură literă mare din alfabetul englez [A...Z]
• Operatorii aritmetici din expresie sunt + – * /

Precizări

• Se va accepta orice soluție validă. De exemplu:
  • ABC+*D/ -> A*(B+C)/D = (A*(B+C))/D = ((A*(B+C))/D) = ((A*(B+C))/D)
• Altfel spus, în evaluarea sursei se va converti scrierea infix din fișierul de ieșire în postfix, iar rezultatul obținut va fi comparat cu expresia din fișierul de intrare
• Fișierul de ieșire trebuie să conțină maxim 200.000 caractere!

Exemplu