Chapter 14Expression Trees“What’s twice eleven?” I said to Pooh.(“Twice what?” said Pooh to Me.)“I think it ought to be twenty-two.”“Just what I think myself,” said Pooh.— A. A. Milne, “Us Two,” Now We Are Six, 1927Objectives•To appreciate how you can use trees to interpret expressions in a programminglanguage.• To recognize the recursive structure of expressions and understand how you canrepresent that structure in C++.• To learn how to use C++ inheritance to structure a set of related classes.• To understand the process of parsing the text representation of an expression into itsinternal form.• To be able to write simple recursive functions that manipulate expression trees.Expression Trees – 492 –Chapter 13 focused on binary search trees because they provide a simple context forexplaining how trees work. Trees occur in many other programming contexts as well. Inparticular, trees often show up in the implementation of compilers because they are idealfor representing the hierarchical structure of a program. By exploring this topic in somedetail, you will learn quite a bit, not only about trees, but also about the compilationprocess itself. Understanding how compilers work removes some of the mysterysurrounding programming and makes it easier to understand the process as a whole.Unfortunately, designing a complete compiler is far too complex to serve as a usefulillustration. Typical commercial compilers require many person-years of programming,much of which is beyond the scope of this text. Even so, it is possible to give you a senseof how they work—and, in particular, of how trees fit into the process—by making thefollowing simplifications:• Having you build an interpreter instead of a compiler. As described in the section on“What is C++?” in Chapter 1, a compiler translates a program into machine-languageinstructions that the computer can then execute directly. Although it has much incommon with a compiler, an interpreter never actually translates the source code intomachine language but simply performs the operations necessary to achieve the effectof the compiled program. Interpreters are generally easier to write, but have thedisadvantage that interpreted programs tend to run much more slowly than theircompiled counterparts.• Focusing only on the problem of evaluating arithmetic expressions. A full-scalelanguage translator for a modern programming language—whether a compiler or aninterpreter—must be able to process control statements, function calls, typedefinitions, and many other language constructs. Most of the fundamental techniquesused in language translation, however, are illustrated in the seemingly simple task oftranslating arithmetic expressions. For the purpose of this chapter, arithmeticexpressions will be limited to constants and variables combined using the operators +,–, *, /, and = (assignment). As in C++, parentheses may be used to define the order ofoperations, which is otherwise determined by applying precedence rules.• Limiting the types used in expressions to integers. Modern programming languageslike C++ allow expressions to manipulate data of many different types. In this chapter,all data values are assumed to be of type int, which simplifies the structure of theinterpreter considerably.14.1 Overview of the interpreterThe goal of this chapter is to show you how to design a program that accepts arithmeticexpressions from the user and then displays the results of evaluating those expressions.The basic operation of the interpreter is therefore to execute the following stepsrepeatedly as part of a loop in the main program:1. Read in an expression from the user and translate it into an appropriate internal form.2. Evaluate the expression to produce an integer result.3. Print the result of the evaluation on the console.This iterated process is characteristic of interpreters and is called a read-eval-print loop.At this level of abstraction, the code for the read-eval-print interpreter is extremelysimple. Although the final version of the program will include a little more code than isshown here, the following main program captures the essence of the interpreter:Expression Trees – 493 –int main() { while (true) { expressionT exp = ReadExp(); int value = exp->eval(); cout << value << endl; delete exp; } return 0;}As you can see, the idealized structure of the main program is simply a loop that callsfunctions to accomplish each phase of the read-eval-print loop. In this formulation, thetask of reading an expression is indicated by a call to the function ReadExp, which will bereplaced in subsequent versions of the interpreter program with a somewhat longersequence of statements. Conceptually, ReadExp is responsible for reading an expressionfrom the user and converting it into its internal representation, which takes the form of anexpressionT value. The task of evaluating the expression falls to the eval method,which returns the integer you get if you apply all the operators in the expression in theappropriate order. The print phase of the read-eval-print loop is accomplished by asimple stream insertion to displays the result.At this point, you don’t yet have any detailed sense of what the expressionT type isor how it is represented. From the appearance of the -> operator in the lineint value = exp->eval();you can infer that expressionT is a pointer to some type that has a method called eval.The existence of an eval method, moreover, tells you that expressionT type points toobjects of some class, but the details are as yet undefined. That, of course, is how itshould be. As a client of the expression package, you are less concerned with howexpressions are implemented than you are with how to use them. For the moment, it isbest to think of expressionT as an abstract type for which you just happen to use pointersyntax to refer to its methods. The reasons underlying that decision will come in time.The operation of the ReadExp function consists of the three following steps:1. Input. The input phase consists of reading in a line of text from the user, which canbe accomplished with a simple call to the GetLine function from simpio.h.2. Lexical analysis. The lexical analysis phase consists of dividing the input line intoindividual units called tokens, each of which represents a single logical entity, such asan integer constant, an operator, or a variable