MPW Calculator
Volume Number: 9
Issue Number: 1
Column Tag: Jörg's Folder
MPW Calculator Tool in C++ 
An MPW tool written in bare bones C++ - not with MacApp.
By Jörg Langowski, MacTech Magazine Regular Contributing Author
Note: Source code files accompanying this article are located on MacTech CD-ROMor source code disks.
After a long break, you’ll find another C++ example in my column. Not with
MacApp - we’re going back to the basics here and show a simple ‘bare C++’ program
that executes as an MPW tool, or in the Simple Input/Output Window environment
(SIOW) provided by Apple.
I came across this example reading a book on C++, “Programming in C++”, by
Stephen Dewhurst and Kathy Stark (1989, Prentice Hall). I very much recommend
this book for those of you who want to get the basic notions of C++ and an idea of its
‘programming flavor’. It may be not as comprehensive as the “C++ programming
language” by Stroustrup (Addison-Wesley), or as the manuals that come with Apple’s
C++ compiler; but it contains a lot of examples and exercises.
One classic exercise in computer science is to write a parser for algebraic
expressions, that is, a program that takes an input string like
(3 + 5) * (-4 + (2 - 9))
and calculates the result of this expression. In fact, what you do to compute that
expression is to convert it into an internal representation, and then evaluate that
representation.
You can represent the expression given above by a linked list:
where each node of the list either contains an operator or a number. Once the
arithmetic expression is given in list form, evaluating it is easy and can be done in a
straightforward, object oriented way. Suppose you define a class node (also in listing):
class node {
protected:
node() {}
public:
virtual ~node() {}
virtual int set (int)
{ cout << "Error: node::set(int) undefined" << eoln;
return 0;}
virtual int eval()
{ cout << "Error: node::eval() undefined" << eoln;
return 0;}
};
where the constructor and destructor do nothing at the moment; they will have to be
overridden by the derived node classes. There are two more virtual methods: eval(),
which returns the value of the node, and set(), which can ‘set something’ in the node if
defined in a subclass. For the base class, the methods just print error messages and
return zero. These methods will be overridden, and they are virtual because we want
their behavior to be determined at run time. That is, if we define a pointer mynode
*node and assign it an object of a subclass of node, the actual eval() or set() methods
used will be the ones corresponding to the subclass of the object that the pointer
contains.
We now define two types of subclasses of node: dyadic operators and other stuff.
All dyadic operators will be derived from the subclass :
class dyad : public node {
protected:
node *left, *right;
dyad(node *l, node *r) {left=l; right=r;}
~dyad() {delete left; delete right;}
};
dyad only defines the two nodes that the operator connects: the constructor
assigns these two nodes to two instance variables, and the destructor deletes them
again. The classes derived from dyad define the four arithmetic operations, and the
assignment (see listing). For example, addition is defined as:
class plus : public dyad {
public:
plus(node *l, node *r) : dyad(l,r) {}
int eval() { return left->eval() + right->eval();}
};
where the constructor just calls the superclass constructor, and
eval() returns the value of the sum of the values of the left and right hand side of
the plus operation.
For the ‘expression tree’ shown above, you need one more class: numbers, which
are ‘end nodes’ of the list. Thus, they do not contain pointers to other nodes, but an
integer value in an instance variable. Their constructor assigns the value, and their
eval() method simply returns it:
class inumber : public node {
int value;
public:
inumber(int v) {value = v;}
int eval() {return value;}
};
Finally, the unary minus operator (uminus in the listing) will return the
negative value of the node that it points to.
The listing contains two more node classes: variables (id) and the assignment
operator (equals), Variables contain a pointer to the head of a symbol table, and a
pointer to the entry of this variable into the symbol table. The symbol table is a linked
list of entries, and the pointer to its head is a static class variable. This means that,
unlike instance variables, the pointer is not created again for every object of the class,
but only one copy exists. Thus, all objects of this class reference the same symbol
table, which is just what you want.
Assume we create a new node for a variable with its name given by the *char
pointer nm. The constructor then first looks up the name in the symbol table (see
listing, method look); if it is already there, it will put a pointer to the symbol table
entry in the instance variable ent of the node. Otherwise, it will add a new entry to the
symbol table, put its pointer into ent, make the new entry the head of the list, and
change the (static) pointer so that it references the new head. All other variable
objects will now have an updated reference to the symbol table.
A variable is assigned a value by the assignment operation equals. When an equals
node is created, its right and left hand sides are set just as for the arithmetic
operations; when its eval() method is called, the variable on the left hand side is set to
the result of the right hand side. No check is done whether the left hand side is really a
node of class id; but only those nodes contain a set method. The assignment operation
also returns a value (just as in C), the right hand side of the statement.
So now we have defined a syntax tree for simple arithmetic expressions with
assignment of variables. If, lets say, root is the pointer to the root of this tree (the
times symbol in the drawing), and we call root->eval(), the result returned should be
the value of the expression, in our case (3 + 5) * (-4 + (2 - 9)) = -88. With the
class definitions given so far, this should work. But how do we set up the syntax tree in
the first place? We need a routine, an expression parser, that takes the string
expression and constructs the tree from it.
In order to write the parser, we first need to formalize the syntax of our simple
arithmetic expressions. Such a formal description would for instance look like this:
() | - |
We then define three parser routines that return an object of class node: e(),
t(), and f(), returning, respectively, a pointer to an expression, a term, and a factor.
Each of these routines makes repeated calls to another routine scan(), which gets the
next token from the input stream. A token is a separate syntactic element, such as an
open or close bracket, an arithmetic operator, a number or an identifier. scan()
returns a character value, either the ascii value of a symbol if the token consists of
one symbol, or a special value > 127. For the special values ID and INT, additional
information can be found in a static char variable; this string will be used for the
value of a number or the name of a variable. Other possible values are BAD (the
scanner found something it couldn’t interpret), or EOLN (end of line found).
The first of the three parser routines, e(), is called from the main program (see
listing for main()). On entry, one token has been read from the input stream; then e()
tries to parse the input into a valid arithmetic expression and assign a pointer to its
syntax tree to root. It does so by calling t() (see listing), which makes a term out of
one or several factors by calling f(), just like e() makes the expression out of one or
several term. When e() encounters a plus or minus sign after a term, is makes a new
plus resp. minus node which connects the first term with the next one. Same for t();
here eventually a times or divide node is made, which connects two factors. f(),
finally, will look for a number or identifier token and return a pointer to the
corresponding node; or it might find an open bracket or a minus sign, after which a
new expression or a factor have to follow. When all these recursive calls have been
evaluated and no syntax errors have been found, the top-level e() returns the
expression’s syntax tree.
In order to get the value of the expression, all we have to do then is call
root->eval(), and the syntax tree will be evaluated as described above.
As long as no syntax errors are found, the main program loops continuously and
asks for new expressions; the names and values of identifiers are remembered from
one evaluation to the next, so you can play around with stored values a little.
As you may imagine, it is not too difficult to add on to this extremely simple
calculator program e.g. to implement exponentiation or to include functions like
exp(), log() etc. The constructed syntax tree could also serve in a bigger program as
an internal representation of a function that the user has typed in and that has to be
evaluated a lot of times (and computed fast). One could even imagine to generate real
machine code out of the syntax tree, which makes this program some kind of a
rudimentary compiler. We’ll add to the example during the next columns.
On the source code disk, I have compiled two versions of the program, one as an
MPW tool, and the other one using the Simple Input/Output Window mechanism.
Actually, the only thing that has to be changed is the linking. The MPW sequence to
create the two versions of the program look like the following:
cplus calc.cp
Link -w -c 'MPS ' -t MPST ∂
calc.cp.o ∂
"{CLibraries}"StdCLib.o ∂
"{Libraries}"ToolLibs.o ∂
"{Libraries}"Runtime.o ∂
"{Libraries}"Interface.o ∂
"{CLibraries}"CPlusLib.o ∂
-o calc
Rez -a "{MPW}"Interfaces:Rincludes:SIOW.r -o calcAppl
Link -w -c 'JLMT' -t 'APPL' ∂
calc.cp.o ∂
"{CLibraries}"StdClib.o ∂
"{MPW}"Libraries:Libraries:SIOW.o ∂
"{Libraries}"Runtime.o ∂
"{Libraries}"Interface.o ∂
"{CLibraries}"CPlusLib.o ∂
-o calcAppl
So the second version can be run also by those of you who don’t have MPW.
FORTHcoming
I’m still waiting for those MacForth contributions coming in we’d really like to
see more of that in MacTutor. I’m sure there are quite a few of you satisfied MacForth
users who have something interesting to write about. Please contact me: I promise that
you get your space in this column. My network address has changed in the meantime,
since our institute is going from the Bitnet to the Internet world; so in the future,