Программирование. Принципы и практика использования C++ Исправленное издание

    default: // нет другого оператора: выводим результат

      cout << "Результат: " << lval << '\n';

      keep_window_open;

      return 0;

    }

  }

  error("неверное выражение");

}

Это неплохо, но попытайтесь вычислить выражение 1+2*3, и вы увидите, что результат равен 9, а не 7, как утверждают учителя математики. Аналогично, 1–2*3 равно –3, а не –5, как мы думали. Мы выполняем операции в неправильном порядке: 1+2*3 вычисляется как (1+2)*3, а не 1+(2*3), как обычно. Аналогично, 1–2*3 вычисляется как (1–2)*3, а не 1–(2*3), как обычно. Лентяи! Мы можем считать правило, согласно которому умножение выполняется раньше, чем сложение, устаревшим, но не стоит отменять многовековые правила просто для того, чтобы упростить себе программирование. 

6.3.2. Лексемы

Теперь (каким-то образом) мы должны заранее узнать, содержит ли строка символ * (или /). Если да, то мы должны (каким-то образом) скорректировать порядок выполнения вычислений. К сожалению, пытаясь заглянуть вперед, мы сразу же наталкиваемся на многочисленные препятствия.

1. Выражение не обязательно занимает только одну строку. Рассмотрим пример.

1

+

2

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

2. Как обнаружить символ * (или /) среди цифр и символов +, –, ( и ) в нескольких строках ввода?

3. Как запомнить, в каком месте стоит символ *?

4. Как вычислить выражение, которое не выполняется слева направо (как 1+2*3). Если бы мы были безоглядными оптимистами, то сначала решили бы задачи 1–3, отложив задачу 4 на более позднее время. Кроме того, нам понадобится помощь. Кто-то ведь должен знать, как считать такие вещи, как числа и операторы, из входного потока и сохранить их так, чтобы с ними было удобно работать. Общепринятый и самый полезный ответ на эти вопросы таков: разложите выражение на лексемы, т.е. сначала считайте символы, а затем объедините их в лексемы (tokens). В этом случае после ввода символов

45+11.5/7

программа должна создать список лексем

45

+

11.5

/

7 

  Лексема (token) — это последовательность символов, выражающих нечто, что мы считаем отдельной единицей, например число или оператор. Именно так компилятор языка С++ работает с исходным кодом программы. На самом деле разложение на лексемы часто в том или ином виде применяется при анализе текста. Анализируя примеры выражений на языке С++, можно выделить три вида лексем.

• Литералы с плавающей точкой, определенные в языке C++, например 3.14, 0.274e2 и 42.

• Операторы, например +, –, *, /, %.

• Скобки (, ).

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

Как представить такие лексемы в нашей программе? Можно попытаться найти начало (и конец) лексемы, но это может привести к путанице (особенно, если позволить выражениям занимать несколько строк). Кроме того, если хранить числа в виде строки символов, то позднее следует идентифицировать это число по его цифрам; например, если мы видим строку 42 и где-то храним символы 4 и 2, то позднее должны выяснить, что эта строка представляет число 42 (т.е. 4*10+2). Общепринятое решение этой задачи — хранить каждую лексему в виде пары (вид, значение).

Вид идентифицирует лексему как число, оператор или скобку. Для чисел (в нашем примере — только для чисел) в качестве значения используется само число.

Итак, как же выразить идею о паре (вид, значение) в программе? Для этого определим тип Token, представляющий лексемы. Почему? Вспомните, почему мы вообще используем типы: они хранят данные, которые нам нужны, и предоставляют возможность выполнять полезные операции над этими данными. Например, тип int позволяет хранить целые числа и выполнять операции сложения, вычитания, умножения и вычисления остатка, в то время как тип string позволяет хранить последовательности символов и выполнять конкатенацию и доступ к символу по индексу. В языке С++ и его стандартной библиотеке определено много типов, например char, int, double, string, vector и ostream, но не тип Token. На самом деле существует огромное количество типов — тысячи и сотни тысяч, — которые мы хотели бы иметь, но которых нет в языке и в стандартной библиотеке.