Перш ніж зрозуміти перетворення з інфіксної нотації на постфіксну, ми повинні знати про інфіксну та постфіксну нотацію окремо.
Інфікс і постфікс - це вирази. Вираз складається з констант, змінних і символів. Символи можуть бути операторами або круглими дужками. Усі ці компоненти мають бути впорядковані відповідно до набору правил, щоб усі ці вирази можна було обчислити за допомогою набору правил.
Приклади виразів:
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 * +
| Введення | Стек | |
|---|---|---|
| 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.
прокручування мишею не працює
Алгоритм обчислення постфіксного виразу
- Прочитайте персонажа
- Якщо символ є цифрою, перетворите символ на int і помістіть ціле число в стек.
- Якщо символ є оператором,
- Витягніть елементи зі стеку двічі, отримуючи два операнди.
- Виконайте операцію
- Помістіть результат у стек.
Перетворення інфікса в постфікс
Тут ми будемо використовувати стекову структуру даних для перетворення інфіксного виразу у префіксний вираз. Щоразу, коли оператор стикається, ми вставляємо оператора в стек. Якщо ми зустрічаємо операнд, ми додаємо операнд до виразу.
Правила перетворення інфіксного виразу в постфіксний
- Друкуйте операнд, коли вони надходять.
- Якщо стек порожній або містить ліву дужку вгорі, надішліть вхідний оператор до стеку.
- Якщо вхідним символом є '(', перемістіть його в стек.
- Якщо вхідним символом є «)», витягніть стек і виведіть оператори, доки не буде знайдено ліву дужку.
- Якщо вхідний символ має вищий пріоритет, ніж вершина стека, помістіть його в стек.
- Якщо вхідний символ має нижчий пріоритет, ніж верхня частина стека, витягніть і надрукуйте верхню частину стека. Потім протестуйте вхідний оператор на новій вершині стека.
- Якщо вхідний оператор має такий самий пріоритет, як і верхня частина стека, використовуйте правила асоціативності. Якщо асоціативність розташована зліва направо, витягніть і надрукуйте верхню частину стека, а потім натисніть вхідний оператор. Якщо асоціативність справа наліво, натисніть вхідний оператор.
- У кінці виразу витягніть і виведіть усі оператори стека.
Розберемося на прикладі.
Інфіксний вираз: K + L - M*N + (O^P) * W/U/V * T + Q
| Вхідний вираз | Стек | Постфіксний вираз |
|---|---|---|
| К | К | |
| + | + | |
| Л | + | К Л |
| - | - | K L+ |
| М | - | K L+ M |
| * | - * | K L+ M |
| Н | - * | K L + M N |
| + | + | K L + M N* K L + M N* - |
| ( | + ( | K L + M N *- |
| О | + ( | K L + M N * - O |
| ^ | + (^ | K L + M N* - O |
| П | + (^ | K L + M N* - O P |
| ) | + | K L + M N* - O P ^ |
| * | + * | K L + M N* - O P ^ |
| IN | + * | K L + M N* - O P ^ W |
| / | + / | K L + M N* - O P ^ W * |
| IN | + / | K L + M N* - O P ^W*U |
| / | + / | K L + M N* - O P ^W*U/ |
| IN | + / | KL + MON*-UP^W*U/F |
| * | + * | KL+MON*-UP^W*U/F/ |
| Т | + * | KL+MN*-UP^W*U/F/T |
| + | + | ПН+ПН*-ВГОРУ^Ш*У/П/Т* KL+MN*-UP^W*U/F/T*+ |
| Q | + | KL+MN*-OP^W*U/V/T*Q |
| KL+MN*-OP^W*U/V/T*+Q+ |
Остаточним постфіксальним виразом інфіксного виразу (K + L - M*N + (O^P) * W/U/V * T + Q) є KL+MN*-OP^W*U/V/T*+Q+ .