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

Листинг 4.19. Абстрактный класс узла 
public abstract class Node // 
узел 
{ 
protected TypeVal typeVal; 
public abstract object DoOperation(); 
protected object value; 
public object Value 
{ 
get
{
return DoOperation(); 
} 
} 
} 
В этом классе введено защищенное поле тип значения typeVal, свой-
ство значение Value и абстрактный метод DoOperation(). 
У класса Node объявлено два потомка. Первый из них – класс кон-
стант: 
Листинг 4.20. Класс констант 
public class NodeConst : Node // 
узел CONST 
{ 
public NodeConst(TypeVal typeVal, object value) 
public override object DoOperation() 
{ 
11 / 23

---

104 
return value; 
} 
} 
Этот класс реализует свой конструктор NodeConst() и перекрывает 
метод DoOperation(). Второй потомок – класс бинарных операций: 
Листинг 4.21. Класс бинарных операций 
public class NodeOperation : Node 
{ 
public Operation typeOperation; 
public Node left; 
public Node right; 
public NodeOperation(Operation t,
Node left, Node right) 
public override object DoOperation() 
{ 
double 
a=Convert.ToDouble(left.DoOperation()); 
double 
b=Convert.ToDouble(right.DoOperation()); 
switch 
(typeOperation) 
{ 
case Operation.PLUS: 
value = a + b; 
return 
value; 
case Operation.MINUS:
value = a - b; 
return 
value; 
case Operation.MULT:
value = a * b; 
return 
value; 
case Operation.DIV:
value = a / b; 
return 
value; 
12 / 23

---

105 
default:
throw 
new 
NotImplementedException(); 
} 
} 
} 
В этом классе объявлено поле тип операции typeOperation, два по-
ля left и right для ссылок на левое и правое поддеревья, реализован свой 
конструктор и перекрыт метод DoOperation(), который рекурсивно обра-
щается к своим потомкам для вычисления своего значения.
После построения дерева для выражения запустить механизм вычисле-
ния выражения очень просто – надо обратиться к свойству Value корня де-
рева, а тот с помощью метода DoOperation() опросит всех своих потомков 
и вычислит у всех значения Value. 
Выражение обрабатывается следующим образом. Сканер выделяет 
очередную лексему. Лексема анализируется, и в зависимости от ее значения 
и от текущей структуры дерева к дереву добавляется необходимое количест-
во узлов. Дерево надстраивается, т. е. создается новая вершина, в двух слу-
чаях.
Во-первых, когда появляется новое слагаемое на первом уровне метода 
Expression
(). На рисунке 4.10 показано, как надстроилось дерево с рисун-
ка 4.9 при добавлении к предыдущему выражению слагаемого. Появился но-
вый корень, а старое дерево стало левым поддеревом нового. 
Рис.4.10. Надстроенное дерево 
13 / 23

---

106 
Второй случай надстройки дерева встречается тогда, когда в первом 
слагаемом выражения накапливаются множители. На рисунке 4.11а показано 
дерево, соответствующее одному множителю. Добавление множителя вызы-
вает появление нового корня, а старое дерево, как и в предыдущем случае, 
становится левым поддеревом нового. 
а 
б 
Рис. 4.11. Перестройки дерева разбора при добавлении множителя 
14 / 23

---

107 
Для обработки вложенных выражений необходимо сохранить указатель 
на узел, с которого начнется построение поддерева вложенного выражения, а 
затем, закончив обработку вложенности, вернуться к этому узлу. Для этого 
используются локальные переменные метода Expression(). Модуль 
Parser
, обрабатывающий выражение и строящий дерево разбора, приведен 
в листинге 4.22.