Привет, друзья. Вычисление выражения — стандартная задача, ныне имеющая больше учебное значение. Хотя иногда приходится вычислять самому, например, для безопасности: порой в выражение можно запихать что-то такое, чего там быть не должно.
Но мы о другом: о самом подходе к вычислению. Ведь есть приоритет выражений: умножение раньше сложения, степень до умножения (в Вим девять приоритетов, и степени там нет при этом). И есть скобки. Вот как во всем этом алгоритмически разобраться?
Почему так много приоритетов? Ну, вот в Вим в порядке приоритетности: вызовы функций, обращения к регистрам и т.п.; индексация списков/словарей/строк; логическое NOT, унарный — и +; умножение, деление, взятие остатка (%); сложение, вычитание, конкатенация (.); сравнения; логическое AND; логическое OR; оператор ветвления ?:. В Перл есть еще степень и логика двух уровней: есть &&, а есть and, и разница в том, что or имеет самый низкий приоритет вообще, выполняется после даже присваивания, а его аналог || идет раньше, например, ?: или ..
Для начала надо выражение строго определить. Давайте для простоты оставим только сложение и умножение: принцип тот же, а проще. Итак, выражение — это сумма выражений, то есть Е₁+Е₂.
Изящно, но не хватает базы. Добавим еще вариант "выражение — это множитель".
Теперь надо понять, что такое множитель. Это произведение множителей, то есть М₁*М₂, или константа, или выражение в скобках.
Если вы вдумаетесь, то увидите, что 42+9, 6*7, 42, (42), (((666))) всё выражения. И теперь их несложно вычислять: просто по определению. На каждом шаге выражение становится короче, так что рано или поздно доберемся до констант, а там понятно.
Давайте посмотрим, как алгоритм разберет выражение
1+2*(3+4*(5*6+7)).
Найдя знак +, он представит выражение как сумму 1 и 2*(3+4*(5*6+7)). С первым проблем нет: это не сумма, значит, это множитель. И не просто множитель, а константа. Вычислить его легко.
Второе слагаемое — это тоже множитель, состоящий из произведения 2 и (3+4*(5*6+7)) — выражения в скобках. Там сумма, числа 3 и множителя 4*(5*6+7). Он разлагается в произведение 4 и (5*6+7), выражения в скобках. Там стоит сумма множителя 5*6 и числа 7. Произведение двух констант 5*6 считается. Всё.
Как видим, у нас получилось дерево: в листьях константы, дуги — операции, в узлах промежуточные результаты:
Вот ещё пример:
(1*2+3*4)*(5*6+7*8)+9
Это сумма двух слагаемых, одно из которых есть произведение двух множителей, которые выражения в скобках, а именно суммы двух произведений каждое.
По дереву можно не только легко вычислить выражение, но и сделать это эффективно. Например, параллельно. В первом примере параллельности нет, но есть во втором выражении: обе скобки можно вычислять параллельно и независимо друг от друга.
Как обходить дерево — интересный вопрос, достойный отдельной заметки.
Привычная нам форма записи называется инфиксной, потому что операция ставится между операндами: "три плюс пять". Она привычна с детства и, наверное, даже удобна, если привыкнуть к приоритету операций. Но есть и другие.
Например, постфиксная. В ней операция пишется после операндов. Выражение в такой записи очень легко вычислять, если уметь пользоваться стеком.
Стек — это структура данных, в которую можно помещать данные и извлекать оттуда через один и тот же вход. Как стопка тарелок или, скажем, одежда: девушка сначала надевает лифчик, потом блузочку, затем пиджачок и наконец шубку — а снимает в обратном порядке.
Алгоритм вычисления выражения в постфиксной нотации поступает просто: увидев число, суёт его в стек, а увидев знак операции — вытаскивает из стека сколько нужно операндов, совершает операцию и кладет результат в стек.
Не нужен приоритет, не нужны скобки. Всё просто и прозрачно. Пример: выражение выше 1+2*(3+4*(5*6+7)):
1 2 3 4 5 6 * 7 + * + * +
Выполняем. Кладем в стек 1, 2, 3, 4, 5, 6. Вытаскиваем 6 и 5 и умножаем, результат кладем обратно. В стеке 1, 2, 3, 4, 30. кладем в стек 7. Вытаскиваем его и 30, складываем, кладем результат обратно. В стеке 1, 2, 3, 4, 37. Вытаскиваем два верхних, перемножаем. И так далее.
Я слышал о двух языках программирования, в которых такая нотация. Это Forth (язык для своего времени интересный, но ныне широко не употребляется, хотя в 2010 еще кое-где в нишах использовался) и PostScript. Последний вообще разработан так, чтобы легко выполняться, но легкость чтения и программирования не предполагается. Оно и понятно, программы на постскрипте пишут программы и выполняют программы. Постскрипт можно освоить и использовать для рисования. На самом деле, это Тьюринг-полный язык, с циклами, процедурами и условиями, на нем можно вообще все. Я когда-то сделал на Перле рисовалку, которая чертит графики, генерируя соответствующий код в PostScript.
Постфиксная нотация называется еще обратной польской. Словами это как бы "взять пять и шесть и сложить".
Отсутствие скобок уменьшает риск ошибиться в скобках, зато легче ошибиться в самом выражении. Такая запись неверной быть вообще не может; единственная возможная ошибка — это если стек опустеет и операции не хватит операндов (1 +).
Префиксная — это то же самое, только операция пишется до операндов: "сложить пять и шесть". Вычислять ее несложно, но можно вообще не утруждаться, вычисляя ее с конца как постфиксную.
Если операции записаны как функции, то add(5,6) — Это и есть префиксный стиль. Так устроены многие функциональные языки, и в них много скобок, но скобки нужны не для приоритета. Вместо стека будут вызовы функций. Наш пример, если имена функций add и mul, будет выглядеть так:
add(1, mul(2, add(3,mul(4,add(mul(5,6),7))))).
В общем-то, вызов функций реализован через стек, так что это действительно то же самое, что и постфиксная запись, по сути.
Операции у нас были бинарные: брали два операнда. Справа и слева, или два из стека, но два. Есть унарные, классический пример — это унарный минус, умножающий число на -1, или факториал, или натуральный логарифм.
Есть тернарные операции. В программировании часто встречается сишный оператор (?:), который работает так:
a>b ? 42 : 666
Если условие a>b истинно, то вычисляется второй операнд, а если ложно, то второй. И это именно оператор, как плюс или минус, то есть можно так вычислить 42+|x|:
42 + x>0 ? x : -x
У операций есть такие свойства, как ассоциативность, коммутативность и приоритет. Приоритет мы уже обсудили, и в постфиксной нотации он роли не играет. За него будет порядок операндов и операций, что и хорошо, и плохо: порядок жестко задан.
Коммутативность (для бинарных операций) — это возможность менять местами порядок операндов. Сложение коммутативно, вычитание нет, умножение чисел — да, матриц — нет. Об этом надо помнить, потому что, например, (A+B)² = A² + B² + AB + BA для матриц не упрощается до ...+2АВ.
Вот поэтому-то плохая идея конкатенировать строки оператором +.
В постфиксной нотации коммутативность тоже важна: a b - и b a - суть разные вещи. Обычно предусмотрены команды для работы со стеком, например, для обмена первых двух чисел в нем. Это позволяет "выкрутиться", не переписывая все выражение.
Ассоциативность — это независимость от порядка выполнения операций. Произвол расстановки скобок, если в инфиксной нотации:
a+b+c = (a+b)+c = a+(b+c)
В постфиксной это
a b c + + = a b + c +
Векторное произведение векторов не ассоциативно: (a✕b)✕b не равно a✕(b✕b), если векторы ненулевые. Поэтому умножением его называть вообще не слишком правильно. Правда, у векторов и нет нормального группового умножения. Еще пример: коммутатор, AB-BA, который тоже часто встречается вместо умножения.
Вот оператор ?: может быть правоассоциативным, а может быть левоассоциативным. Вот например:
a < 10 ? 1 : a < 100 ? 2 : a < 1000 ? 3 : -1
Переводим на человечий: если а меньше 10, то вернем 1 (однозначное число), а если нет, то: если меньше 100, то вернем 2, а если нет, то: если меньше 1000, то вернем 3, а если нет, то вернем -1. При этом мы трактуем оператор как правоассоциативный:
a < 10 ? 1 : (a < 100 ? 2 : (a < 1000 ? 3 : -1))
Но говорят, что в PHP он левоассоциативен, по непонятной причине. Работает так:
(((a < 10) ? 1 : a < 100) ? 2 : a < 1000) ? 3 : -1
И для а=42 он вернет 3. И вообще, ничего кроме 3 и -1 он не возвращает никогда, и насчет -1 я сомневаюсь. Конечно, в PHP переменные с $, но это сейчас не так важно.