Теперь (каким-то образом) мы должны заранее узнать, содержит ли строка символ
*
(или
/
). Если да, то мы должны (каким-то образом) скорректировать порядок выполнения вычислений. К сожалению, пытаясь заглянуть вперед, мы сразу же наталкиваемся на многочисленные препятствия.
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
. На самом деле существует огромное количество типов — тысячи и сотни тысяч, — которые мы хотели бы иметь, но которых нет в языке и в стандартной библиотеке.
Среди наших любимых типов, которых нет в библиотеке, — классы
Matrix
(см. главу 24),
Date
(см. главу 9) и целые числа с бесконечной точностью (поищите в веб класс
Bignum
). Если вы еще раз поразмыслите над этим, то поймете, что язык не может поддерживать десятки тысяч типов: кто их определит, кто их реализует, как их найти и какое толстое руководство по использованию языка при этом получится? Как и большинство современных языков программирования, язык С++ решает эту проблему, позволяя программисту при необходимости определять свои собственные типы (типы, определенные пользователем).
6.3.3. Реализация лексем
Как должна выглядеть лексема в нашей программе? Иначе говоря, как должен выглядеть тип
Token
? Класс
Token
должен предусматривать выполнение операторов, например
+
и
–
, а также представлять числа, такие как
42
и
3.14
. В самой простой реализации нужно придумать, как задать вид лексемы и как хранить числа.
Существует много способов реализации этой идеи в программе на языке С++. Вот ее простейший вариант:
class Token { // очень простой тип, определенный пользователем
public:
char kind;
double value;
};
Класс
Token
— это тип (такой же, как
int
или
char
), поэтому его можно использовать для определения переменных и хранения значений. Он состоит из двух частей (членов):
kind
и
value
. Ключевое слово
class
означает “тип, определенный пользователем”; это значит, что он содержит члены (хотя в принципе может их и не содержать). Первый член,
kind
, имеет тип
char
и представляет собой символ. С его помощью удобно хранить символы
'+'
и
'*'
, чтобы представить операции
*
и
+
. Рассмотрим пример использования этого типа.
Token t; // t — объект класса Token
t.kind = '+'; // t представляет операцию +
Token t2; // t2 — другой объект класса Token
t2.kind = '8'; // цифра 8 означает, что "вид" является числом
t2.value = 3.14;
Для доступа к члену класса используется обозначение имя_объекта.имя_члена. Выражение