Перш ніж зрозуміти перетворення з інфіксної нотації на постфіксну, ми повинні знати про інфіксну та постфіксну нотацію окремо.

Інфікс і постфікс - це вирази. Вираз складається з констант, змінних і символів. Символи можуть бути операторами або круглими дужками. Усі ці компоненти мають бути впорядковані відповідно до набору правил, щоб усі ці вирази можна було обчислити за допомогою набору правил.

Приклади виразів:

5 + 6

А - Б

(P * 5)

Усі наведені вище вирази мають спільну структуру, тобто ми маємо оператор між двома операндами. Операнд — це об’єкт або значення, над яким має бути виконана операція. У наведених вище виразах 5, 6 є операндами, а «+», «-» і «*» — операторами.

Що таке інфіксна нотація?

Коли оператор записується між операндами, він називається інфіксне позначення . Операнд не завжди повинен бути константою або змінною; він також може бути самим виразом.

Наприклад,

(p + q) * (r + s)

як дізнатися розмір монітора

У наведеному вище виразі обидва вирази оператора множення є операндами, тобто (p + q) , і (r + s) є операндами.

У наведеному вище виразі є три оператори. Операндами для першого оператора плюса є p і q, операндами для другого оператора плюса є r і s. Під час виконання операцій над виразом, нам потрібно дотримуватися певного набору правил, щоб оцінити результат. В вище виразу, операція додавання буде виконана над двома виразами, тобто p+q і r+s, а потім буде виконана операція множення.

Синтаксис позначення інфіксів наведено нижче:

Якщо у виразі є лише один оператор, нам не потрібно застосовувати жодне правило. Наприклад, 5 + 2; у цьому виразі операцію додавання можна виконати між двома операндами (5 і 2), і результатом операції буде 7.

Якщо у виразі кілька операторів, то для обчислення виразу потрібно дотримуватися певного правила.

Якщо вираз:

replaceall у рядку java

4+6*2

Якщо спочатку обчислюється оператор плюс, то вираз виглядатиме так:

10 * 2 = 20

Якщо спочатку обчислюється оператор множення, то вираз виглядатиме так:

4 + 12 = 16

Зазначену вище проблему можна вирішити, дотримуючись правил пріоритету операторів. В алгебраїчному виразі порядок пріоритету операторів наведено в таблиці нижче:

Перша перевага надається дужці; тоді наступна перевага надається експонентам. У випадку кількох операторів експоненти операція буде застосована справа наліво.

Наприклад:

2^2^3 = 2^8

javascript

= 256

Після обчислюються оператори експоненти, множення та ділення. Якщо обидва оператори присутні у виразі, тоді операція буде застосована зліва направо.

Наступна перевага надається додаванню і відніманню. Якщо у виразі доступні обидва оператори, ми йдемо зліва направо.

Оператори, які мають однаковий пріоритет, називаються як операторна асоціативність . Якщо ми йдемо зліва направо, то це називається лівоасоціативним. Якщо ми йдемо справа наліво, то це називається правоасоціативним.

Проблема з інфіксним позначенням

Щоб оцінити інфіксний вираз, ми повинні знати про пріоритет оператора правила, і якщо оператори мають однаковий пріоритет, ми повинні дотримуватися асоціативність правил. Використання круглих дужок дуже важливо в інфіксній нотації для контролю порядку виконання операції. Дужки покращують читабельність виразу. Інфіксний вираз — це найпоширеніший спосіб написання виразу, але розібрати та оцінити інфіксний вираз без двозначності нелегко. Таким чином, математики та логіки вивчали цю проблему та відкрили два інших способи запису виразів, які є префіксальним та постфіксальним. Обидва вирази не потребують дужок і можуть бути розібрані без двозначності. Він не вимагає пріоритету операторів і правил асоціативності.

Постфіксний вираз

Постфіксний вираз - це вираз, в якому оператор записується після операндів. Наприклад, постфіксний вираз інфіксної нотації (2+3) можна записати як 23+.

Деякі ключові моменти щодо постфіксного виразу:

• У постфіксному виразі операції виконуються в тому порядку, в якому вони записані зліва направо.
• Він не вимагає жодних дужок.
• Нам не потрібно застосовувати правила пріоритету операторів і правила асоціативності.

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

• Переглядайте вираз зліва направо, доки ми не зустрінемо будь-який оператор.
• Виконайте операцію
• Замініть вираз його обчисленим значенням.
• Повторюйте кроки від 1 до 3, доки оператори більше не будуть існувати.

Розберемо наведений вище алгоритм на прикладі.

Інфіксний вираз: 2 + 3 * 4

Ми почнемо сканувати більшу частину виразу зліва. Оператор множення – це оператор, який з’являється першим під час сканування зліва направо. Тепер вираз буде таким:

c логічний

Вираз = 2 + 34*

= 2 + 12

Знову ж таки, ми будемо сканувати зліва направо, і вираз буде таким:

Вираз = 2 12 +

= 14

Обчислення постфіксного виразу за допомогою стека.

• Проскануйте вираз зліва направо.
• Якщо ми зустрічаємо будь-який операнд у виразі, ми поміщаємо операнд у стек.
• Коли ми зустрічаємо будь-який оператор у виразі, ми витягуємо відповідні операнди зі стеку.
• Коли ми завершуємо сканування виразу, кінцеве значення залишається в стеку.

Давайте розберемося з обчисленням постфіксного виразу за допомогою стека.

Приклад 1: Постфіксний вираз: 2 3 4 * +

Результатом наведеного вище виразу є 14.

Приклад 2: Постфіксний вираз: 3 4 * 2 5 * +

Результатом наведеного вище виразу є 22.

прокручування мишею не працює

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

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+ .