View source for 3536 - EvaluareExpresie

= Cerința =
Se consideră o expresie aritmetică formată din numere naturale și operatorii binari <code>+</code> (adunare), <code>-</code> (scădere), <code>*</code> (înmulțire), <code>^</code> (ridicare la putere). Să se determine forma postfixată corespunzătoare și să se calculeze valoarea expresiei.

Spunem că expresia este în formă infixată dacă fiecare operator binar este încadrat de cei doi operanzi ai săi. Aceasta este de fapt forma uzuală a expresiilor aritmetice.

Spunem că expresia este în formă postfixată dacă fiecare operator este poziționat după operanzii săi, respectând prioritatea și regula de asociere a operatorilor.

De exemplu, expresia aritmetică în formă infixată: <code>1*2+3^4</code> poate fi rescrisă în forma postfixată astfel:

<code>1*2+3^4 → (parantezare) → ((1*2)+(3^4)) → (postfixare +) → ((1*2)(3^4)+) → (postfixare * și ^) → ((1 2 *)(3 4 ^) +) → (eliminare paranteze) → 1 2 * 3 4 ^ +</code>

Valoarea expresiei date este <code>83</code>.

= Date de intrare =
Fișierul de intrare <code>evaluareexpresie.in</code> conține pe un singur rând un șir de caractere ce reprezintă o expresie aritmetică corect construită ce poate conține numai operatorii binari <code>+</code>, <code>-</code>, <code>*</code>, <code>^</code>, cu semnificațiile de mai sus, și operanzi constante numere naturale.

= Date de ieșire =
Fișierul de ieșire <code>evaluareexpresie.out</code> va conține pe prima linie un șir de caractere ce reprezintă forma postfixată a expresiei date, iar pe cel de-al doilea rând un număr natural ce reprezintă valoarea expresiei date. Pentru forma postfixată operanzii și operatorii vor fi separați cu câte un spațiu. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* Lungimea expresiei din fișierul de intrare va fi de cel mult <code>50</code> de caractere
* Rezultatul final precum și rezultatele intermediare se vor încadra în tipul de date <code>long long</code>
* Expresia este corectă și nu conține alte caractere în afară de cifre și operatorii <code>+</code>, <code>-</code>, <code>*</code>, <code>^</code>

= Exemplul 1: =
<code>evaluareexpresieIN.txt</code>
 100-2*3^2
<code>evaluareexpresieOUT.txt</code>
 100 2 3 2 ^ * -
 82

=== Explicație ===
<code>100-2*3^2 → (100-(2*(3^2))) → (100-(2*(3 2^))) → (100-(2(3 2^)*)) → (100(2(3 2^)*)-) → 100 2 3 2 ^ * -</code>

Valoare expresiei este <code>82</code>.

Exemplul 2:
<code>evaluareexpresieIN.txt</code>
 100-2*3^2@
<code>evaluareexpresieOUT.txt</code>
 Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
import math

def convert(i, j, pf):
    rez = 0
    for k in range(i, j+1):
        cifra = int(pf[k])
        rez = rez * 10 + cifra
    return rez

def afisare(pf, P):
    result = ""
    for i in range(1, P+1):
        if pf[i] == '#':
            result += " "
        elif pf[i] in "^+-*":
            result += pf[i] + " "
        else:
            result += pf[i]
    return result

def main():
    with open("evaluareexpresieIN.txt", "r") as f:
        S = f.read().strip()
    mp = {'^': 3, '*': 2, '+': 1, '-': 1}
    P = 0
    pf = [''] * 105
    ST = []
    Rez = []
    i = 0
    l = len(S)
    while i < l:
        if '0' <= S[i] <= '9':
            P += 1
            pf[P] = S[i]
        else:
            P += 1
            pf[P] = '#'
            while ST and mp[ST[-1]] >= mp[S[i]]:
                op = ST.pop()
                P += 1
                pf[P] = op
            ST.append(S[i])
        i += 1
    P += 1
    pf[P] = '#'
    while ST:
        P += 1
        pf[P] = ST.pop()
    result = afisare(pf, P)
    with open("evaluareexpresieOUT.txt", "w") as g:
        g.write(result + '\n')
    start = 1
    for i in range(2, P+1):
        if start == -1 and pf[i-1] in "#^+-*" and '0' <= pf[i] <= '9':
            start = i
        if pf[i] == '#' and start != -1:
            nr = convert(start, i-1, pf)
            Rez.append(nr)
            start = -1
        elif pf[i] in "^*+-":
            nr1 = Rez.pop()
            nr2 = Rez.pop()
            if pf[i] == '^':
                r = math.pow(nr2, nr1)
            elif pf[i] == '*':
                r = nr2 * nr1
            elif pf[i] == '+':
                r = nr2 + nr1
            else:
                r = nr2 - nr1
            Rez.append(r)
    with open("evaluareexpresieOUT.txt", "a") as g:
        g.write(str(Rez[-1]))

if __name__ == "__main__":
    main()

</syntaxhighlight>