Înainte de a înțelege conversia de la notația infix la postfix, ar trebui să știm despre notațiile infix și postfix separat.

Un infix și un postfix sunt expresii. O expresie constă din constante, variabile și simboluri. Simbolurile pot fi operatori sau paranteze. Toate aceste componente trebuie aranjate după un set de reguli astfel încât toate aceste expresii să poată fi evaluate folosind setul de reguli.

Exemple de expresii sunt:

5 + 6

A - B

(P * 5)

Toate expresiile de mai sus au o structură comună, adică avem un operator între cei doi operanzi. Un operand este un obiect sau o valoare pe care urmează să fie efectuată operația. În expresiile de mai sus, 5, 6 sunt operanzii, în timp ce „+”, „-” și „*” sunt operatorii.

Ce este notația infixă?

Când operatorul este scris între operanzi, atunci este cunoscut ca notație infixă . Operandul nu trebuie să fie întotdeauna o constantă sau o variabilă; poate fi și o expresie în sine.

De exemplu,

(p + q) * (r + s)

În expresia de mai sus, ambele expresii ale operatorului de multiplicare sunt operanzi, adică (p + q) , și (r + s) sunt operanzii.

În expresia de mai sus, există trei operatori. Operanzii pentru primul operator plus sunt p și q, operanzii pentru al doilea operator plus sunt r și s. În timpul efectuării operațiuni asupra expresiei, trebuie să respectăm un set de reguli pentru a evalua rezultatul. În expresiei de mai sus, operația de adunare ar fi efectuată pe cele două expresii, adică p+q și r+s, apoi ar fi efectuată operația de înmulțire.

cifre romane 1100

Sintaxa notației infixe este prezentată mai jos:

Dacă există un singur operator în expresie, nu avem nevoie de aplicarea vreunei reguli. De exemplu, 5 + 2; în această expresie, operația de adunare poate fi efectuată între cei doi operanzi (5 și 2), iar rezultatul operației ar fi 7.

Dacă există mai mulți operatori în expresie, atunci trebuie urmată o regulă pentru a evalua expresia.

Dacă expresia este:

4+6*2

Dacă operatorul plus este evaluat mai întâi, atunci expresia ar arăta astfel:

10 * 2 = 20

Dacă operatorul de multiplicare este evaluat mai întâi, atunci expresia ar arăta astfel:

4 + 12 = 16

Problema de mai sus poate fi rezolvată urmând regulile de prioritate a operatorului. În expresia algebrică, ordinea de prioritate a operatorului este dată în tabelul de mai jos:

Prima preferință este dată parantezei; apoi următoarea preferință este dată exponenților. În cazul operatorilor cu exponenți multipli, atunci operația va fi aplicată de la dreapta la stânga.

replaceall în șir de caractere java

De exemplu:

2^2^3 = 2^8

= 256

fmovies India

După ce sunt evaluați operatorii exponent, înmulțire și împărțire. Dacă ambii operatori sunt prezenți în expresie, atunci operația va fi aplicată de la stânga la dreapta.

Următoarea preferință este dată de adunare și scădere. Dacă ambii operatori sunt disponibili în expresie, atunci mergem de la stânga la dreapta.

Operatorii care au aceeași prioritate numiți ca asociativitatea operatorului . Dacă mergem de la stânga la dreapta, atunci este cunoscut ca stânga-asociativ. Dacă mergem de la dreapta la stânga, atunci este cunoscut ca drept-asociativ.

Problemă cu notația infixă

Pentru a evalua expresia infixă, ar trebui să știm despre prioritatea operatorului reguli, iar dacă operatorii au aceeași prioritate, atunci ar trebui să respectăm asociativitatea reguli. Utilizarea parantezei este foarte importantă în notația infixă pentru a controla ordinea în care operația trebuie efectuată. Paranteza îmbunătățește lizibilitatea expresiei. O expresie infixă este cel mai comun mod de a scrie expresia, dar nu este ușor să analizați și să evaluați expresia infixă fără ambiguitate. Deci, matematicienii și logicienii au studiat această problemă și au descoperit alte două moduri de a scrie expresii care sunt prefix și postfix. Ambele expresii nu necesită nicio paranteză și pot fi analizate fără ambiguitate. Nu necesită reguli de prioritate și asociativitate a operatorului.

