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

Как вы знаете, программисты умеют говорить компьютерам, что им делать: они пишут код, запускают его, и компьютер выполняет заданные ему команды.

Хотя у программистов есть над компьютерами некая власть, в коде все еще остается много волшебства, которое люди часто упускают из виду. Особенно это касается языков высокого уровня с предварительно встроенными функциями. Конечно же, нет никакой веской причины изобретать велосипед или пытаться переписать эти же полезные функции самостоятельно, но заглянуть под капот и посмотреть, как все работает внутри, все равно интересно.

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

Предположим, вы хотите вычислить это выражение:

5 + 10 * 3

Согласно математическому порядку операций, сначала следует умножить 10 на 3, а затем добавить 5 к полученному произведению. Но как объяснить это компьютеру? В этом мануале мы расскажем, как это делается.

Есть несколько способов обработки такого уравнения, среди них встречаются и довольно сложные.

Согласно нашему методу, сначала нужно преобразовать данное уравнение в правильный формат. Когда выражение примет машиночитаемую форму, мы сможем передать его анализирующему алгоритму, который фактически вычислит его.

Итак, сначала вы научитесь преобразовывать ваши данные в правильный формат, а затем познакомитесь с самим алгоритмом, который анализирует выражения. Для простоты в этом мануале мы будем работать только с четырьмя операторами – сложения, вычитания, умножения и деления.

Преобразовании инфиксной нотации в постфиксную

Скорее всего, вы уже знакомы с инфиксной нотацией (даже если еще не знаете об этом). Это выражение:

5 + 10 * 3

записано именно в ней. При инфиксной нотации операторы стоят между операндами, к которым они относятся.

Что такое постфиксная нотация?

Ранее мы говорили, что нам нужно преобразовать наше выражение в понятный компьютеру формат. Этот формат называется постфиксной нотацией.

В постфиксной нотации все операторы стоят не между операндами, к которым они относятся, а после них.

Это очень важно, и вот почему. Когда машина читает выражения в этом формате, она сначала видит операнды, а уже затем операторы – то есть машине не придется возвращаться назад к предыдущему оператору.

Следовательно, наш пример 5 + 10 * 3 в постфиксной нотации будет выглядеть так:

5 10 3 * +

Этот результат может выглядеть необычно, но он выводится по четкому методу.

Человекочитаемый способ преобразования инфикса в постфикс

Возьмите выражения в скобки в порядке приоритета:

(5 + (10 * 3))

Внутри этих скобок переместите все операторы вправо:

(5 ( 10 3 *)+)

А теперь просто удалите скобки, и вы получите выражение в постфиксной нотации:

5 10 3 * +

Обратите внимание: операторы не всегда стоят в самом конце выражения в постфиксной нотации. Вот пример, который показывает это:

8 * 4 + 2
((8 * 4) + 2)
((8 4 *) 2 +)
8 4 * 2 +

Опять же, это еще не наилучший вариант для компьютера. Если бы эту строку читала машина, она все еще не знала бы, где поставить скобки. К счастью, для преобразования инфикса в постфикс существует удобный алгоритм.

Алгоритм сортировочной станции

Алгоритм сортировочной станции был разработан Эдсгером Дейкстрой как метод преобразования инфиксной нотации в постфиксную.

Давайте быстро рассмотрим две структуры данных, которые мы будем использовать в мануале дальше: это будет стек (stack) и очередь (queue). Для хранения этих наборов данных можно использовать массив. Основное отличие заключается в порядке добавления и удаления данных.

Когда мы добавляем данные в очередь, они помещаются в конец. Просто представьте, что вы стоите в обычной очереди на концерт: здесь каждый человек является элементом. Когда вы подходите к очереди, вы автоматически становитесь в ее конец. При этом в зал сначала проходят люди, которые стоят в начале очереди, поскольку они пробыли там дольше. Этот механизм можно запомнить с помощью английской аббревиатуры FIFO: first in, first out (что значит «первым пришёл-первым вышел»).

При добавлении нового элемента в стек он будет помещаться в начале, а не в конце. Элементы удаляются из стека, начиная с верхнего (первого). Поскольку новые элементы всегда помещаются в начало стека, эти новые элементы всегда будут извлекаться первыми, если вы захотите что-то удалить. Этот механизм можно запомнить с помощью английской аббревиатуры LIFO: last in, first out (что значит «последним пришёл-первым вышел»).

Предположим, у нас есть один временный стек для хранения операторов (назовем его «стеком операторов») и одна очередь, которая будет содержать конечный результат.

Как работает алгоритм сортировочной станции

Алгоритм сортировочной станции состоит из 4 основных этапов:

  1. Алгоритм анализирует выражение слева направо.
  2. Если он встречает операнд, он немедленно помещает его в очередь результатов.
  3. Если алгоритм встречает оператор, есть несколько вариантов:
    1. Если стек операторов пуст, алгоритм помещает входящий оператор в стек.
    2. Если входящий оператор имеет более высокий приоритет, чем тот оператор, что в настоящее время находится на вершине стека, входящий оператор помещается на вершину стека.
    3. Если входящий оператор имеет такой же приоритет, верхний оператор извлекается из стека и выводится в очередь, а входящий оператор помещается в стек.
    4. Если приоритет входящего оператора ниже, верхний оператор извлекается из стека и выводится в очередь, после чего входящий оператор сравнивается с новой вершиной стека.
  4. Когда все выражение будет проанализировано, все оставшиеся токены перекладываются из стека операторов.

Вычисление выражений с помощью алгоритма сортировочной станции

Чтобы лучше разобраться в работе алгоритма, давайте конвертируем из инфикса в постфикс это выражение:

5 + 10 * 3

