Fișierul intrare/ieșire	inpostfix.in, inpostfix.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	0.05 sec	Limită de memorie	4096 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

Inpostfix (clasa a 10-a)

Se dă un șir de caractere ce reprezintă o expresie aritmetică. Să se afișeze scrierea postfix a acesteia (Forma Inversă Poloneză).

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 inpostfix.in conține pe o singură linie șirul de caractere ce reprezintă notația infix a unei expresii.

Date de ieșire

În fișierul de ieșire inpostfix.out se va găsi un șir de caractere reprezentând notația postfix 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 + – * /
• Expresia conține doar paranteze rotunde ( )

Exemplu