Ennen kuin ymmärrämme muunnoksen infixistä postfix-merkintään, meidän tulisi tietää infix- ja postfix-merkinnät erikseen.
Infix ja postfix ovat ilmaisuja. Lauseke koostuu vakioista, muuttujista ja symboleista. Symbolit voivat olla operaattoreita tai sulkeita. Kaikki nämä komponentit on järjestettävä sääntöjoukon mukaan, jotta kaikki nämä lausekkeet voidaan arvioida sääntöjoukon avulla.
Esimerkkejä ilmauksista ovat:
5 + 6
A-B
(P * 5)
Kaikilla yllä olevilla lausekkeilla on yhteinen rakenne, eli meillä on operaattori kahden operandin välillä. Operandi on objekti tai arvo, jolle operaatio suoritetaan. Yllä olevissa lausekkeissa 5, 6 ovat operandit, kun taas '+', '-' ja '*' ovat operaattoreita.
Mikä on infix-merkintä?
Kun operaattori kirjoitetaan operandien väliin, se tunnetaan nimellä infix-merkintä . Operandin ei tarvitse olla aina vakio tai muuttuja; se voi olla myös itse ilmaisu.
Esimerkiksi,
(p + q) * (r + s)
Yllä olevassa lausekkeessa molemmat kertooperaattorin lausekkeet ovat operandit, ts. (p + q) , ja (r + s) ovat operandit.
Yllä olevassa lausekkeessa on kolme operaattoria. Ensimmäisen plus-operaattorin operandit ovat p ja q, toisen plus-operaattorin operandit ovat r ja s. Suorittaessaan lausekkeen operaatioita, meidän on noudatettava joitain sääntöjä tuloksen arvioimiseksi. Vuonna Yllä oleva lauseke summausoperaatio suoritettaisiin kahdelle lausekkeelle, eli p+q ja r+s, ja sitten suoritettaisiin kertolasku.
Infix-merkinnän syntaksi on annettu alla:
Jos lausekkeessa on vain yksi operaattori, emme vaadi säännön soveltamista. Esimerkiksi 5 + 2; tässä lausekkeessa summausoperaatio voidaan suorittaa kahden operandin (5 ja 2) välillä, ja operaation tulos olisi 7.
python-tavut merkkijonoon
Jos lausekkeessa on useita operaattoreita, lausekkeen arvioimiseksi on noudatettava jotakin sääntöä.
Jos lauseke on:
4+6*2
Jos plus-operaattori arvioidaan ensin, lauseke näyttää tältä:
10 * 2 = 20
Jos kertolaskuoperaattori arvioidaan ensin, lauseke näyttää tältä:
4 + 12 = 16
Yllä oleva ongelma voidaan ratkaista noudattamalla operaattorin ensisijaisuussääntöjä. Algebrallisessa lausekkeessa operaattorin tärkeysjärjestys on annettu alla olevassa taulukossa:
| Operaattorit | Symbolit |
|---|---|
| Suluissa | ( ), {}, [ ] |
| Eksponentit | ^ |
| Kerto- ja jakolasku | *,/ |
| Yhteen-ja vähennyslasku | +,- |
Ensimmäinen etusija annetaan suluille; sitten seuraava etusija annetaan eksponenteille. Useiden eksponenttioperaattoreiden tapauksessa operaatiota sovelletaan oikealta vasemmalle.
Esimerkiksi:
2^2^3 = 2^8
= 256
Eksponentti-, kerto- ja jako-operaattorit arvioidaan. Jos molemmat operaattorit ovat läsnä lausekkeessa, toimintoa sovelletaan vasemmalta oikealle.
Seuraava etusija annetaan yhteen- ja vähennyslaskulle. Jos molemmat operaattorit ovat käytettävissä lausekkeessa, siirrytään vasemmalta oikealle.
Operaattoreita, joilla on sama etusija, kutsutaan nimellä operaattorin assosiatiivisuus . Jos mennään vasemmalta oikealle, niin se tunnetaan vasen-assosiatiivisena. Jos siirrymme oikealta vasemmalle, se tunnetaan oikea-assosiatiivisena.
Ongelma infix-merkinnöissä
Infix-lausekkeen arvioimiseksi meidän pitäisi tietää operaattorin etusijalla säännöt, ja jos operaattoreilla on sama etusija, meidän tulee noudattaa assosiatiivisuus säännöt. Sulujen käyttö on erittäin tärkeää infix-merkinnöissä ohjaamaan järjestystä, jossa toiminto suoritetaan. Sulkeet parantavat lausekkeen luettavuutta. Infix-lauseke on yleisin tapa kirjoittaa lauseke, mutta infix-lausekkeen jäsentäminen ja arvioiminen ilman epäselvyyttä ei ole helppoa. Joten matemaatikot ja loogikot tutkivat tätä ongelmaa ja löysivät kaksi muuta tapaa kirjoittaa ilmaisuja, jotka ovat etuliite ja jälkiliite. Molemmat lausekkeet eivät vaadi sulkuja ja ne voidaan jäsentää ilman epäselvyyttä. Se ei vaadi operaattorin ensisijaisuutta ja assosiaatiosääntöjä.
merkkijonon muuntaminen int
Postfix ilmaus
Postfix lauseke on lauseke, jossa operaattori kirjoitetaan operandien jälkeen. Esimerkiksi infix-merkinnän postfix-lauseke ( 2+3) voidaan kirjoittaa muodossa 23+.
Jotkut postfix-ilmaisun avainkohdat ovat:
- Postfix-lausekkeessa toiminnot suoritetaan siinä järjestyksessä, jossa ne on kirjoitettu vasemmalta oikealle.
- Se ei vaadi sulkuja.
- Meidän ei tarvitse soveltaa operaattorin ensisijaisuussääntöjä ja assosiatiivisuussääntöjä.
Algoritmi postfix-lausekkeen arvioimiseksi
- Skannaa lauseke vasemmalta oikealle, kunnes kohtaamme operaattorin.
- Suorita toimenpide
- Korvaa lauseke sen lasketulla arvolla.
- Toista vaiheet 1–3, kunnes operaattoreita ei enää ole.
Ymmärretään yllä olevaa algoritmia esimerkin avulla.
Infix-lauseke: 2 + 3 * 4
Aloitamme skannauksen suurimman osan lausekkeesta vasemmalta. Kertolasku on operaattori, joka näkyy ensimmäisenä skannattaessa vasemmalta oikealle. Nyt ilmaus olisi:
Lauseke = 2 + 34*
= 2 + 12
Jälleen skannaamme vasemmalta oikealle, ja lauseke olisi:
avl puita
Lauseke = 2 12 +
= 14
Postfix-lausekkeen arviointi pinon avulla.
- Skannaa lauseke vasemmalta oikealle.
- Jos kohtaamme lausekkeessa jonkin operandin, työnnämme operandin pinoon.
- Kun kohtaamme lausekkeessa minkä tahansa operaattorin, poistamme vastaavat operandit pinosta.
- Kun lopetamme lausekkeen skannauksen, lopullinen arvo jää pinoon.
Ymmärretään postfix-lausekkeen arviointi pinon avulla.
Esimerkki 1: Postfix-lauseke: 2 3 4 * +
| Syöte | Pino | |
|---|---|---|
| 2 3 4 * + | tyhjä | Työnnä 2 |
| 34*+ | 2 | Työnnä 3 |
| 4*+ | 3 2 | Työnnä 4 |
| * + | 4 3 2 | Pop 4 ja 3 ja suorita 4*3 = 12. Työnnä 12 pinoon. |
| + | 12 2 | Nosta 12 ja 2 pinosta ja suorita 12+2 = 14. Työnnä 14 pinoon. |
Yllä olevan lausekkeen tulos on 14.
Esimerkki 2: Postfix-lauseke: 3 4 * 2 5 * +
| Syöte | Pino | |
|---|---|---|
| 3 4 * 2 5 * + | tyhjä | Työnnä 3 |
| 4*2 5*+ | 3 | Työnnä 4 |
| *25*+ | 4 3 | Nosta 3 ja 4 pinosta ja suorita 3*4 = 12. Työnnä 12 pinoon. |
| 25*+ | 12 | Työnnä 2 |
| 5*+ | 2 12 | Työnnä 5 |
| *+ | 5 2 12 | Nosta 5 ja 2 pinosta ja suorita 5*2 = 10. Työnnä 10 pinoon. |
| + | 10 12 | Nosta 10 ja 12 pinosta ja suorita 10+12 = 22. Työnnä 22 pinoon. |
Yllä olevan lausekkeen tulos on 22.
Algoritmi postfix-lausekkeen arvioimiseksi
- Lue hahmo
- Jos merkki on numero, muunna merkki int:ksi ja työnnä kokonaisluku pinoon.
- Jos merkki on operaattori,
- Pop elementit pinosta kahdesti saadaksesi kaksi operandia.
- Suorita toimenpide
- Työnnä tulos pinoon.
Infixin muuntaminen postfixiksi
Tässä käytämme pinotietorakennetta infix-lausekkeen muuntamiseen etuliitelausekkeeksi. Aina kun operaattori kohtaa, työnnämme operaattorin pinoon. Jos kohtaamme operandin, liitämme operandin lausekkeeseen.
Säännöt muunnoksille infix-lauseesta postfix-lausekkeeksi
- Tulosta operandi niiden saapuessa.
- Jos pino on tyhjä tai sen päällä on vasen sulkumerkki, työnnä saapuva operaattori pinoon.
- Jos saapuvan viestin symboli on '(', työnnä se pinoon.
- Jos saapuvan viestin symboli on ')', nosta pino ja tulosta operaattorit, kunnes löydät vasen sulkumerkki.
- Jos saapuvan symbolin etusija on suurempi kuin pinon yläosassa, työnnä se pinon päälle.
- Jos saapuvan symbolin tärkeysjärjestys on pienempi kuin pinon yläreuna, poksauta ja tulosta pinon yläosa. Testaa sitten saapuva operaattori pinon uutta yläosaa vasten.
- Jos saapuvalla operaattorilla on sama etusija pinon yläosan kanssa, käytä assosiatiivisuussääntöjä. Jos assosiaatio on vasemmalta oikealle, ponnahda ja tulosta pinon yläosa ja paina sitten tulevaa operaattoria. Jos assosiaatio on oikealta vasemmalle, paina saapuvaa operaattoria.
- Popsaa ja tulosta lausekkeen lopussa kaikki pinon operaattorit.
Ymmärretään esimerkin kautta.
Infix-lauseke: K + L - M*N + (O^P) * W/U/V * T + Q
| Input Expression | Pino | Postfix ilmaus |
|---|---|---|
| K | K | |
| + | + | |
| L | + | K L |
| - | - | K L+ |
| M | - | K L+ M |
| * | -* | K L+ M |
| N | -* | K L + M N |
| + | + | K L + M N* K L + M N* - |
| ( | + ( | K L + M N *- |
| O | + ( | K L + M N * - O |
| ^ | + (^ | K L + M N* - O |
| P | + (^ | K L + M N* - O P |
| ) | + | K L + M N* - O P^ |
| * | + * | K L + M N* - O P^ |
| SISÄÄN | + * | K L + M N* - O P ^ W |
| / | +/ | K L + M N* - O P ^ W * |
| SISÄÄN | +/ | K L + M N* - O P ^W*U |
| / | +/ | K L + M N* - O P ^W*U/ |
| SISÄÄN | +/ | KL + MA*-UP^W*U/F |
| * | + * | KL+MA*-UP^W*U/F/ |
| T | + * | KL+MN*-UP^W*U/F/T |
| + | + | KL+MA*-UP^W*U/F/T* KL+MN*-UP^W*U/F/T*+ |
| K | + | KL+MN*-OP^W*U/V/T*Q |
| KL+MN*-OP^W*U/V/T*+Q+ |
Infix-lausekkeen (K + L - M*N + (O^P) * W/U/V * T + Q) viimeinen jälkiliitteen lauseke on KL+MN*-OP^W*U/V/T*+Q+ .