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