На уроках математики нас учили правильно вычислять значения выражений. Один из пунктов получения правильного ответа — корректно определить порядок выполнения операций. Ещё со школы мы знаем, что выражение в скобках выполняют в первую очередь, а деление и умножение приоритетнее сложения и вычитания. 

Человек мыслит в этой математической парадигме. А вот компьютер не “мыслит” как человек. В этой статье мы взглянем под капот и узнаем, как в программировании работают с математическими операциями.

Инфиксная, префиксная и постфиксная формы

Инфиксная форма 

Форма записи или нотация — это правила составления выражений и их декомпозиции. Возьмем простое выражение:

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 / +, что соответствует предыдущим примерам.

Заключение

Мы разобрались, как в программировании работают с базовыми математическими операциями. Если вы планируете начать учиться программированию, на timeweb.cloud можно заказать недорогой облачный сервер для учебы и тестов. 

А в своем официальном канале Timeweb Cloud собрали комьюнити из специалистов, которые говорят про IT-тренды, делятся полезными инструкциями и даже приглашают к себе работать.