3536 - EvaluareExpresie

Cerinta

Se consideră o expresie aritmetică formată din numere naturale și operatorii binari + (adunare), - (scădere), * (înmulțire), ^ (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ă: 1*2+3^4 poate fi rescrisă în forma postfixată astfel: 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 ^ + Valoarea expresiei date este 83.

Date de intrare

Fișierul de intrare evaluareexpresie.in 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 +, -, *, ^, cu semnificațiile de mai sus, și operanzi constante numere naturale.

Date de iesire

Fișierul de ieșire evaluareexpresie.out 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.

Restrictii si precizari

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

Exemplul 1

intrare

100-2*3^2

iesire

Datele introduse corespund restrictiilor impuse.

100 2 3 2 ^ * -

82

Exemplul 2

intrare

-77 1 2 1 ^ * -

6

iesire

Datele de intrare nu corespund restrictiilor impuse.

Rezolvare

3536 - EvaluareExpresie

def este_operator(caracter):

   return caracter in {'+', '-', '*', '^'}

def prioritate(operator):

   if operator == '^':
       return 3
   elif operator in {'*', '/'}:
       return 2
   elif operator in {'+', '-'}:
       return 1
   return 0

def infix_to_postfix(expresie):

   postfix = []
   stiva_operatori = []

   for caracter in expresie:
       if caracter.isalnum():
           postfix.append(caracter)
       elif caracter == '(':
           stiva_operatori.append(caracter)
       elif caracter == ')':
           while stiva_operatori and stiva_operatori[-1] != '(':
               postfix.append(stiva_operatori.pop())
           stiva_operatori.pop()  # Elimină '(' din stivă
       elif este_operator(caracter):
           while stiva_operatori and prioritate(stiva_operatori[-1]) >= prioritate(caracter):
               postfix.append(stiva_operatori.pop())
           stiva_operatori.append(caracter)

   while stiva_operatori:
       postfix.append(stiva_operatori.pop())

   return postfix

def evalueaza_postfix(postfix):

   stiva = []

   for caracter in postfix:
       if caracter.isalnum():
           stiva.append(int(caracter))
       elif este_operator(caracter):
           operand2 = stiva.pop()
           operand1 = stiva.pop()
           if caracter == '+':
               stiva.append(operand1 + operand2)
           elif caracter == '-':
               stiva.append(operand1 - operand2)
           elif caracter == '*':
               stiva.append(operand1 * operand2)
           elif caracter == '^':
               stiva.append(operand1 ** operand2)

   return stiva[0]

</syntaxhighlight>