TweetFollow Us on Twitter

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-ROM or 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:

<expression> :== <term> { [+|-] <term> }
<term>   :== <factor> { [*|/] <factor> }
<factor> :== <identifier> | <inumber> |
 (<expression >) | -<factor> |
 <identifier> = <expression>

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, please send messages to either of those three addresses (in order of preference):

 jl@macjl.embl-grenoble.fr
 langowski.j@applelink.apple.com
 langowsk@titan.embl-grenoble.fr 

(note the missing last letter in the name)

Meanwhile, we do have news from the Forth world. I don’t have to tell you that the NEON successor, Yerk, keeps being updated faster than I can write about it; you know that you can get the current version by ftp from oddjob.uchicago.edu. Mops, the NEON lookalike with real 680x0 machine code, can also be found there.

But here is something very interesting for those of you who used and liked Mach2, the Forth in which I did most of my examples here: Two users of Mach2, John Fleming who works at Motorola, and Steven Wiley, a molecular biologist at the University of Utah, got together and made all those modifications to Mach2 that the implementers should have done two years ago; now it is System7 and 32-bit compatible. It may also be soon in the public domain (non-commercial) like Yerk is, with the full source code available. You’ll hear more about it in one of the next columns. Until then.

Listing: The MPW calculator tool
// 
// calc.cp
//
// a simple calculator program
// based on an example from Dewhurst/Stark
// "Programming in C++"
//
// J. Langowski November 1992
//

#include <Ctype.h>
#include <StdIO.h>
#include <String.h>
#include <Stream.h>
#include <StdLib.h>

#define NIL 0

// basic syntax tree structure
//
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;} 
};

class dyad : public node {
 protected:
 node *left, *right;
 dyad(node *l, node *r) {left=l; right=r;}
 ~dyad() {delete left; delete right;}
};
// operators
//
class plus : public dyad {
 public:
 plus(node *l, node *r) : dyad(l,r) {}
 int eval() { return left->eval() + right->eval();} 
};

class minus : public dyad {
 public:
 minus(node *l, node *r) : dyad(l,r) {}
 int eval() { return left->eval() - right->eval();}
};

class times : public dyad {
 public:
 times(node *l, node *r) : dyad(l,r) {}
 int eval() { return left->eval() * right->eval();}
};

class divide : public dyad {
 public:
 divide(node *l, node *r) : dyad(l,r) {}
 int eval() { return left->eval() / right->eval();}
};

class uminus : public node {
 node *operand;
 public:
 uminus(node *o) {operand = o;}
 ~uminus() {delete operand;}
 int eval() {return -operand->eval();}
};

class inumber : public node {
 int value;
 public:
 inumber(int v) {value = v;}
 int eval() {return value;}
};


// identifier table
//
class id;

class entry {
 char *name;
 int value;
 entry *next;
 entry (char *nm, entry *n) {
 name = strcpy (new char[strlen(nm) + 1], nm);
 value = 0;
 next = n;
 }
 friend id;
};

class id : public node {
 static entry *symtab;
 entry *ent;
 entry *look(char *);
 public:
 id(char *nm) {ent = look(nm);}
 int set(int i) {return ent->value = i;}
 int eval() {return ent->value;}
};

entry *id::look(char *nm) {
 for(entry *p = symtab; p; p = p->next)
 if(strcmp(p->name,nm) == 0) return p;


 return symtab = new entry(nm,symtab);
}

entry *id::symtab = NIL;

// assignment
//
class equals : public dyad {
 public:
 equals(node *t,node *e) : dyad(t,e) {}
 int eval()
 { return left->set(right->eval()); }
};


// parsing + evaluation
//

static char token;   // current token 
static char line[81];   // for reading identifiers + numbers
enum {ID = char(128), INT, EOLN, BAD}; // special tokens

node *e(), *t(), *f();    // parser routines 
 // for expression, term, factor

// input stream scanner, returns next token
//
char scan() {
 char c;
 while (1)
 switch (c = cin.get()) {
 case '+': case '-': case '*': case '/':
 case '(': case ')': case '=':
 return c;
 case ' ': case '\t':
 continue;
 case '\n': case '\r':
 return EOLN;
 default:
 if (isdigit(c)) {
 char *s = line;
 do*s++ = c;
 while(isdigit(c = cin.get()));
 *s = '\0'; 
 // terminate string just read
 cin.putback(c); 
 // had read one too much
 return INT;
 }
 
 if (isalpha(c)) {
 char *s = line;
 do*s++ = c;
 while(isalnum(c = cin.get()));
 *s = '\0'; 
 // terminate string just read
 cin.putback(c); 
 // had read one too much
 return ID;
 }
 
 return BAD; 
 // if nothing fits, syntax error
 }
}

// simple error routine
//
void error() { cout << "Syntax error." << endl; exit(255); }

// parser routines for expression, term, factor
//

