Mikä on infix-merkintä?
Infix-merkintä on merkintä, jossa lauseke kirjoitetaan tavallisessa tai normaalissa muodossa. Se on merkintä, jossa operaattorit sijaitsevat operandien välissä. Esimerkkejä infix-merkinnöistä ovat A+B, A*B, A/B jne.
Kuten yllä olevista esimerkeistä näemme, kaikki operaattorit ovat operandien välissä, joten ne ovat infix-merkintöjä. Siksi infix-merkinnän syntaksi voidaan kirjoittaa seuraavasti:
Infix-lausekkeiden jäsentäminen
Jotta voimme jäsentää mitä tahansa lauseketta, meidän on huolehdittava kahdesta asiasta, esim. Operaattorin etusija ja Assosiatiivisuus . Operaattorin etusijalla tarkoitetaan minkä tahansa operaattorin etusijaa toiseen operaattoriin nähden. Esimerkiksi:
A + B * C → A + (B * C)
Koska kertolaskuoperaattorilla on korkeampi etusija summausoperaattoriin nähden, B * C -lauseke arvioidaan ensin. B * C:n kertolaskutulos lisätään A:han.
Tärkeysjärjestys
| Operaattorit | Symbolit |
|---|---|
| Suluissa | { }, ( ), [ ] |
| Eksponentiaalinen merkintä | ^ |
| Kerto- ja jakolasku | *,/ |
| Yhteen-ja vähennyslasku | +, - |
Assosiatiivisuus tarkoittaa sitä, että lausekkeessa esiintyy operaattorit, joilla on sama etusija. Esimerkiksi lausekkeessa, eli A + B - C, operaattoreilla '+' ja '-' on sama etusija, joten ne arvioidaan assosiatiivisuuden avulla. Koska sekä '+' että '-' ovat vasen assosiatiivisia, ne arvioitaisiin muodossa (A + B) - C.
Assosiaatiojärjestys
| Operaattorit | Assosiatiivisuus |
|---|---|
| ^ | Oikealta vasemmalle |
| *,/ | Vasemmalta oikealle |
| +, - | Vasemmalta oikealle |
Ymmärretään assosiatiivisuus esimerkin kautta.
1 + 2*3 + 30/5
Koska yllä olevassa lausekkeessa * ja / ovat samat, sovellemme assosiatiivisuussääntöä. Kuten yllä olevassa taulukossa voidaan havaita, että * ja /-operaattoreiden assosiatiivisuus on vasemmalta oikealle, joten skannaamme vasemmanpuoleisimmalta operaattorilta. Ensiksi tullut operaattori arvioidaan ensin. Operaattori * näkyy ennen operaattoria /, ja kertolasku tehdään ensin.
1+ (2*3) + (30/5)
1+6+6 = 13
Mikä on etuliitemerkintä?
Etuliitemerkintä on toinen ilmaisumuoto, mutta se ei vaadi muita tietoja, kuten ensisijaisuutta ja assosiatiivisuutta, kun taas infiksimerkintä vaatii tietoa etusijasta ja assosiatiivisuudesta. Se tunnetaan myös nimellä puola merkintä . Etuliitemerkinnöissä operandi tulee ennen operandia. Etuliitemerkinnän syntaksi on annettu alla:
Python lajittelee tuples
Esimerkiksi, jos infiksilauseke on 5+1, niin tätä infiksilauseketta vastaava etuliitelauseke on +51.
Jos infix-lauseke on:
a * b + c
↓
*ab+c
↓
+*abc (etuliitelauseke)
Harkitse toista esimerkkiä:
A + B * C
Ensimmäinen skannaus: Yllä olevassa lausekkeessa kertooperaattorilla on korkeampi prioriteetti kuin summausoperaattorilla; B*C:n etuliitemerkintä olisi (*BC).
A + *BC
Toinen skannaus: Toisessa skannauksessa etuliite olisi:
+A *BC
esimerkki listasta javassa
Yllä olevassa lausekkeessa käytämme kahta skannausta muuntaaksemme liitteen etuliitelausekkeeksi. Jos lauseke on monimutkainen, tarvitsemme suuremman määrän skannauksia. Meidän on käytettävä tätä menetelmää, joka vaatii vain yhden skannauksen ja tarjoaa halutun tuloksen. Jos saavutamme halutun tulosteen yhdellä skannauksella, niin algoritmi olisi tehokas. Tämä on mahdollista vain käyttämällä pinoa.
Infixin muuntaminen etuliitteeksi pinon avulla
K + L - M * N + (O^P) * W/U/V * T + Q
Jos muunnamme lausekkeen infiksista etuliitteeksi, meidän on ensin käännettävä lauseke.
Käänteinen lauseke olisi:
Q + T * V/U/W * ) P^O(+ N*M - L + K
Etuliitelausekkeen saamiseksi olemme luoneet taulukon, joka koostuu kolmesta sarakkeesta, eli syöttölausekkeesta, pinosta ja etuliitelausekkeesta. Kun kohtaamme minkä tahansa symbolin, lisäämme sen yksinkertaisesti etuliitelausekkeeseen. Jos kohtaamme operaattorin, työnnämme sen pinoon.
| Syötelauseke | Pino | Etuliitelauseke |
|---|---|---|
| K | K | |
| + | + | K |
| T | + | QT |
| * | +* | QT |
| SISÄÄN | +* | QTV |
| / | +*/ | QTV |
| SISÄÄN | +*/ | QTVU |
| / | +*// | QTVU |
| SISÄÄN | +*// | QTVUW |
| * | +*//* | QTVUW |
| ) | +*//*) | QTVUW |
| P | +*//*) | QTVUWP |
| ^ | +*//*)^ | QTVUWP |
| O | +*//*)^ | QTVUWPO |
| ( | +*//* | QTVUWPO^ |
| + | ++ | QTVUWPO^*//* |
| N | ++ | QTVUWPO^*//*N |
| * | ++* | QTVUWPO^*//*N |
| M | ++* | QTVUWPO^*//*NM |
| - | ++- | QTVUWPO^*//*NM* |
| L | ++- | QTVUWPO^*//*NM*L |
| + | +-+ | QTVUWPO^*//*NM*L |
| K | +-+ | QTVUWPO^*//*NM*LK |
| QTVUWPO^*//*NM*LK+-++ |
Yllä oleva lauseke, eli QTVUWPO^*//*NM*LK+-++, ei ole lopullinen lauseke. Meidän on käännettävä tämä lauseke saadaksemme etuliitelausekkeen.
Säännöt infixin muuntamiseen etuliitelausekkeeksi:
- Ensin käännä tehtävässä annettu infix-lauseke.
- Skannaa lauseke vasemmalta oikealle.
- Aina kun operandit saapuvat, tulosta ne.
- Jos käyttäjä saapuu paikalle ja pino havaitaan tyhjäksi, työnnä käyttäjä pinoon.
- Jos saapuvan operaattorin etusija on korkeampi kuin pinon TOP, työnnä saapuva operaattori pinoon.
- Jos saapuvalla operaattorilla on sama etusija pinon yläosan kanssa, työnnä saapuva operaattori pinoon.
- Jos saapuvan operaattorin tärkeysjärjestys on pienempi kuin pinon TOP, poksauta ja tulosta pinon yläosa. Testaa tulevaa operaattoria pinon yläosaa vasten uudelleen ja nosta operaattori pinosta, kunnes se löytää operaattorin, jolla on pienempi tai sama tärkeysjärjestys.
- Jos saapuvalla operaattorilla on sama etusija pinon yläosan kanssa ja saapuva operaattori on ^, nosta pinon yläosaa, kunnes ehto on tosi. Jos ehto ei ole tosi, paina ^-operaattoria.
- Kun saavutamme lausekkeen loppuun, paina ja tulosta kaikki operaattorit pinon yläosasta.
- Jos operaattori on ')', työnnä se pinoon.
- Jos operaattori on '(', nosta kaikki operaattorit pinosta, kunnes se löytää ) pinon avaussulku.
- Jos pinon yläosassa on ')', työnnä operaattori pinoon.
- Lopuksi käännä lähtö.
Infixin pseudokoodi etuliitteeksi muuntaminen
Function InfixtoPrefix( stack, infix) infix = reverse(infix) loop i = 0 to infix.length if infix[i] is operand → prefix+= infix[i] else if infix[i] is '(' → stack.push(infix[i]) else if infix[i] is ')' → pop and print the values of stack till the symbol ')' is not found else if infix[i] is an operator(+, -, *, /, ^) → if the stack is empty then push infix[i] on the top of the stack. Else → If precedence(infix[i] > precedence(stack.top)) → Push infix[i] on the top of the stack else if(infix[i] == precedence(stack.top) && infix[i] == '^') → Pop and print the top values of the stack till the condition is true → Push infix[i] into the stack else if(infix[i] == precedence(stack.top)) → Push infix[i] on to the stack Else if(infix[i] <precedence(stack.top)) → pop the stack values and print them till is not empty infix[i] < precedence(stack.top) push on to end loop remaining elements of prefix="reverse(prefix)" return pre> <hr></precedence(stack.top))>