Expresie Postfix

Expresia postfix este o expresie în care operatorul este scris după operanzi. De exemplu, expresia postfixă a notației infixe ( 2+3) poate fi scrisă ca 23+.

Câteva puncte cheie referitoare la expresia postfix sunt:

• În expresia postfixă, operațiile sunt efectuate în ordinea în care au scris de la stânga la dreapta.
• Nu necesită nicio paranteză.
• Nu trebuie să aplicăm regulile de precedență ale operatorilor și regulile de asociativitate.

Algoritm pentru evaluarea expresiei postfix

• Scanați expresia de la stânga la dreapta până când întâlnim orice operator.
• Efectuați operația
• Înlocuiți expresia cu valoarea sa calculată.
• Repetați pașii de la 1 la 3 până când nu mai există operatori.

Să înțelegem algoritmul de mai sus printr-un exemplu.

Expresie infixă: 2 + 3 * 4

Vom începe să scanăm din stânga cea mai mare parte a expresiei. Operatorul de multiplicare este un operator care apare primul în timpul scanării de la stânga la dreapta. Acum, expresia ar fi:

Expresie = 2 + 34*

= 2 + 12

Din nou, vom scana de la stânga la dreapta, iar expresia ar fi:

Expresie = 2 12 +

= 14

Evaluarea expresiei postfix folosind stiva.

• Scanați expresia de la stânga la dreapta.
• Dacă întâlnim orice operand în expresie, atunci împingem operandul în stivă.
• Când întâlnim orice operator în expresie, atunci scoatem operanzii corespunzători din stivă.
• Când terminăm cu scanarea expresiei, valoarea finală rămâne în stivă.

Să înțelegem evaluarea expresiei postfix folosind stiva.

Exemplul 1: Expresie postfix: 2 3 4 * +

Rezultatul expresiei de mai sus este 14.

Exemplul 2: Expresie postfix: 3 4 * 2 5 * +

Rezultatul expresiei de mai sus este 22.

moștenirea java

Algoritm pentru evaluarea expresiei postfix

1. Citiți un personaj
2. Dacă caracterul este o cifră, convertiți caracterul în int și împingeți întregul în stivă.
3. Dacă personajul este un operator,
   • Scoateți elementele din stivă de două ori obținând doi operanzi.
   • Efectuați operația
   • Împingeți rezultatul în stivă.

Transformarea infixului în postfix

Aici, vom folosi structura de date stiva pentru conversia expresiei infixe în expresie prefixă. Ori de câte ori se va întâlni un operator, îl împingem în stivă. Dacă întâlnim un operand, atunci anexăm operandul expresiei.

Reguli pentru conversia de la expresia infixă la expresia postfixă

1. Imprimați operandul pe măsură ce sosesc.
2. Dacă stiva este goală sau conține o paranteză din stânga deasupra, împingeți operatorul de intrare pe stivă.
3. Dacă simbolul de intrare este „(”, împingeți-l în stivă.
4. Dacă simbolul de intrare este „)”, deschideți stiva și tipăriți operatorii până când se găsește paranteza din stânga.
5. Dacă simbolul de intrare are o prioritate mai mare decât partea de sus a stivei, împingeți-l pe stivă.
6. Dacă simbolul de intrare are o prioritate mai mică decât partea de sus a stivei, deschideți și imprimați partea de sus a stivei. Apoi testați operatorul de intrare față de noul vârf al stivei.
7. Dacă operatorul de intrare are aceeași prioritate cu partea de sus a stivei, atunci utilizați regulile de asociativitate. Dacă asociativitatea este de la stânga la dreapta, apăsați și imprimați partea de sus a stivei, apoi apăsați operatorul de intrare. Dacă asociativitatea este de la dreapta la stânga atunci apăsați operatorul de intrare.
8. La sfârșitul expresiei, pop și tipăriți toți operatorii stivei.

Să înțelegem printr-un exemplu.

Expresie infixă: K + L - M*N + (O^P) * W/U/V * T + Q

Expresia postfixă finală a expresiei infixe (K + L - M*N + (O^P) * W/U/V * T + Q) este KL+MN*-OP^W*U/V/T*+Q+ .