Când scrieți o expresie aritmetică ca B * C, formularul său vă oferă suficiente informații pentru o interpretare corectă. În acest caz, știm că variabila B este înmulțită cu variabila C, deoarece operatorul de multiplicare * este în expresia dintre ele. Acest tip de înregistrare se numește infix. deoarece operatorul este situat între doi operanzi cu care operează.
Luați în considerare un alt exemplu infix: A + B * C. Operatorii + și * sunt încă localizați între operanzi, dar există deja o problemă. Cu ce operandi vor lucra? + funcționează cu A și B sau * acceptă B și C? Expresia pare ambiguă.
Să interpretăm expresia dificilă A + B * C, folosind prioritatea operatorilor. B și C sunt înmulțite mai întâi, apoi rezultatul este adăugat la A. (A + B) * C va determina adăugarea A și B înainte de înmulțire. În expresia A + B + C în ordine (prin asociativitate), se va calcula mai întâi cel mai din stânga +.
Deși acest lucru este evident pentru dvs., rețineți: calculatorul are nevoie de o cunoaștere exactă a modului în care și în ce ordine se calculează operatorii. O modalitate de a scrie o expresie care garantează că nu va exista nici o confuzie cu privire la ordinea operațiilor este crearea a ceea ce se numește o expresie cu paranteze complet distanțate. Acest tip de expresie utilizează o pereche de paranteze pentru fiecare instrucțiune. Parantezele dictează ordinea operațiilor, astfel încât nu există nicio ambiguitate aici. De asemenea, nu este nevoie să vă amintiți regulile pentru stabilirea priorităților.
Expresia A + B * C + D poate fi rescrisă ca (A + (B * C)) + D) pentru a arăta că multiplicarea are loc mai întâi și apoi urmează adăugarea cea mai din stânga. A + B + C + D va fi rescrisă în (((A + B) + C) + D), deoarece operațiile de adăugare sunt asociate de la stânga la dreapta.
Există două formate de expresii importante, care, la prima vedere, vă pot părea nevăzute. Luați în considerare o intrare infix A + B. Ce se întâmplă dacă plasăm un operator în fața a două operanzi? Expresia care rezultă va fi + A B. De asemenea, putem muta afirmația la sfârșit, obținând A B +. Toate astea arată ciudat.
Aceste schimbări în poziția operatorului față de operanzi creează două noi formate - prefix și postfix. O expresie prefixă a unei expresii necesită ca toți operatorii să preceadă cei doi operanzi cu care lucrează. Postfix, la rândul său, cere ca operatorii să meargă după operanzii corespunzători. Câteva exemple suplimentare vă vor ajuta să clarificați acest punct (a se vedea tabelul 2).
A + B * C în notația prefixului poate fi rescrisă ca + A * B C. Operatorul multiplicator este plasat imediat înaintea operanților B și C, indicând prioritatea * peste +. Apoi operatorul de adunare înainte de A și rezultatul multiplicării urmează.
În înregistrarea postfix, expresia arată ca A B C * +. Ordinea operațiilor este salvată din nou, deoarece * este imediat după B și C, indicând faptul că are prioritate față de următoarea +. Deși operatorii se mișcă și sunt acum înaintea sau după operanzii corespunzători, ordinea ultimului în raport unul cu celălalt rămâne exact așa cum a fost.
Tabelul 2: Exemple de înregistrări infix, prefix și postfix
Conversia unei expresii infix la un prefix și un cod Postfix
Până în prezent am utilizat metode speciale pentru a converti între expresiile infix și prefixele echivalente și postfix. După cum vă puteți aștepta, există modalități algoritmice de a efectua astfel de transformări, permițând transformarea corectă a oricărei expresii a oricărei complexități.
Prima dintre tehnicile pe care le considerăm va fi folosirea ideii de aranjare completă a parantezelor în expresia pe care am considerat-o mai devreme. Rețineți că A + B * C poate fi scris ca (A + (B * C)) pentru a indica în mod explicit prioritatea multiplicării înainte de adăugare. Cu toate acestea, după o examinare mai detaliată, veți vedea că fiecare pereche de paranteze marchează de asemenea începutul și sfârșitul perechii de operanzi cu operatorul corespunzător în mijloc.
Uită-te la paranteza dreapta în subexpression (B * C) de mai sus. Dacă mutăm simbolul de înmulțire din poziția sa și eliminăm paranteza stângă corespunzătoare, obținem B C *, atunci subexpresia va fi convertită în notație postfix. Dacă operatorul adițional este mutat și în paranteza dreaptă corespunzătoare și se adaugă paranteza stângă asociată cu acesta, rezultatul este o expresie complet postfix (a se vedea figura 6).
Figura 6: Mutarea operatorilor spre dreapta pentru înregistrarea postfix
Dacă facem același lucru, dar în loc să mutăm caracterul pe poziția în paranteza dreaptă, mutați-l în stânga, obținem o notație de prefix (a se vedea figura 7). Poziția unei perechi de brațe este, de fapt, cheia pentru poziția finală a operatorului cuprins între ele.
Figura 7: Mutarea operatorilor spre stânga pentru înregistrarea prefixelor.
Astfel, atunci când convertiți o expresie (indiferent de cât de complicată) la un prefix sau un postfix, se utilizează aranjamentul complet al parantezelor pentru a stabili ordinea operațiilor. Apoi, operatorul din interiorul lor se mișcă spre extrema din stânga sau spre extrema dreaptă - în funcție de dacă doriți să obțineți prefixul sau înregistrarea postfix.
Iată o expresie mai complexă: (A + B) * C - (D - E) * (F + G). Figura 8 prezintă conversia sa în tipuri de postfix și prefix.
Figura 8: Conversia unei expresii complexe într-un prefix și în înregistrarea postfix.
O transformare generalizată dintr-o vizualizare infix într-o vizualizare postfix
Trebuie să dezvoltăm un algoritm pentru conversia oricărei expresii infix în postfix. Pentru a face acest lucru, să examinăm procesul de conversie în sine.
Luați în considerare din nou expresia A + B * C. După cum sa arătat mai sus, echivalentul său postfix este A B C * +. Am observat deja că operanții A, B și C rămân în locurile lor, iar locația este schimbată numai de operatori. Să aruncăm o privire din nou la operatorii din expresia infix. Primul care trece de la stânga la dreapta este +. Cu toate acestea, în expresia postfix + este la sfârșit, deoarece următorul operator, *, are prioritate față de plus. Ordinea operatorilor în expresia originală este inversă a expresiei postfix rezultate.
În timpul procesării unei expresii, operatorii trebuie să fie stocați undeva până când se găsește operantele lor corespunzătoare. De asemenea, ordinea acestor operatori stocați poate fi inversă (din cauza priorității lor), ca în acest exemplu cu adăugare și multiplicare. Deoarece operatorul de adunare care apare în fața operatorului de multiplicare are o prioritate mai mică, acesta trebuie să apară după ce acesta a fost utilizat. Din cauza acestei ordine inversă, este logic să luați în considerare utilizarea unui stiv pentru a stoca operatorii până când acestea sunt necesare.
Ce zici de (A + B) * C? Amintiți-vă echivalentul postfix: A B + C *. Vom repeta că vom procesa această expresie infix din stânga în dreapta, vom întâlni mai întâi +. În acest caz, atunci când vedem *, + va fi deja plasat în expresia rezultată, deoarece are un avantaj față de * din cauza folosirii parantezelor. Acum putem începe să luăm în considerare funcționarea algoritmului de transformare. Când vedem paranteza stângă, îl salvăm ca semn că ar trebui să apară un alt operator cu o prioritate ridicată. El va aștepta până când paranteza dreaptă corespunzătoare va marca locul său (amintiți-vă tehnica de capsare completă). După ce apare paranteza dreaptă, operatorul este scos din teanc.
Din moment ce scanăm expresia infix din stânga în dreapta, vom folosi stiva pentru a stoca instrucțiunile. Acest lucru ne va da ordinea inversă, care a fost observată în primul exemplu. În partea de sus a stivei, va exista întotdeauna ultimul operator salvat. Ori de câte ori citim noul operator, trebuie să îl comparăm cu prioritate cu operatorii din stivă (dacă există).
Să presupunem că o expresie infix este un șir de jetoane separate prin spații. Jetoanele de operatori sunt *, /, + și - împreună cu parantezele din dreapta și stânga (și). Tokenii operanzi sunt identificatori de o literă A, B, C și așa mai departe. Următoarea secvență de pași va da un șir de jetoane în ordinea postfix.
- Creați un stiv gol numit opstack pentru a stoca operatorii. Creați o listă goală pentru ieșire.
- Conversia unui șir infix la o listă utilizând metoda șirului de divizare.
- Scanați lista de jetoane de la stânga la dreapta.
- Dacă tokenul este un operand, atunci adăugați-l la sfârșitul listei de ieșire.
- Dacă tokenul este o paranteză stângă, puneți-l în opstack.
- Dacă jetonul este paranteza dreaptă, împingeți articolele din opstack până când se găsește paranteza stângă corespunzătoare. Fiecare operator este adăugat la sfârșitul listei de rezultate.
- Dacă jetonul este un operator *, /, + sau -, puneți-l în opstack. Cu toate acestea, înainte de aceasta, împingeți oricare dintre operatorii deja în opstack. dacă are o prioritate mai mare sau egală, și o adăugați la lista care rezultă.
#. Când expresia de intrare este complet procesată, verificați opstack-ul. Orice operatori care sunt încă în el ar trebui să fie împinși și adăugați la sfârșitul listei de rezumate.
Figura 9 prezintă algoritmul de transformare care lucrează la expresia A * B + C * D. Rețineți că primul * operator este șters înainte de a întâlni operatorul +. De asemenea, + rămâne pe stivă când apare al doilea *, deoarece multiplicarea are prioritate față de plus. La sfârșitul expresiei infix, stiva apare de două ori, eliminând ambii operatori și plasând + ca ultimul element în expresia postfix rezultată.
Figura 9: Convertiți A * B + C * D în înregistrarea postfix
Pentru a codifica un algoritm în Python, vom folosi un dicționar numit prec pentru a stoca valorile precedente ale operatorilor. Se leagă fiecare operator la un număr întreg, care poate fi comparat cu numerele altor operatori, ca nivel de prioritate (pentru că am numere întregi 3, 2 și 1 arbitrar ales). Paranteza stângă va obține cea mai mică valoare. Astfel, orice operator comparat cu acesta va avea o prioritate mai mare și va fi situat deasupra acestuia. Linia 15 specifică faptul că operanzii pot fi orice caractere sau numere mari. Funcția de conversie completă este afișată în ActiveCode 8.
Rulați Salvare încărcare afișare în Codelens
Postfix Computing¶
În ultimul exemplu de utilizare a stivei, vom analiza o expresie care este deja în forma postfix. În acest caz, stiva este selectată din nou pentru a rezolva problema. Cu toate acestea, din moment ce scanați o expresie postfix, operanzii, mai degrabă decât operatorii, ar trebui să aștepte rândul lor, spre deosebire de algoritmul de mai sus. O altă modalitate de a ne gândi la această soluție: când un operator este detectat la intrare, cei doi operanzi cei mai recenți vor fi utilizați pentru calcul.
Pentru a înțelege mai detaliat acest lucru, luați în considerare expresia postfix 4 5 6 * +. Dacă îl scanați de la stânga la dreapta, veți întâlni mai întâi operanții 4 și 5. Ce să faceți cu ei este necunoscut până când simbolul următor este cunoscut. Punerea fiecăruia pe teanc garantează disponibilitatea acestora în cazul în care operatorul apare în continuare.
În cazul nostru, următorul personaj este un alt operand. Deci, ca și înainte, puneți-l pe stivă și verificați următorul personaj. Vedem operatorul *, ceea ce înseamnă înmulțirea celor doi operanzi cei mai recenți. După împingerea din stack de două ori, obținem multiplicatorii necesari și apoi efectuăm multiplicarea (în acest caz rezultatul este de 30).
Figura 11 prezintă un exemplu oarecum mai complex: 7 8 + 3 2 + /. Există două puncte care merită notate. În primul rând, mărimea stivei crește, scade și crește din nou în timpul calculului subexpresiilor. În al doilea rând: trebuie să te ocupi de operatorul diviziei foarte atent. Amintiți-vă că operanzii din termenii postfix sunt în ordinea inițială, deoarece postfix modifică numai poziția operatorului. Când operanzii de divizare sunt împinși din teanc, ele sunt în ordine inversă. Deoarece diviziunea nu este operatorul comutativ (cu alte cuvinte, \ (15/5 \) nu este același lucru ca și \ (5/15 \)), trebuie să fim siguri că ordinea operanzilor nu este schimbat.
Figura 11: Un exemplu mai complex de calcul
Să presupunem că expresia postfix este un șir de jetoane separate prin spații. Operatorii sunt *, /, + și -, iar operanzii sunt valori întregi de o singură cifră. Rezultatul va fi un rezultat întreg.
- Creați un stack gol numit operandStack.
- Conversia unui șir într-o listă utilizând metoda șirului de divizare.
- Scanăm lista de jetoane de la stânga la dreapta.
- Dacă tokenul este un operand, atunci convertiți-l dintr-un șir într-un întreg și puneți valoarea în operandStack.
- Dacă tokenul este un operator *, /, + sau -, atunci este nevoie de doi operanzi. Împingem de două ori operandStack. Mai întâi, al doilea operand este împins, apoi primul. Executăm operația aritmetică și punem rezultatul în operandStack.
- Când expresia de intrare este procesată complet, rezultatul acesteia este în stivă. Îl împingem din operandStack și îl returnează ca răspuns.
Funcția completă pentru calcularea expresiilor postfix este afișată în ActiveCode 9. Pentru ajutor cu aritmetică, funcția auxiliară doMath este definită. Este nevoie de doi operanzi și de un operator și apoi efectuează o operație aritmetică adecvată.
Rulați Salvare încărcare afișare în Codelens
Trimiteți-le prietenilor: