На уроках математики нас учили правильно вычислять значения выражений. Один из пунктов получения правильного ответа — корректно определить порядок выполнения операций. Ещё со школы мы знаем, что выражение в скобках выполняют в первую очередь, а деление и умножение приоритетнее сложения и вычитания.
Человек мыслит в этой математической парадигме. А вот компьютер не “мыслит” как человек. В этой статье мы взглянем под капот и узнаем, как в программировании работают с математическими операциями.
Инфиксная, префиксная и постфиксная формы
Инфиксная форма
Форма записи или нотация — это правила составления выражений и их декомпозиции. Возьмем простое выражение:
Вот классический алгоритм вычисления значения этого выражения:
- Вычисляем 15*4 = 60;
- Вычисляем 6/2 = 3;
- Складываем все слагаемые: 10 + 60 + 3 = 73.
Здесь используется инфиксная форма записи — операции (сложение, вычитание, умножение и деление) записываются между аргументами (числами, переменными, функциями и другими математическими объектами). Инфиксная форма естественна для человека и используется людьми в повседневной жизни.
Но компьютеру сложнее разобрать такую форму записи. Поэтому обычно в компьютерах используется префиксная или постфиксная формы.
Префиксная форма
Префиксная нотация — это форма записи, в которой операторы располагают слева от аргументов.
Возьмем пример 5 + 10. Это запись в инфиксной форме. В префиксной форме она будет иметь такой вид:
Для лучшего понимания стоит переводить этот пример в человеческий язык “Прибавить к 5 10”. Аналогично с – 5 10 — “Отнять от 5 10”. Возьмем пример посложнее:
Переведем это выражение в префиксную форму:
- Расставим в выражении скобки, руководствуясь приоритетностью операций (для читабельности используем разные скобки):
- Вынесем за пределы скобок операции, а в скобках оставим аргументы:
- Уберем скобки и получим префиксную форму записи:
+ – 64 * 15 4 / 20 4 — это префиксная форма записи выражения 64 – 15*4 + 20/4. Прочитать её можно как “ПРИБАВИМ к результату ВЫЧИТАНИЯ из 64 ПРОИЗВЕДЕНИЯ 15 и 4 результат ДЕЛЕНИЯ 20 на 4.
Как перевести запись обратно? Есть рекурсивный способ сделать это. Возьмем выражение + x y (в инфиксной x+y) и переведем в инфиксную форму:
- Берем первый оператор:
- Ставим слева от него первый аргумент:
- Справа ставим второй аргумент:
В качестве x и y могут выступать выражения в префиксной записи, к которым рекурсивно можно применять этот алгоритм. Возьмем наше выражение:
- Первый оператор — это
+. Начинаем с него. - Первый аргумент — это
– 64 * 15 4. Запишем его в скобках справа от оператора:
- Второй аргумент — это
/ 20 4. Записываем его справа от оператора:
Теперь рекурсивно применяем алгоритм к каждому слагаемому. Сначала для – 64 * 15 4:
- Первый оператор — это
–. Начинаем с него. - Первый аргумент — это
64. Запишем его справа от оператора:
- Второй аргумент — это
* 15 4. Записываем его справа от оператора:
Для * 15 4:
- Оператор
*; - Первый аргумент –
15; - Второй –
4;
Получаем 15 * 4 и вставляем его в 64 – (* 15 4). Вот первый аргумент “основного” примера:
Для / 20 4:
- Оператор
/; - Первый аргумент –
20; - Второй –
4;
Получаем 20 / 4. Вставляем его и первый аргумент в “основной” пример:
Облачные серверы
по всему миру с почасовой оплатой.
Постфиксная форма записи выражений
Постфиксная нотация — это форма записи, в которой операторы располагаются справа от аргументов. Выражение 5 + 10 в постфиксной форме будет иметь вид 5 10 +. Возьмем предыдущий пример и переведем его постфиксную форму аналогичным способом:
Перевод инфиксной в постфиксную нотацию:
- Расставляем скобки по приоритетности операций. Также для читабельности используем разные скобки:
- Выносим за скобки операции и ставим их справа от аргументов:
- Убираем все скобки и получаем постфиксную форму:
Для перевода из постфиксной в инфиксную будем идти не от большего к малому, как с префи, а наоборот. Рассмотрим рекурсивный алгоритм действий для x y +:
- Берем первый аргумент
x; - Берем второй аргумент
y; - Между ними помещаем оператор
+:x + y
Применим его для 64 15 4 * – 20 4 / +:
- Берем первый аргумент
64; - Берем следующий аргумент
15; - Дальше идет тоже аргумент, а значит есть более “вложенная” операция.
Разбираемся с аргументом 15:
- Берем следующий аргумент
4; - Берем операцию
*; - Совмещаем и получаем
15 * 4;
Возвращаемся к 64 со вторым аргументом 15 * 4:
- Берем операцию
–и помещаем между аргументами:
Переходим к 20:
- Видим, что после
20идет не операция, и разбираемся с20 4 /. Получаем20 / 4.
Возвращаемся к 64 – 15 * 4. Это первый аргумент, 20 / 4 — второй. Смотрим операцию и вставляем её между аргументами:
Зачем нужна префиксная и постфиксная форма?
Когда человек смотрит на пример в инфиксной форме, он видит картину целиком и может расставить порядок операций, отталкиваясь от их приоритета.
В компьютер математический пример поступает последовательно: сначала аргумент, потом операция и не ясно, будет ли дальше более приоритетная операция. В постфиксной и префиксной форме порядок операций определяется самой записью и компьютер может вычислять пример последовательно.
Алгоритм сортировочной станции
Алгоритм сортировочной станции или сортировочная станция Дейкстры — это алгоритм для преобразования инфиксной формы в постфиксную нотацию или дерево, придуманный и разработанный Эдсгером Дейкстрой.
В алгоритме используется два объекта для хранения — стек и очередь. Разберемся, что это такое.
Стек (Stack) — это список для хранения данных, организованный по принципу LIFO (Last In First Out). Этот принцип означает, что новый элемент в стеке становится первым в списке. Стек похож на стакан, в который что-то насыпают, например горохом: внизу будет горох, который первый оказался в стакане, а сверху самый последний.
Очередь (Queue) — это список, организованный по принципу FIFO (First In First Out). Он как очередь в магазине — кто первый пришел, того раньше и обслужат.
Вот сам алгоритм:
- На вход поступает выражение в инфиксной форме. Проходим по нему слева направо;
- Если встречаем аргумент, то помещаем его в очередь;
- Если встречаем операцию, то есть три варианта:
- Если стек пустой, то помещаем операцию в стек;
- Если входящая операция имеет более высокий приоритет, чем операция в начале стека, то входящая операция помещается в стек;
- Если входящая операция имеет такой же приоритет, то операция в начале стека помещается в очередь и удаляется из стека; входящая операция помещается в стек;
- Если входящая операция имеет более низкий приоритет, то операция в начале стека помещается в очередь и входящая операция опять сравнивается с началом стека;
- Если конец выражения, то перемещаем оставшиеся операции из стека в очередь.
Прогоним алгоритм по выражению из предыдущих примеров — 64 – 15*4 + 20/4. Будем отслеживать текущее состояние с помощью operand stack (стек операций) и Queue (очередь)
1. Встретили аргумент 64. Помещаем в очередь. Текущее состояние:
2. Встретили оператор –. Стек пустой, значит помещаем его туда. Текущее состояние:
3. Встретили аргумент 15. Помещаем в очередь. Текущее состояние:
4. Встретили оператор *. Оператор имеет больший приоритет, чем вершина стека, значит помещаем его туда. Текущее состояние:
5. Встретили аргумент 15. Помещаем в очередь. Текущее состояние:
6. Встретили оператор +. Оператор имеет меньший, чем вершина стека, значит помещаем вершину стека в очередь. Следующий оператор имеет такой же приоритет — его тоже переносим. Входящий помещаем в стек. Текущее состояние:
7. Встретили аргумент 20. Помещаем в очередь. Текущее состояние:
8. Встретили оператор / . Оператор имеет больший приоритет, чем вершина стека, значит помещаем его туда. Текущее состояние:
9. Встретили аргумент 4. Помещаем в очередь.Текущее состояние:
10. Конец выражения. Помещаем стек в очередь. Конечное состояние:
В конце мы получили 64 15 4 * – 20 4 / +, что соответствует предыдущим примерам.
Размещайте свои приложения
в облаке Timeweb Cloud
477 ₽/мес
657 ₽/мес
Заключение
Мы разобрались, как в программировании работают с базовыми математическими операциями. Если вы планируете начать учиться программированию, на timeweb.cloud можно заказать недорогой облачный сервер для учебы и тестов.
А в своем официальном канале Timeweb Cloud собрали комьюнити из специалистов, которые говорят про IT-тренды, делятся полезными инструкциями и даже приглашают к себе работать.