Создайте два массива: один для результатов, а второй – для стека операторов.

expression = 5 + 10 * 3
output = []
operator stack = []

Выражение анализируется слева направо. Итак, в самом начале у нас идет 5. Поскольку это операнд, мы можем сразу поместить его в массив выходной очереди.

expression = + 10 * 3
output = [5]
operator stack = []

Далее идет оператор +. Стек операторов пуст, поэтому мы можем просто вставить его туда.

expression = 10 * 3
output = [5]
operator stack = [+]

Далее идет операнд 10, который помещается в выходную очередь.

expression = * 3
output = [5, 10]
operator stack = [+]

Теперь мы встречаем другой оператор, *. Поскольку стек операторов уже не пуст, мы должны сравнить этот входящий оператор с текущей вершиной стека и оценить, какой из них имеет более высокий приоритет.

Как вы знаете, текущей вершиной стека является оператор +. Сравнив их, мы увидим, что умножение имеет более высокий приоритет, чем сложение.

Значит, мы можем просто поместить оператор * на вершину стека, и тогда у нас получится:

expression = 3
output = [5, 10]
operator stack = [*, +]

Теперь мы достигли конца выражения, где видим операнд 3. Поскольку это не оператор, мы можем просто поместить его в выходную очередь.

expression is now empty
output = [5, 10, 3]
operator stack = [*, +]

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

output = [5, 10, 3, *, +]

Вот и все! Как видите, наш результат соответствует описанному выше методу с применением скобок, но этот способ намного проще для компьютера.

Правила приоритета

Возможно, выполняя предыдущий пример, вы заметили один момент, когда для принятия решения вместо алгоритма мы использовали собственные знания: это случилось тогда, когда нам нужно было определить, какой оператор имел более высокий приоритет.

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

Для этого нужно создать объект, который будет ранжировать каждого оператора. Операторам умножения и деления мы присвоим ранг 2, а операторам сложения и вычитания — 1.

Во время кодирования мы просто сравним два оператора по их рангу. Числа 1 и 2 мы выбрали здесь произвольно, поэтому не будем на этом останавливаться. Просто помните, что приоритет умножения выше, чем сложения, поэтому его ранг будет тоже выше.

const precedence = { "*":2, "/":2, "+":1, "-":1 };

Вычисление выражения в постфиксной нотации

Итак, у вас есть выражение в постфиксной нотации. Сейчас его можно вычислить. Для этого существует специальный алгоритм.

  1. Для начала берется пустой стек.
  2. Анализируется первый токен в выражении.
  3. Если это операнд, он помещается в стек.
  4. Если это оператор, соответствующее количество операндов перекладывается из стека во временные переменные (например, умножение – это бинарный оператор, поэтому, если при анализе вы встречаете оператор умножения, вы должны переместить два операнда).
  5. Для вычисления этого выражения используется текущий оператор и два операнда, которые были перемещены.
  6. Этот результат помещается на вершину стека.

Этапы 2-6 повторяются, пока выражение не закончится.

В нашем примере мы работаем только с бинарными операторами, поэтому мы всегда можем переложить два операнда, когда видим оператор.

Но помните, что встречаются и унарные операторы (например, !).

Давайте рассмотрим работу алгоритма на примере полученного нами выражения в постфиксной нотации.

5 10 3 * +

Для начала все операнды перекладываются в стек по принципу «первый зашел – последний вышел»:

expression = [5, 10, 3, *, +]
- push 5
- push 10
- push 3
stack = [3, 10, 5]

Встретив первый оператор, *, мы должны взять из стека два операнда:

- pop 3
- pop 10

Итак, мы извлекли два операнда, 3 и 10, и теперь можем соединить их с оператором *, в результате чего получится 10 * 3.

expression = [+]
stack = [5]
tempOperand1 = 3
tempOperand2 = 10
tempOperator = *
eval(tempOperand1 + tempOperator + tempOperand2) // 3 * 10

Это выражение вычисляется и дает результат 30, после чего возвращается в стек. Теперь у нас есть вот что:

expression = [+]
stack = [30, 5]

Мы снова анализируем выражение и сразу встречаем оператор. Нам нужно снова извлечь два операнда из стека.

expression = []
stack = []
tempOperand1 = 30
tempOperand2 = 5
tempOperator = +
eval(tempOperand1 + tempOperator + tempOperand2) // 30 + 5

Мы извлекаем 30 и 5, а затем помещаем между ними оператор +, в результате получаем выражение 5 + 30, что дает 35. Этот результат помещается в стек.

Возвращаясь к исходному выражению, мы увидим, что оно пустое:

expression = []
stack = [35]

Это означает, что либо выражение закончено, либо исходное выражение было искажено.

Давайте посмотрим на наш стек. Сейчас в нем есть только одно значение, так что это означает, что выражение проанализировано полностью, а 35 – это конечный результат нашего исходного выражения, 5 + 10 * 3.

Префиксная нотация

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

Давайте вернемся к первому методу, в котором мы использовали скобки и перемещали операторы. Чтобы преобразовать выражение в префиксную нотацию, нужно переместить операторы вправо от операндов, в начало (а не влево, в конец, как в постфиксной нотации). Сделав это, вы можете убрать скобки и получите выражение в префиксной нотации.

5 + 10 * 3
(5 + (10 * 3))
(+ 5 (* 10 3))
+ 5 * 10 3

Если вы хотите проверить свои знания, попробуйте самостоятельно вычислить это выражение с помощью алгоритма сортировочной станции.

Заключение

В данном мануале вы познакомились с алгоритмом сортировочной станции и порядком вычисления математических выражений, а также узнали об инфиксной, префиксной и постфиксной нотации.