Пре него што разумемо конверзију из инфиксне у постфиксну нотацију, требало би да знамо о инфиксној и постфиксној нотацији одвојено.
Инфикс и постфикс су изрази. Израз се састоји од константи, променљивих и симбола. Симболи могу бити оператори или заграде. Све ове компоненте морају бити распоређене према скупу правила тако да се сви ови изрази могу проценити коришћењем скупа правила.
Примери израза су:
5 + 6
А - Б
јава за паузу
(П * 5)
Сви наведени изрази имају заједничку структуру, тј. имамо оператор између два операнда. Операнд је објекат или вредност на којој треба да се изврши операција. У горњим изразима, 5, 6 су операнди, док су '+', '-' и '*' оператори.
Шта је инфиксна нотација?
Када је оператор написан између операнда, тада је познат као инфиксна нотација . Операнд не мора увек бити константа или променљива; може бити и сам израз.
На пример,
(п + к) * (р + с)
У горњем изразу, оба израза оператора множења су операнди, тј. (п + к) , и (р + с) су операнди.
У горњем изразу постоје три оператора. Операнди за први плус оператор су п и к, операнди за други плус оператор су р и с. Током извођења операције на изразу, морамо да пратимо неки скуп правила да бисмо проценили резултат. У изнад израза, операција сабирања би се извршила на два израза, тј. п+к и р+с, а затим би се извршила операција множења.
Синтакса инфиксне нотације је дата у наставку:
Ако у изразу постоји само један оператор, не захтевамо примену ниједног правила. На пример, 5 + 2; у овом изразу, операција сабирања се може извршити између два операнда (5 и 2), а резултат операције би био 7.
Ако у изразу постоји више оператора, онда је потребно поштовати неко правило да би се проценио израз.
Ако је израз:
4+6*2
Ако се први процени плус оператор, онда би израз изгледао овако:
10 * 2 = 20
Ако се прво процени оператор множења, онда би израз изгледао овако:
4 + 12 = 16
Горњи проблем се може решити праћењем правила приоритета оператора. У алгебарском изразу, редослед приоритета оператора дат је у табели испод:
| Оператери | Симболи |
|---|---|
| Заграда | ( ), {}, [ ] |
| Експоненти | ^ |
| Множење и дељење | *, / |
| Сабирање и одузимање | + , - |
Прва предност се даје загради; онда се следећа предност даје експонентима. У случају вишеструких експонентних оператора, тада ће се операција применити с десна на лево.
На пример:
2^2^3 = 2^8
= 256
Након експонента, процењују се оператори множења и дељења. Ако су оба оператора присутна у изразу, онда ће се операција применити с лева на десно.
Следећа предност се даје сабирању и одузимању. Ако су оба оператора доступна у изразу, идемо с лева на десно.
Оператори који имају исти приоритет се називају као асоцијативност оператора . Ако идемо с лева на десно, онда је то познато као лево-асоцијативно. Ако идемо с десна на лево, онда је познато као десно-асоцијативно.
Проблем са инфиксном нотацијом
Да бисмо проценили инфиксни израз, требало би да знамо о приоритет оператора правила, а ако оператори имају исти приоритет, онда треба да следимо асоцијативност Правила. Употреба заграда је веома важна у инфиксном запису како би се контролисао редослед којим ће се операција извршити. Заграда побољшава читљивост израза. Инфиксни израз је најчешћи начин писања израза, али није лако рашчланити и проценити инфиксни израз без двосмислености. Дакле, математичари и логичари су проучавали овај проблем и открили још два начина писања израза, а то су префикс и постфикс. Оба израза не захтевају никакве заграде и могу се рашчланити без двосмислености. Не захтева предност оператора и правила асоцијативности.
како пронаћи блокиране бројеве на андроиду
Постфик Екпрессион
Постфикс израз је израз у коме се оператор пише иза операнада. На пример, постфиксни израз инфиксне нотације ( 2+3) се може написати као 23+.
Неке кључне тачке у вези са постфикс изразом су:
- У постфикс изразу, операције се изводе редоследом којим су писане с лева на десно.
- Не захтева никакве заграде.
- Не морамо да примењујемо правила приоритета оператора и правила асоцијативности.
Алгоритам за процену постфикс израза
- Скенирајте израз с лева на десно док не наиђемо на било који оператор.
- Извршите операцију
- Замените израз његовом израчунатом вредношћу.
- Понављајте кораке од 1 до 3 док више не постоје оператори.
Хајде да разумемо горњи алгоритам кроз пример.
Инфиксни израз: 2 + 3 * 4
Почећемо да скенирамо већи део израза са леве стране. Оператор множења је оператор који се први појављује док скенирате с лева на десно. Сада би израз био:
функције у в
Израз = 2 + 34*
= 2 + 12
Опет ћемо скенирати с лева на десно, а израз би био:
Израз = 2 12 +
= 14
Процена постфикс израза коришћењем стека.
- Скенирај израз с лева на десно.
- Ако наиђемо на било који операнд у изразу, онда гурамо операнд у стек.
- Када наиђемо на било који оператор у изразу, тада избацујемо одговарајуће операнде из стека.
- Када завршимо са скенирањем израза, коначна вредност остаје у стеку.
Хајде да разумемо процену постфикс израза помоћу стека.
Пример 1: Постфикс израз: 2 3 4 * +
| Улазни | Гомила | |
|---|---|---|
| 2 3 4 * + | празан | Притисните 2 |
| 3 4 * + | 2 | Притисните 3 |
| 4*+ | 3 2 | Притисните 4 |
| * + | 4 3 2 | Искочите 4 и 3 и извршите 4*3 = 12. Гурните 12 у сноп. |
| + | 12 2 | Избаците 12 и 2 из гомиле и извршите 12+2 = 14. Гурните 14 у сноп. |
Резултат горњег израза је 14.
Пример 2: Постфикс израз: 3 4 * 2 5 * +
| Улазни | Гомила | |
|---|---|---|
| 3 4 * 2 5 * + | празан | Притисните 3 |
| 4*2 5*+ | 3 | Притисните 4 |
| *2 5 * + | 4 3 | Избаците 3 и 4 из гомиле и извршите 3*4 = 12. Гурните 12 у сноп. |
| 2 5 * + | 12 | Притисните 2 |
| 5*+ | 2 12 | Притисните 5 |
| *+ | 5 2 12 | Избаците 5 и 2 из гомиле и извршите 5*2 = 10. Гурните 10 у сноп. |
| + | 10 12 | Избаците 10 и 12 из гомиле и извршите 10+12 = 22. Гурните 22 у сноп. |
Резултат горњег израза је 22.
Алгоритам за процену постфикс израза
- Прочитај лик
- Ако је знак цифра, претворите знак у инт и гурните цео број у сноп.
- Ако је знак оператор,
- Избаците елементе из стека двапут да бисте добили два операнда.
- Извршите операцију
- Гурните резултат у гомилу.
Конверзија инфикса у постфикс
Овде ћемо користити структуру података стека за конверзију инфиксног израза у префиксни израз. Кад год наиђе на оператера, гурамо га у стек. Ако наиђемо на операнд, онда изразу додајемо операнд.
Правила за конверзију из инфиксног у постфикс израз
- Штампајте операнд како стигну.
- Ако је стек празан или садржи леву заграду на врху, гурните долазни оператор на стек.
- Ако је улазни симбол '(', гурните га на стек.
- Ако је долазни симбол ')', искочите стек и одштампајте операторе док се не пронађе лева заграда.
- Ако долазни симбол има већи приоритет од врха стека, гурните га на стек.
- Ако долазни симбол има мањи приоритет од врха снопа, искочите и одштампајте врх снопа. Затим тестирајте долазни оператор у односу на нови врх стека.
- Ако долазни оператор има исти приоритет са врхом стека, онда користите правила асоцијативности. Ако је асоцијативност с лева на десно, онда искочите и одштампајте врх стека, а затим притисните долазни оператор. Ако је асоцијативност с десна на лево онда притисните долазни оператор.
- На крају израза искочите и одштампајте све операторе стека.
Хајде да разумемо кроз пример.
Инфиксни израз: К + Л - М*Н + (О^П) * В/У/В * Т + К
| Улазни израз | Гомила | Постфик Екпрессион |
|---|---|---|
| К | К | |
| + | + | |
| Л | + | К Л |
| - | - | К Л+ |
| М | - | К Л+ М |
| * | -* | К Л+ М |
| Н | -* | К Л + М Н |
| + | + | К Л + М Н* К Л + М Н* - |
| ( | + ( | К Л + М Н *- |
| О | + ( | К Л + М Н * - О |
| ^ | + (^ | К Л + М Н* - О |
| П | + (^ | К Л + М Н* - О П |
| ) | + | К Л + М Н* - О П ^ |
| * | + * | К Л + М Н* - О П ^ |
| ИН | + * | К Л + М Н* - О П ^ В |
| / | + / | К Л + М Н* - О П ^ В * |
| ИН | + / | К Л + М Н* - О П ^В*У |
| / | + / | К Л + М Н* - О П ^В*У/ |
| ИН | + / | КЛ + МОН*-УП^В*У/Ф |
| * | + * | КЛ+МОН*-УП^В*У/Ф/ |
| Т | + * | КЛ+МН*-УП^В*У/Ф/Т |
| + | + | КЛ+МОН*-УП^В*У/Ф/Т* КЛ+МН*-УП^В*У/Ф/Т*+ |
| П | + | КЛ+МН*-ОП^В*У/В/Т*К |
| КЛ+МН*-ОП^В*У/В/Т*+К+ |
Коначни постфиксни израз инфиксног израза (К + Л - М*Н + (О^П) * В/У/В * Т + К) је КЛ+МН*-ОП^В*У/В/Т*+К+ .