Шта је инфиксна нотација?
Инфиксна нотација је нотација у којој је израз написан у уобичајеном или нормалном формату. То је нотација у којој се оператори налазе између операнада. Примери инфиксне нотације су А+Б, А*Б, А/Б, итд.
Као што видимо у горњим примерима, сви оператори постоје између операнада, тако да су инфиксне нотације. Дакле, синтакса инфиксне нотације се може написати као:
Парсинг инфикс израза
Да бисмо рашчланили било који израз, морамо да водимо рачуна о две ствари, тј. Приоритет оператера и Асоцијативност . Приоритет оператора значи предност било ког оператора над другим оператором. На пример:
име посебних знакова
А + Б * Ц → А + (Б * Ц)
Како оператор множења има већи приоритет у односу на оператор сабирања, тако ће се Б * Ц израз прво проценити. Резултат множења Б * Ц се додаје А.
Редослед приоритета
| Оператери | Симболи |
|---|---|
| Заграда | { }, ( ), [ ] |
| Експоненцијална нотација | ^ |
| Множење и дељење | *, / |
| Сабирање и одузимање | +, - |
Асоцијативност значи када у изразу постоје оператори са истим приоритетом. На пример, у изразу, тј. А + Б - Ц, оператори '+' и '-' имају исти приоритет, па се процењују уз помоћ асоцијативности. Пошто су и '+' и '-' лево-асоцијативни, они би се оценили као (А + Б) - Ц.
Поредак асоцијативности
| Оператери | Асоцијативност |
|---|---|
| ^ | Десна на лево |
| *, / | С лева надесно |
| +, - | С лева надесно |
Хајде да разумемо асоцијативност кроз пример.
1 + 2*3 + 30/5
Пошто у горњем изразу * и / имају исти приоритет, па ћемо применити правило асоцијативности. Као што можемо приметити у горњој табели да * и / оператори имају асоцијативност с лева на десно, тако ћемо скенирати од крајњег левог оператора. Оператер који дође први ће бити процењен први. Оператор * се појављује пре / оператора, а множење би било прво.
1+ (2*3) + (30/5)
1+6+6 = 13
Шта је префикс нотација?
Префиксна нотација је други облик изражавања, али не захтева друге информације као што су приоритет и асоцијативност, док инфиксна нотација захтева информације о приоритету и асоцијативности. Такође је познато као пољска нотација . У префиксној нотацији, оператор долази испред операнда. Синтакса префиксне нотације је дата у наставку:
На пример, ако је инфиксни израз 5+1, онда је префиксни израз који одговара овом инфиксном изразу +51.
Ако је инфиксни израз:
а * б + ц
↓
*аб+ц
↓
+*абц (префикс израз)
Размотрите још један пример:
А + Б * Ц
Прво скенирање: У горњем изразу, оператор множења има већи приоритет од оператора сабирања; нотација префикса Б*Ц би била (*БЦ).
А + *БЦ
Друго скенирање: У другом скенирању, префикс би био:
+А *БЦ
У горњем изразу користимо два скенирања да конвертујемо инфиксни у префиксни израз. Ако је израз сложен, онда нам је потребан већи број скенирања. Морамо да користимо ону методу која захтева само једно скенирање, а даје жељени резултат. Ако постигнемо жељени резултат једним скенирањем, онда би алгоритам био ефикасан. Ово је могуће само коришћењем стека.
Конверзија инфикса у префикс помоћу стека
К + Л - М * Н + (О^П) * В/У/В * Т + К
Ако конвертујемо израз из инфикса у префикс, прво морамо да обрнемо израз.
Обрнути израз би био:
К + Т * В/У/В * ) П^О(+ Н*М - Л + К
Да бисмо добили израз префикса, направили смо табелу која се састоји од три колоне, тј. улазног израза, стека и израза префикса. Када наиђемо на било који симбол, једноставно га додамо у израз префикса. Ако наиђемо на оператера, гурнућемо га у стек.
| Улазни израз | Гомила | Префиксни израз |
|---|---|---|
| П | П | |
| + | + | П |
| Т | + | КТ |
| * | +* | КТ |
| ИН | +* | КТВ |
| / | +*/ | КТВ |
| ИН | +*/ | КТВУ |
| / | +*// | КТВУ |
| ИН | +*// | КТВУВ |
| * | +*//* | КТВУВ |
| ) | +*//*) | КТВУВ |
| П | +*//*) | КТВУВП |
| ^ | +*//*)^ | КТВУВП |
| О | +*//*)^ | КТВУВПО |
| ( | +*//* | КТВУВПО^ |
| + | ++ | КТВУВПО^*//* |
| Н | ++ | КТВУВПО^*//*Н |
| * | +** | КТВУВПО^*//*Н |
| М | +** | КТВУВПО^*//*НМ |
| - | ++- | КТВУВПО^*//*НМ* |
| Л | ++- | КТВУВПО^*//*НМ*Л |
| + | +-+ | КТВУВПО^*//*НМ*Л |
| К | +-+ | КТВУВПО^*//*НМ*ЛК |
| КТВУВПО^*//*НМ*ЛК+-++ |
Горњи израз, тј. КТВУВПО^*//*НМ*ЛК+-++, није коначни израз. Морамо да обрнемо овај израз да бисмо добили израз префикса.
Правила за конверзију инфиксног у префикс израза:
формат јава стринг
- Прво, обрните инфиксни израз дат у задатку.
- Скенирај израз с лева на десно.
- Кад год операнди стигну, одштампајте их.
- Ако оператер стигне и открије се да је стек празан, једноставно гурните оператора у стек.
- Ако долазни оператор има већи приоритет од ВРХА стека, гурните долазног оператора у стек.
- Ако долазни оператер има исти приоритет са ТОП стека, гурните долазног оператора у стек.
- Ако долазни оператор има мањи приоритет од ВРХА стека, искочите и одштампајте врх стека. Поново тестирајте долазни оператор на врху стека и избаците оператора из стека док не пронађе оператор нижег или истог приоритета.
- Ако долазни оператор има исти приоритет са врхом стека, а долазни оператор је ^, онда искочите врх стека док услов не буде истинит. Ако услов није тачан, притисните оператор ^.
- Када дођемо до краја израза, искочите и одштампајте све операторе са врха стека.
- Ако је оператор ')', онда га гурните у стек.
- Ако је оператор '(', онда извуците све операторе из стека док не пронађе ) отворну заграду у стеку.
- Ако је врх стека ')', гурните оператор на стек.
- На крају обрните излаз.
Псеудокод конверзије инфикса у префикс
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))>