На уроках математики нас учили правильно вычислять значения выражений. Один из пунктов получения правильного ответа — корректно определить порядок выполнения операций. Ещё со школы мы знаем, что выражение в скобках выполняют в первую очередь, а деление и умножение приоритетнее сложения и вычитания.
Человек мыслит в этой математической парадигме. А вот компьютер не “мыслит” как человек. В этой статье мы взглянем под капот и узнаем, как в программировании работают с математическими операциями.
Форма записи или нотация — это правила составления выражений и их декомпозиции. Возьмем простое выражение:
10 + 15*4 + 6/2
Вот классический алгоритм вычисления значения этого выражения:
Здесь используется инфиксная форма записи — операции (сложение, вычитание, умножение и деление) записываются между аргументами (числами, переменными, функциями и другими математическими объектами). Инфиксная форма естественна для человека и используется людьми в повседневной жизни.
Но компьютеру сложнее разобрать такую форму записи. Поэтому обычно в компьютерах используется префиксная или постфиксная формы.
Префиксная нотация — это форма записи, в которой операторы располагают слева от аргументов.
Возьмем пример 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
cloud
Постфиксная нотация — это форма записи, в которой операторы располагаются справа от аргументов. Выражение 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 / +
, что соответствует предыдущим примерам.
Размещайте свои приложения<br>в облаке Timeweb Cloud
Мы разобрались, как в программировании работают с базовыми математическими операциями. Если вы планируете начать учиться программированию, на timeweb.cloud можно заказать недорогой облачный сервер для учебы и тестов.
А в своем официальном канале Timeweb Cloud собрали комьюнити из специалистов, которые говорят про IT-тренды, делятся полезными инструкциями и даже приглашают к себе работать.