1: //simple_expression_tree.cpp
3: #include <iostream>
4: #include <climits>
5: using namespace std;
8: enum TagType
9: {
10: INT_ONLY,
11: SUB_NODE
12: };
13: //Note that only the very highest-level structure here has a name,
14: //and everything else except the enum type is "anonymous".
15: struct Node
16: {
17: TagType tag;
18: union
19: {
20: int intValue;
21: struct
22: {
23: Node* left;
24: char op;
25: Node* right;
26: };
27: };
28: };
31: int valueOf
32: (
33: Node node //in
34: )
35: {
36: if (node.tag == INT_ONLY)
37: return node.intValue;
38: else //It must now be the case that node.tag == SUB_NODE
39: {
40: if (node.op == '+')
41: return valueOf(*node.left) + valueOf(*node.right);
42: if (node.op == '*')
43: return valueOf(*node.left) * valueOf(*node.right);
44: cout << "\nError: Bad operator.";
45: cout << "\nPress Enter to continue ... "; cin.ignore(80, '\n');
46: return INT_MIN;
47: }
48: }
51: int main()
52: {
53: cout << "\nThis program illustrates the construction and evaluation "
54: "of a very simple\nexpression tree. The evaluation is performed "
55: "by a recursive function call.\nTry writing a recursive function "
56: "to display the expression as well.";
57: cout << "\nPress Enter to continue ... "; cin.ignore(80, '\n');
59: Node eTree;
61: //Put the arithmetic expression "123" into the tree.
62: //Then evaluate the expression and display its value.
63: eTree.tag = INT_ONLY;
64: eTree.intValue = 123;
65: cout << "\nValue of expression \"123\" from tree = "
66: << valueOf(eTree) << endl;
67: cout << "Press Enter to continue ... "; cin.ignore(80, '\n');
69: //Put the arithmetic expression "9+14" into the tree.
70: //Then evaluate the expression and display its value.
71: eTree.tag = SUB_NODE;
72: eTree.left = new Node;
73: eTree.left->tag = INT_ONLY;
74: eTree.left->intValue = 9;
75: eTree.op = '+';
76: eTree.right = new Node;
77: eTree.right->tag = INT_ONLY;
78: eTree.right->intValue = 14;
79: cout << "\nValue of expression \"9+14\" from tree = "
80: << valueOf(eTree) << endl;
81: cout << "Press Enter to continue ... "; cin.ignore(80, '\n');
83: //Put the arithmetic expression "5*3" into the tree.
84: //Then evaluate the expression and display its value.
85: eTree.tag = SUB_NODE;
86: eTree.left = new Node;
87: eTree.left->tag = INT_ONLY;
88: eTree.left->intValue = 5;
89: eTree.op = '*';
90: eTree.right = new Node;
91: eTree.right->tag = INT_ONLY;
92: eTree.right->intValue = 3;
93: cout << "\nValue of expression \"5*3\" from tree = "
94: << valueOf(eTree) << endl;
95: cout << "Press Enter to continue ... "; cin.ignore(80, '\n');
96: }