VPN без ограничения скорости для Android, iOS, Windows, macOSПодробнее

Порядок выполнения операций в программировании

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

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

Порядок Выполнения Операций В Программировании (1)

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

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

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

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-тренды, делятся полезными инструкциями и даже приглашают к себе работать.

Telegram
VK
Скопировать ссылку
MySQL: для чего нужна, как устроена, основные преимущества и недостатки
MySQL: для чего нужна, как устроена, основные преимущества и недостатки
Что такое SSL-сертификат и для чего он нужен
Что такое SSL-сертификат и для чего он нужен

Зарегистрируйтесь и начните пользоваться
сервисами Timeweb Cloud прямо сейчас

15 лет опыта
Сосредоточьтесь на своей работе: об остальном позаботимся мы
165 000 клиентов
Нам доверяют частные лица и компании, от небольших фирм до корпораций
Поддержка 24/7
100+ специалистов поддержки, готовых помочь в чате, тикете и по телефону