Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23

Листинг 4.27. Создание и обход дерева разбора арифметического вы-
ражения 
public abstract class Node // 
узел 
{ 
protected TypeVal typeVal; 
public abstract object DoOperation(); 
protected object value; 
public object Value { 
get { return DoOperation(); } 
} 
}; 
public class NodeConst : Node // 
узел CONST 
{ 
public NodeConst(TypeVal typeVal, object value) 
public override object DoOperation() 
1 / 23

---

117 
{ 
return value; 
} 
} 
public class NodeVal : Node 
{ 
protected int numVal; 
public NodeVal(int numVal) 
public override object DoOperation() 
{ return aVar[numVal].value; } 
} 
public class NodeOperation : Node 
{ 
protected Operation typeOperation; 
protected Node left; 
protected Node right; 
public NodeOperation(Operation t,
Node left, Node right) 
public override object DoOperation() 
} 
public class NodeFunc : Node 
{ 
protected int numFunc; 
protected Node arg; 
public NodeFunc(int numFunc, Node arg) 
public override object DoOperation() 
} 
На рисунке 4.18 представлена диаграмма этих классов. 
2 / 23

---

118 
Рис. 4.18. Диаграмма классов, предназначенная для описания узлов 
В этой структуре поле value предназначено для хранения значения 
узла, которое мы будем вычислять. 
Если тип узла — операция typeNode = OPERATION, то поле 
typeOperation
указывает на бинарную операцию, а поля left, right 
указывают на левый и правый операнды. 
Если тип узла — функция typeNode = FUNC, то поле numFunc пока-
зывает на номер функции, а поле arg является указателем на вершину дере-
ва, в котором сохраняется структура единственного параметра-значения 
функции. 
Если тип узла — константа typeNode = CONST, то поле предка 
value
содержит значение вещественной константы. 
Если тип узла — переменная typeNode = VAL, то поле numVal со-
держит номер переменной. 
Имена и значения переменных, находящихся в листьях дерева выраже-
ния будем хранить в динамическом массиве: 
public static Tvar[] aVar = new Tvar[2]; 
Тип TVar содержит два поля: имя переменной name и значение пере-
менной value: 
public struct Tvar 
{ 
3 / 23

---

119 
public string name; 
public double value; 
} 
При разборе строки могут возникать ошибки, связанные с неверной за-
писью выражения. В этом случае переменной Error будем присваивать не-
нулевой код ошибки и аварийно прерывать разбор строки вызовом оператора 
Exit
. Список сообщений, выдаваемых в случае возникновения ошибки, соб-
ран в массиве MsgEr: 
MsgEr: array[1..12] of string = ( 
'
Не найден оператор присваивания :=', 
'
Не найдено THEN', 
'
Ожидается выражение', 
'
Ожидается простое выражение', 
'
Ожидается слагаемое', 
'
Ожидается множитель', 
'
Неизвестная переменная', 
'
Нет скобки "("', 
'
Нет скобки ")"', 
'
Деление на 0', 
'Ln 
от отрицательного числа', 
'
Корень отрицательного числа' 
); 
В соответствии с усложненной постановкой задачи изменились и син-
таксические диаграммы. На рисунке 4.19 представлены синтаксические диа-
граммы добавленного выражения, простого выражения, слагаемого и изме-
ненного множителя.
Решение задачи состоит из двух этапов: на первом этапе рекурсивной 
функцией SetOperator() создается структура данных Operator; на вто-
ром этапе при заданном значении x эта структура используется для вычисле-
ния переменной y. 
4 / 23

---

120 
Выражение:
Простое выражение: 
Слагаемое: 
Множитель: 
Рис. 4.19. Синтаксические диаграммы выражения 
Первый этап состоит из следующих шагов. 
1. 
С помощью процедуры SetOperator() определить опера-
тор присваивания или if. 
2. 
С помощью процедуры PFormula() проанализировать опе-
рации отношения '<', '>', '==', '!=', '<=', '>='. 
3. 
С помощью процедуры Expression() проанализировать 
операции сложения и вычитания.
5 / 23

---

121 
4. 
С помощью процедуры Term() проанализировать операции 
умножения и сложения.
5. 
С помощью процедуры Factor() проанализировать кон-
станты, скобки, функции и переменные.
6. 
С помощью процедуры SetConst() проанализировать кон-
станту. 
Будем рассматривать строку, содержащую оператор, как стек, из нача-
ла которого поочередно извлекаются символы. Пробелы, естественно, игно-
рируются, и для изъятия пробелов используется функция Trim
():
s = s.Trim(); 
Для извлечения из строки n символов предназначена функция Pop() 
(листинг 4.28).