Преди да разберем преобразуването от инфиксна към постфиксна нотация, трябва да знаем за инфиксната и постфиксната нотация поотделно.

Инфикс и постфикс са изразите. Изразът се състои от константи, променливи и символи. Символите могат да бъдат оператори или скоби. Всички тези компоненти трябва да бъдат подредени според набор от правила, така че всички тези изрази да могат да бъдат оценени с помощта на набора от правила.

Примери за изрази са:

5 + 6

А - Б

(P * 5)

Всички горни изрази имат обща структура, т.е. имаме оператор между двата операнда. Операндът е обект или стойност, върху която трябва да се извърши операцията. В горните изрази 5, 6 са операндите, докато '+', '-' и '*' са операторите.

Какво е инфикс нотация?

Когато операторът е написан между операндите, той е известен като инфикс нотация . Операндът не трябва винаги да е константа или променлива; може да бъде и самият израз.

Например,

(p + q) * (r + s)

обработка на низове в c++

В горния израз и двата израза на оператора за умножение са операндите, т.е. (p + q) , и (r + s) са операндите.

В горния израз има три оператора. Операндите за първия оператор плюс са p и q, операндите за втория оператор плюс са r и s. Докато изпълнявате операции върху израза, трябва да следваме някакъв набор от правила, за да оценим резултата. В горния израз, операцията на събиране ще бъде извършена върху двата израза, т.е. p+q и r+s, и след това ще бъде извършена операцията за умножение.

Синтаксисът на инфиксната нотация е даден по-долу:

Ако има само един оператор в израза, не изискваме прилагане на никакво правило. Например 5 + 2; в този израз може да се извърши операция за добавяне между двата операнда (5 и 2), а резултатът от операцията ще бъде 7.

Ако има няколко оператора в израза, тогава трябва да се следва някакво правило, за да се оцени изразът.

Ако изразът е:

какво е 10 от 1 милион

4+6*2

Ако първо се изчисли операторът плюс, тогава изразът ще изглежда така:

10 * 2 = 20

Ако първо се изчисли операторът за умножение, тогава изразът ще изглежда така:

4 + 12 = 16

execlp

Горният проблем може да бъде решен чрез спазване на правилата за приоритет на операторите. В алгебричния израз редът на приоритета на оператора е даден в таблицата по-долу:

Първото предпочитание се дава на скобата; тогава следващото предпочитание се дава на експонентите. В случай на множество експонентни оператори, тогава операцията ще се приложи отдясно наляво.

Например:

2^2^3 = 2^8

= 256

След степента се оценяват операторите за умножение и деление. Ако и двата оператора присъстват в израза, тогава операцията ще се приложи отляво надясно.

Следващото предпочитание се дава на събирането и изваждането. Ако и двата оператора са налични в израза, тогава вървим отляво надясно.

Операторите, които имат същия приоритет, наречени as операторна асоциативност . Ако вървим отляво надясно, тогава е известно като ляво-асоциативно. Ако вървим отдясно наляво, тогава това е известно като дясно-асоциативно.

Проблем с инфиксната нотация

За да оценим инфиксния израз, трябва да знаем за приоритет на оператора правила и ако операторите имат еднакъв приоритет, тогава трябва да следваме асоциативност правила. Използването на скоби е много важно в инфиксната нотация за контролиране на реда, в който трябва да се извърши операцията. Скобите подобряват четливостта на израза. Инфикс изразът е най-често срещаният начин за писане на израз, но не е лесно да се анализира и оцени инфикс изразът без двусмислие. И така, математиците и логиците проучиха този проблем и откриха два други начина за писане на изрази, които са префикс и постфикс. И двата израза не изискват никакви скоби и могат да бъдат анализирани без двусмислие. Не изисква приоритет на оператора и правила за асоциативност.

Постфиксен израз

Постфиксният израз е израз, в който операторът е написан след операндите. Например постфиксният израз на инфиксна нотация ( 2+3) може да бъде написан като 23+.

Някои ключови моменти относно постфиксния израз са:

• В постфиксния израз операциите се извършват в реда, в който са записани отляво надясно.
• Не изисква никакви скоби.
• Не е необходимо да прилагаме правила за приоритет на оператори и правила за асоциативност.

Алгоритъм за изчисляване на постфиксния израз

• Сканирайте израза отляво надясно, докато не срещнем оператор.
• Извършете операцията
• Заменете израза с неговата изчислена стойност.
• Повторете стъпките от 1 до 3, докато не съществуват повече оператори.

Нека разберем горния алгоритъм чрез пример.

Инфиксен израз: 2 + 3 * 4

Ще започнем да сканираме отляво по-голямата част от израза. Операторът за умножение е оператор, който се появява първи при сканиране отляво надясно. Сега изразът ще бъде:

опората на пандата

Израз = 2 + 34*

= 2 + 12

Отново ще сканираме отляво надясно и изразът ще бъде:

Израз = 2 12 +

= 14

Оценка на постфиксен израз с помощта на стек.

• Сканирайте израза отляво надясно.
• Ако срещнем някакъв операнд в израза, тогава избутваме операнда в стека.
• Когато срещнем оператор в израза, изваждаме съответните операнди от стека.
• Когато приключим със сканирането на израза, крайната стойност остава в стека.

Нека разберем оценката на постфиксния израз с помощта на стека.

Пример 1: Постфиксен израз: 2 3 4 * +

Резултатът от горния израз е 14.

Пример 2: Постфиксен израз: 3 4 * 2 5 * +

Резултатът от горния израз е 22.

безплатен ipconfig

Алгоритъм за оценка на постфиксен израз

1. Прочетете знак
2. Ако знакът е цифра, преобразувайте знака в int и поставете цялото число в стека.
3. Ако символът е оператор,
   • Извадете елементите от стека два пъти, за да получите два операнда.
   • Извършете операцията
   • Поставете резултата в стека.

Преобразуване на инфикс в постфикс

Тук ще използваме стековата структура от данни за преобразуване на инфиксен израз в префиксен израз. Всеки път, когато се срещне оператор, ние избутваме оператор в стека. Ако срещнем операнд, тогава добавяме операнд към израза.

Правила за преобразуване от инфиксен към постфиксен израз

1. Отпечатайте операнда, когато пристигнат.
2. Ако стекът е празен или съдържа лява скоба отгоре, натиснете входящия оператор върху стека.
3. Ако входящият символ е '(', натиснете го върху стека.
4. Ако входящият символ е ')', извадете стека и отпечатайте операторите, докато се намери лявата скоба.
5. Ако входящият символ има по-висок приоритет от горната част на стека, натиснете го върху стека.
6. Ако входящият символ има по-нисък приоритет от горната част на стека, извадете и отпечатайте горната част на стека. След това тествайте входящия оператор спрямо новия връх на стека.
7. Ако входящият оператор има същия приоритет като горната част на стека, тогава използвайте правилата за асоциативност. Ако асоциативността е отляво надясно, извадете и отпечатайте горната част на стека, след което натиснете входящия оператор. Ако асоциативността е отдясно наляво, натиснете входящия оператор.
8. В края на израза извадете и отпечатайте всички оператори на стека.

Нека разберем чрез пример.

Инфикс израз: K + L - M*N + (O^P) * W/U/V * T + Q

Крайният постфиксен израз на инфикс израз (K + L - M*N + (O^P) * W/U/V * T + Q) е KL+MN*-OP^W*U/V/T*+Q+ .