// expression = term (+ -) term
node *e() {
 node *root = t();
 while (1)
 switch (token) {
 case '+':
 token = scan();
 root = new plus(root, t()); 
 break;
 case '-':
 token = scan();
 root = new minus(root, t());
 break;
 default:
 return root;
 }
}

// term = factor (* /) factor
node *t() {
 node *root = f();
 while (1)
 switch (token) {
 case '*':
 token = scan();
 root = new times(root, t()); 
 break;
 case '/':
 token = scan();
 root = new divide(root, t()); 
 break;
 default:
 return root;
 }
}

// factor = identifier | number | expression | -factor
node *f() {
 node *root = NIL;
 switch (token) {
 case ID:
 root = new id(line);
 token = scan();
 if (token == '=') {
 token = scan();
 root = new equals(root, e());
 }
 return root;
 case INT:
 root = new inumber(atoi(line));
 token = scan();
 return root;
 case '(':
 token = scan();
 root = e();
 if (token != ')' ) error();
 token = scan();
 return root;
 case '-':
 token = scan();
 return new uminus(f());
 default:
 error();
 }
}

// main program
//

void main() {
 node *root = NIL;
 while (1) {
 cout << "Enter expression: " << endl;
 token = scan();
 root = e();

 if (token == BAD) error();
 
 if (root != NIL)
 { 
     cout << "Result = " << root->eval() << endl;
     delete root; 
 }
 }
}

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

OmniGraffle 6.3 - Create diagrams, flow...
OmniGraffle helps you draw beautiful diagrams, family trees, flow charts, org charts, layouts, and (mathematically speaking) any other directed or non-directed graphs. We've had people use Graffle to... Read more
PDFKey Pro 4.3.2 - Edit and print passwo...
PDFKey Pro can unlock PDF documents protected for printing and copying when you've forgotten your password. It can now also protect your PDF files with a password to prevent unauthorized access and/... Read more
Ableton Live 9.2.2 - Record music using...
Ableton Live lets you create and record music on your Mac. Use digital instruments, pre-recorded sounds, and sampled loops to arrange, produce, and perform your music like never before. Ableton Live... Read more
Macs Fan Control 1.3.1.0 - Monitor and c...
Macs Fan Control allows you to monitor and control almost any aspect of your computer's fans, with support for controlling fan speed, temperature sensors pane, menu-bar icon, and autostart with... Read more
NetShade 6.3.1 - Browse privately using...
NetShade is an anonymous proxy and VPN app+service for Mac. Unblock your Internet through NetShade's high-speed proxy and VPN servers spanning seven countries. NetShade masks your IP address as you... Read more
Dragon Dictate 4.0.7 - Premium voice-rec...
With Dragon Dictate speech recognition software, you can use your voice to create and edit text or interact with your favorite Mac applications. Far more than just speech-to-text, Dragon Dictate lets... Read more
Persecond 1.0.2 - Timelapse video made e...
Persecond is the easy, fun way to create a beautiful timelapse video. Import an image sequence from any camera, trim the length of your video, adjust the speed and playback direction, and you’re done... Read more
GIMP 2.8.14p2 - Powerful, free image edi...
GIMP is a multi-platform photo manipulation tool. GIMP is an acronym for GNU Image Manipulation Program. The GIMP is suitable for a variety of image manipulation tasks, including photo retouching,... Read more
Sandvox 2.10.2 - Easily build eye-catchi...
Sandvox is for Mac users who want to create a professional looking website quickly and easily. With Sandvox, you don't need to be a Web genius to build a stylish, feature-rich, standards-compliant... Read more
LibreOffice 5.0.1.2 - Free, open-source...
LibreOffice is an office suite (word processor, spreadsheet, presentations, drawing tool) compatible with other major office suites. The Document Foundation is coordinating development and... Read more

