Выражения

Содержание

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

Числа
Операторы (знаки операций) +, -, /, *, ^, %, =
Скобки
Переменные

Оператор ^ означает возведение в степень, как в языке BASIC, а символ = обозначает оператор присваивания. Перечисленные элементы можно комбинировать в выражения согласно правилам алгебры, например:

10 - 8
(100 - 5) * 14 / 6
a + b - c
10^5
a = 10 - b

Пусть операторы имеют следующий приоритет:

высший     унарный + и -
           ^
           * / %
           + -
низший     =

Если выражение содержит операторы, имеющие одинаковый приоритет, то вычисления выполняются слева направо^[1].

В примерах данной главы все переменные имеют имена из одной буквы (другими словами, допускается 26 переменных, от А до Z). Имена переменных не чувствительны к регистру (заглавных или строчных букв). Например, а и А обозначают одну и ту же переменную. Каждое числовое значение имеет тип double, хотя не составляет труда написать процедуры для обработки значений других типов. Наконец, чтобы логика программ была простой и понятной, будет производиться лишь минимальный контроль за ошибками.

Если вы еще не задумывались о процессе синтаксического разбора выражений, попробуйте вычислить следующее выражение:

10 - 2 * 3

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

a = получить первый операнд
while(есть операнд){
  op = получить опретор
  b = получить второй операнд
  a = a op b
}

Эта процедура получает первый операнд, оператор и второй операнд, выполняет над ними первую операцию, а затем читает следующий оператор и операнд (если они есть) и выполняет следующую операцию, обозначенную полученным оператором и т.д.

Однако при данном подходе при вычислении выражения 10 — 2 * 3 в результате получается 24 (т.е. 8 * 3) вместо 4, поскольку описанная процедура не учитывает приоритет операторов. Нельзя просто выбирать операнды и операторы слева направо, поскольку правила алгебры гласят, что умножение производится прежде вычитания. Некоторые начинающие программисты думают, что эту проблему легко преодолеть. В очень редких случаях им это удается. Но проблема усложняется при добавлении скобок, возведении в степень, появлении переменных, вызове функций и т.п.

Несмотря на то, что существует несколько способов написания программы вычисления выражений, описываемый нами способ наиболее прост для кодирования человеком. Он также является самым распространенным. (При некоторых других методах создания синтаксических анализаторов в них применяются сложные таблицы, генерируемые другой компьютерной программой. Такие анализаторы иногда называются таблично управляемыми (table-driven).) Описанный здесь метод называется методом рекурсивного спуска, и, читая главу, вы, несомненно, догадаетесь, почему он так называется.

^[1]Впрочем, здесь есть одно часто встречающееся исключение — оператор возведения в степень. X**Y**Z означает, как правило, не (X**Y)**Z, a X**(Y**Z). (Оператор ** — обычное обозначение операции возведения в степень во многих языках программирования, наиболее распространенным из которых является Фортран.) Точно то же происходит и в алгебре: выражение а^{b^c} означает а^{(b^c)}, а не (а^b)^c = а^b^c.