ReBoard: Revolutionary Keyboard (Utilit...
ReBoard: Revolutionary Keyboard 1.0 Device: iOS Universal Category: Utilities Price: $1.99, Version: 1.0 (iTunes) Description: Do everything within the keyboard without switching apps! If you are in WhatsApp, how do you schedule a... | Read more »
Tiny Empire (Games)
Tiny Empire 1.1.3 Device: iOS Universal Category: Games Price: $2.99, Version: 1.1.3 (iTunes) Description: Launch cannonballs and blow tiny orcs into thousands of pieces in this intuitive fantasy-themed puzzle shooter! Embark on an... | Read more »
Astropad Mini (Productivity)
Astropad Mini 1.0 Device: iOS iPhone Category: Productivity Price: $4.99, Version: 1.0 (iTunes) Description: *** 50% off introductory price! ​*** Get the high-end experience of a Wacom tablet at a fraction of the price with Astropad... | Read more »
Emo Chorus (Music)
Emo Chorus 1.0.0 Device: iOS Universal Category: Music Price: $1.99, Version: 1.0.0 (iTunes) Description: Realistic Choir simulator ranging from simple Chorus emulation to full ensemble Choir with 128 members. ### introductory offer... | Read more »
Forest Spirit (Games)
Forest Spirit 1.0.5 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0.5 (iTunes) Description: | Read more »
Ski Safari 2 (Games)
Ski Safari 2 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: The world's most fantastical, fun, family-friendly skiing game is back and better than ever! Play as Sven's sister Evana, share... | Read more »
Lara Croft GO (Games)
Lara Croft GO 1.0.47768 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0.47768 (iTunes) Description: Lara Croft GO is a turn based puzzle-adventure set in a long-forgotten world. Explore the ruins of an ancient... | Read more »
Whispering Willows (Games)
Whispering Willows 1.23 Device: iOS Universal Category: Games Price: $4.99, Version: 1.23 (iTunes) Description: **LAUNCH SALE 50% OFF** - Whispering Willows is on sale for 50% off ($4.99) until September 9th. | Read more »
Calvino Noir (Games)
Calvino Noir 1.1 Device: iOS iPhone Category: Games Price: $3.99, Version: 1.1 (iTunes) Description: The film noir stealth game. Calvino Noir is the exploratory, sneaking adventure through the 1930s European criminal underworld.... | Read more »
Angel Sword (Games)
Angel Sword 1.0 Device: iOS Universal Category: Games Price: $6.99, Version: 1.0 (iTunes) Description: Prepare to adventure in the most epic full scale multiplayer 3D RPG for mobile! Experience amazing detailed graphics in full HD.... | Read more »

Price Scanner via MacPrices.net

Apple offering refurbished 2015 13-inch Retin...
The Apple Store is offering Apple Certified Refurbished 2015 13″ Retina MacBook Pros for up to $270 (15%) off the cost of new models. An Apple one-year warranty is included with each model, and... Read more
Apple refurbished 2015 MacBook Airs available...
The Apple Store has Apple Certified Refurbished 2015 11″ and 13″ MacBook Airs (the latest models), available for up to $180 off the cost of new models. An Apple one-year warranty is included with... Read more
21-inch iMacs on sale for up to $120 off MSRP
B&H Photo has 21″ iMacs on sale for up to $120 off MSRP including free shipping plus NY sales tax only: - 21″ 1.4GHz iMac: $999.99 $100 off - 21″ 2.7GHz iMac: $1199.99 $100 off - 21″ 2.9GHz iMac... Read more
5K iMacs on sale for up to $150 off MSRP, fre...
B&H Photo has the 27″ 3.3GHz 5K iMac on sale for $1899.99 including free shipping plus NY tax only. Their price is $100 off MSRP. They have the 27″ 3.5GHz 5K iMac on sale for $2149.99 $2199.99, $... Read more
1.4GHz Mac mini, refurbished, available for $...
The Apple Store has Apple Certified Refurbished 1.4GHz Mac minis available for $419. Apple’s one-year warranty is included, and shipping is free. Their price is $80 off MSRP, and it’s the lowest... Read more
iPad Air 2 on sale for up to $100 off MSRP
Best Buy has iPad Air 2s on sale for up to $100 off MSRP on their online store for a limited time. Choose free shipping or free local store pickup (if available). Sale prices available for online... Read more
MacBook Airs on sale for $100 off MSRP
Best Buy has MacBook Airs on sale for $100 off MSRP on their online store. Choose free shipping or free local store pickup (if available). Sale prices for online orders only, in-store prices may vary... Read more
Big Grips Lift Handle For iPad Air and iPad A...
KEM Ventures, Inc. which pioneered the extra-large, super-protective iPad case market with the introduction of Big Grips Frame and Stand in 2011, is launching Big Grips Lift featuring a new super-... Read more
Samsung Launches Galaxy Tab S2, Its Most Powe...
Samsung Electronics America, Inc. has announced the U.S. release of the Galaxy Tab S2, its thinnest, lightest, ultra-fast tablet. Blending form and function, elegant design and multitasking power,... Read more
Tablet Screen Sizes Expanding as iPad Pro App...
Larger screen sizes are gaining favor as the tablet transforms into a productivity device, with shipments growing 185 percent year-over-year in 2015. According to a new Strategy Analytics’ Tablet... Read more

Jobs Board

*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
*Apple* Desktop Analyst - KDS Staffing (Unit...
…field and consistent professional recruiting achievement. Job Description: Title: Apple Desktop AnalystPosition Type: Full-time PermanentLocation: White Plains, NYHot Read more
*Apple* Systems Engineer (Mclean, VA and NYC...
Title: Apple Systems Engineer (Mclean, VA and NYC) Location: United States-New York-New York-200 Park Ave (22005) Other Locations: United States-Virginia-Vienna-Towers Read more
*Apple* Systems Engineer (Mclean, VA and NYC...
…Assist in providing strategic direction and technical leadership within the Apple portfolio, including desktops, laptops, and printing environment. This person will Read more
*Apple* Subject Matter Expert - Experis (Uni...
We are seeking an Apple Subject Matter Expert to assist in developing the architecture, support and services for integration of Apple devices into the company's Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.