Partys 5applying C++

Partys 5applying C++

P

The purpose of this section is twofold. First, the examples

help illustrate the benefits of object-oriented programming.

Second, they show how C++ can be applied to solve two very

different types of programming problems.


Chapter

The

strings. The overloaded relational operators are defined within the

declaration. They are repeated here for your convenience:

StrType class supports the full range of relational operations to be applied toStrType class

// relational operations between StrType objects

int operator==(StrType &o) { return !strcmp(p, o.p); }

int operator!=(StrType &o) { return strcmp(p, o.p); }

int operator<(StrType &o) { return strcmp(p, o.p) < 0; }

int operator>(StrType &o) { return strcmp(p, o.p) > 0; }

int operator<=(StrType &o) { return strcmp(p, o.p) <= 0; }

int operator>=(StrType &o) { return strcmp(p, o.p) >= 0; }

// operations between StrType objects and quoted strings

int operator==(char *s) { return !strcmp(p, s); }

int operator!=(char *s) { return strcmp(p, s); }

int operator<(char *s) { return strcmp(p, s) < 0; }

int operator>(char *s) { return strcmp(p, s) > 0; }

int operator<=(char *s) { return strcmp(p, s) <= 0; }

int operator>=(char *s) { return strcmp(p, s) >= 0; }

The relational operations are very straightforward; you should have no trouble

understanding their implementation. However, keep in mind that the

implements comparisons between two

StrType classStrType objects or comparisons that have a

StrType

to be able to put the quoted string on the left and a

need to add additional relational functions.

Given the overloaded relational operator functions defined by

following types of string comparisons are allowed:

object as the left operand and a quoted string as the right operand. If you wantStrType object on the right, you willStrType, the

StrType x("one"), y("two"), z("three");

if(x < y) cout << "x less than y";

if(z=="three") cout << "z equals three";

y = "o";

z = "ne";

if(x==(y+z)) cout << "x equals y+z";

C h a p t e r 3 9 : I n t e g r a t i n g N e w C l a s s e s : A C u s t o m S t r i n g C l a s s

943

Miscellaneous String Functions

The

completely with the C++ programming environment. They are

StrType class defines three functions that make StrType objects integrate morestrsize(), makestr(),

and the conversion function

operator char *() . These functions are defined within the

StrType

declaration and are shown here:

int strsize() { return strlen(p); } // return size of string

void makestr(char *s) { strcpy(s, p); } // make quoted string

operator char *(){ return p; } // conversion to char *

The first two functions are easy to understand. As you can see, the

strsize()

function returns the length of the string pointed to by

might be different than the value stored in the

of a shorter string, for example), the length is computed by calling

p. Since the length of the stringsize variable (because of an assignmentstrlen() . The

makestr()

function is useful when you want to obtain a null-terminated string given a

function copies into a character array the string pointed to by p. ThisStrType

object.

The conversion function

to the string contained within the object. This function allows a

used anywhere that a null-terminated string can be used. For example, this is valid

code:

operator char *() returns p, which is, of course, a pointerStrType object to be

StrType x("Hello");

char s[20];

// copy a string object using the strcpy() function

strcpy(s, x); // automatic conversion to char *

Recall that a conversion function is automatically executed when an object is

involved in an expression for which the conversion is defined. In this case, because the

prototype for the

type

a pointer to the string contained within

strcpy() function tells the compiler that its second argument is ofchar *, the conversion from StrType to char * is automatically performed, causingx to be returned. This pointer is then used by

strcpy()

to copy the string into s. Because of the conversion function, you can use an

StrType

takes an argument of type

object in place of a null-terminated string as an argument to any function thatchar *.

944

C + + : T h e C o m p l e t e R e f e r e n c e

The conversion to

has a pointer to the object's string, it is possible for that function to modify the

string directly, bypassing the

knowledge. For this reason, you must use the conversion to

loss of encapsulation in this case is offset by increased utility and integration with

existing library functions. However, such a trade-off is not always warranted.

char * does circumvent encapsulation, because once a functionStrType member functions and without that object'schar * with care. The

The Entire StrType Class

Here is a listing of the entire

demonstrates its features:

StrType class along with a short main() function that

#include <iostream>

#include <new>

#include <cstring>

#include <cstdlib>

using namespace std;

class StrType {

char *p;

int size;

public:

StrType();

StrType(char *str);

StrType(const StrType &o); // copy constructor

~StrType() { delete [] p; }

friend ostream &operator<<(ostream &stream, StrType &o);

friend istream &operator>>(istream &stream, StrType &o);

StrType operator=(StrType &o); // assign a StrType object

StrType operator=(char *s); // assign a quoted string

StrType operator+(StrType &o); // concatenate a StrType object

StrType operator+(char *s); // concatenate a quoted string

friend StrType operator+(char *s, StrType &o); /* concatenate

a quoted string with a StrType object */

C h a p t e r 3 9 : I n t e g r a t i n g N e w C l a s s e s : A C u s t o m S t r i n g C l a s s

945

Note

StrType operator-(StrType &o); // subtract a substring

StrType operator-(char *s); // subtract a quoted substring

// relational operations between StrType objects

int operator==(StrType &o) { return !strcmp(p, o.p); }

int operator!=(StrType &o) { return strcmp(p, o.p); }

int operator<(StrType &o) { return strcmp(p, o.p) < 0; }

int operator>(StrType &o) { return strcmp(p, o.p) > 0; }

int operator<=(StrType &o) { return strcmp(p, o.p) <= 0; }

int operator>=(StrType &o) { return strcmp(p, o.p) >= 0; }

// operations between StrType objects and quoted strings

int operator==(char *s) { return !strcmp(p, s); }

int operator!=(char *s) { return strcmp(p, s); }

int operator<(char *s) { return strcmp(p, s) < 0; }

int operator>(char *s) { return strcmp(p, s) > 0; }

int operator<=(char *s) { return strcmp(p, s) <= 0; }

int operator>=(char *s) { return strcmp(p, s) >= 0; }

int strsize() { return strlen(p); } // return size of string

void makestr(char *s) { strcpy(s, p); } // null-terminated string

operator char *() { return p; } // conversion to char *

};

// No explicit initialization.

StrType::StrType() {

size = 1; // make room for null terminator

try {

p = new char[size];

} catch (bad_alloc xa) {

cout << "Allocation error\n";

exit(1);

}

strcpy(p, "");

}

// Initialize using a quoted string.

StrType::StrType(char *str) {

size = strlen(str) + 1; // make room for null terminator

try {

p = new char[size];

946

C + + : T h e C o m p l e t e R e f e r e n c e

} catch (bad_alloc xa) {

cout << "Allocation error\n";

exit(1);

}

strcpy(p, str);

}

// Initialize using a StrType object.

StrType::StrType(const StrType &o) {

size = o.size;

try {

p = new char[size];

} catch (bad_alloc xa) {

cout << "Allocation error\n";

exit(1);

}

strcpy(p, o.p);

}

// Output a string.

ostream &operator<<(ostream &stream, StrType &o)

{

stream << o.p;

return stream;

}

// Input a string.

istream &operator>>(istream &stream, StrType &o)

{

char t[255]; // arbitrary size - change if necessary

int len;

stream.getline(t, 255);

len = strlen(t) + 1;

if(len > o.size) {

delete [] o.p;

try {

o.p = new char[len];

} catch (bad_alloc xa) {

cout << "Allocation error\n";

exit(1);

C h a p t e r 3 9 : I n t e g r a t i n g N e w C l a s s e s : A C u s t o m S t r i n g C l a s s

947

}

o.size = len;

}

strcpy(o.p, t);

return stream;

}

// Assign a StrType object to a StrType object.

StrType StrType::operator=(StrType &o)

{

StrType temp(o.p);

if(o.size > size) {

delete [] p; // free old memory

try {

p = new char[o.size];

} catch (bad_alloc xa) {

cout << "Allocation error\n";

exit(1);

}

size = o.size;

}

strcpy(p, o.p);

strcpy(temp.p, o.p);

return temp;

}

// Assign a quoted string to a StrType object.

StrType StrType::operator=(char *s)

{

int len = strlen(s) + 1;

if(size < len) {

delete [] p;

try {

p = new char[len];

} catch (bad_alloc xa) {

cout << "Allocation error\n";

exit(1);

}

size = len;

948

C + + : T h e C o m p l e t e R e f e r e n c e

}

strcpy(p, s);

return *this;

}

// Concatenate two StrType objects.

StrType StrType::operator+(StrType &o)

{

int len;

StrType temp;

delete [] temp.p;

len = strlen(o.p) + strlen(p) + 1;

temp.size = len;

try {

temp.p = new char[len];

} catch (bad_alloc xa) {

cout << "Allocation error\n";

exit(1);

}

strcpy(temp.p, p);

strcat(temp.p, o.p);

return temp;

}

// Concatenate a StrType object and a quoted string.

StrType StrType::operator+(char *s)

{

int len;

StrType temp;

delete [] temp.p;

len = strlen(s) + strlen(p) + 1;

temp.size = len;

try {

temp.p = new char[len];

} catch (bad_alloc xa) {

cout << "Allocation error\n";

exit(1);

C h a p t e r 3 9 : I n t e g r a t i n g N e w C l a s s e s : A C u s t o m S t r i n g C l a s s

949

}

strcpy(temp.p, p);

strcat(temp.p, s);

return temp;

}

// Concatenate a quoted string and a StrType object.

StrType operator+(char *s, StrType &o)

{

int len;

StrType temp;

delete [] temp.p;

len = strlen(s) + strlen(o.p) + 1;

temp.size = len;

try {

temp.p = new char[len];

} catch (bad_alloc xa) {

cout << "Allocation error\n";

exit(1);

}

strcpy(temp.p, s);

strcat(temp.p, o.p);

return temp;

}

// Subtract a substring from a string using StrType objects.

StrType StrType::operator-(StrType &substr)

{

StrType temp(p);

char *s1;

int i, j;

s1 = p;

for(i=0; *s1; i++) {

if(*s1!=*substr.p) { // if not first letter of substring

temp.p[i] = *s1; // then copy into temp

950

C + + : T h e C o m p l e t e R e f e r e n c e

s1++;

}

else {

for(j=0; substr.p[j]==s1[j] && substr.p[j]; j++) ;

if(!substr.p[j]) { // is substring, so remove it

s1 += j;

i--;

}

else { // is not substring, continue copying

temp.p[i] = *s1;

s1++;

}

}

}

temp.p[i] = '\0';

return temp;

}

// Subtract quoted string from a StrType object.

StrType StrType::operator-(char *substr)

{

StrType temp(p);

char *s1;

int i, j;

s1 = p;

for(i=0; *s1; i++) {

if(*s1!=*substr) { // if not first letter of substring

temp.p[i] = *s1; // then copy into temp

s1++;

}

else {

for(j=0; substr[j]==s1[j] && substr[j]; j++) ;

if(!substr[j]) { // is substring, so remove it

s1 += j;

i--;

}

else { // is not substring, continue copying

temp.p[i] = *s1;

s1++;

}

}

C h a p t e r 3 9 : I n t e g r a t i n g N e w C l a s s e s : A C u s t o m S t r i n g C l a s s

951

}

temp.p[i] = '\0';

return temp;

}

int main()

{

StrType s1("A sample session using string objects.\n");

StrType s2(s1);

StrType s3;

char s[80];

cout << s1 << s2;

s3 = s1;

cout << s1;

s3.makestr(s);

cout << "Convert to a string: " << s;

s2 = "This is a new string.";

cout << s2 << endl;

StrType s4(" So is this.");

s1 = s2+s4;

cout << s1 << endl;

if(s2==s3) cout << "Strings are equal.\n";

if(s2!=s3) cout << "Strings are not equal.\n";

if(s1<s4) cout << "s1 less than s4\n";

if(s1>s4) cout << "s1 greater than s4\n";

if(s1<=s4) cout << "s1 less than or equals s4\n";

if(s1>=s4) cout << "s1 greater than or equals s4\n";

if(s2 > "ABC") cout << "s2 greater than ABC\n\n";

s1 = "one two three one two three\n";

s2 = "two";

cout << "Initial string: " << s1;

cout << "String after subtracting two: ";

s3 = s1 - s2;

cout << s3;

952

C + + : T h e C o m p l e t e R e f e r e n c e

cout << endl;

s4 = "Hi there!";

s3 = s4 + " C++ strings are fun\n";

cout << s3;

s3 = s3 - "Hi there!";

s3 = "Aren't" + s3;

cout << s3;

s1 = s3 - "are ";

cout << s1;

s3 = s1;

cout << "Enter a string: ";

cin >> s1;

cout << s1 << endl;

cout << "s1 is " << s1.strsize() << " characters long.\n";

puts(s1); // convert to char *

s1 = s2 = s3;

cout << s1 << s2 << s3;

s1 = s2 = s3 = "Bye ";

cout << s1 << s2 << s3;

return 0;

}

The preceding program produces this output:

A sample session using string objects.

A sample session using string objects.

A sample session using string objects.

Convert to a string: A sample session using string objects.

This is a new string.

This is a new string. So is this.

Strings are not equal.

s1 greater than s4

s1 greater than or equals s4

s2 greater than ABC

C h a p t e r 3 9 : I n t e g r a t i n g N e w C l a s s e s : A C u s t o m S t r i n g C l a s s

953

Initial string: one two three one two three

String after subtracting two: one three one three

Hi there! C++ strings are fun

Aren't C++ strings are fun

Aren't C++ strings fun

Enter a string: I like C++

s1 is 10 characters long.

I like C++

Aren't C++ strings fun

Aren't C++ strings fun

Aren't C++ strings fun

Bye Bye Bye

This output assumes that the string "I like C++" was entered by the user when

prompted for input.

To have easy access to the

rest of the preceding listing into a file called STR.H. Then, just include this header file

with any program in which you want to use

StrType class, remove the main() function and put theStrType.

Using the StrType Class

To conclude this chapter, two short examples are given that illustrate the

As you will see, because of the operators defined for it and because of its conversion

function to

That is, it can be used like any other type defined by Standard C++.

The first example creates a simple thesaurus by using

creates a two-dimensional array of

contains the key word, which may be looked up. The second string contains a list of

alternative or related words. The program prompts for a word, and if the word is in the

thesaurus, alternatives are displayed. This program is very simple, but notice how

clean and clear the string handling is because of the use of the

operators. (Remember, the header file STR.H contains the

StrType class.char *, StrType is fully integrated into the C++ programming environment.StrType objects. It firstStrType objects. Within each pair of strings, the firstStrType class and itsStrType class.)

#include "str.h"

#include <iostream>

using namespace std;

StrType thesaurus[][2] = {

"book", "volume, tome",

954

C + + : T h e C o m p l e t e R e f e r e n c e

"store", "merchant, shop, warehouse",

"pistol", "gun, handgun, firearm",

"run", "jog, trot, race",

"think", "muse, contemplate, reflect",

"compute", "analyze, work out, solve"

"", ""

};

int main()

{

StrType x;

cout << "Enter word: ";

cin >> x;

int i;

for(i=0; thesaurus[i][0]!=""; i++)

if(thesaurus[i][0]==x) cout << thesaurus[i][1];

return 0;

}

The next example uses a

a program, given its filename. To use the program, specify the filename without an

extension on the command line. The program then repeatedly tries to find an

executable file by that name by adding an extension, trying to open that file, and

reporting the results. (If the file does not exist, it cannot be opened.) After each

extension is tried, the extension is subtracted from the filename and a new extension is

added. Again, the

and easy to follow.

StrType object to check if there is an executable version ofStrType class and its operators make the string manipulations clean

#include "str.h"

#include <iostream>

#include <fstream>

using namespace std;

// executable file extensions

char ext[3][4] = {

"EXE",

"COM",

"BAT"

C h a p t e r 3 9 : I n t e g r a t i n g N e w C l a s s e s : A C u s t o m S t r i n g C l a s s

955

};

int main(int argc, char *argv[])

{

StrType fname;

int i;

if(argc!=2) {

cout << "Usage: fname\n";

return 1;

}

fname = argv[1];

fname = fname + "."; // add period

for(i=0; i<3; i++) {

fname = fname + ext[i]; // add extension

cout << "Trying " << fname << " ";

ifstream f(fname);

if(f) {

cout << "- Exists\n";

f.close();

}

else cout << "- Not found\n";

fname = fname - ext[i]; // subtract extension

}

return 0;

}

For example, if this program is called ISEXEC, and assuming that TEST.EXE exists,

the command line

ISEXEC TEST produces this output:

Trying TEST.EXE - Exists

Trying TEST.COM - Not found

Trying TEST.BAT - Not found

One thing to notice about the program is that an

StrType object is used by the

ifstream

automatically invoked. As this situation illustrates, by the careful application of C++

features, you can achieve significant integration between C++'s standard types and

types that you create.

constructor. This works because the conversion function char *() is

956

C + + : T h e C o m p l e t e R e f e r e n c e

Creating and Integrating New Types in General

As the

new data type into the C++ environment. To do so, just follow these steps.

1. Overload all appropriate operators, including the I/O operators.

2. Define all appropriate conversion functions.

3. Provide constructors that allow objects to be easily created in a variety of

situations.

Part of the power of C++ is its extensibility. Don't be afraid to take advantage of it.

StrType class has demonstrated, it is actually quite easy to create and integrate a

A Challenge

Here is an interesting challenge that you might enjoy. Try implementing

the STL. That is, use a container to store the characters that comprise a string. Use

iterators to operate on the strings, and use the algorithms to perform the various string

manipulations.

StrType using

C h a p t e r 3 9 : I n t e g r a t i n g N e w C l a s s e s : A C u s t o m S t r i n g C l a s s

957

This page intentionally left blank.

Chapter 40

An Object-Oriented

Expression Parser

959

C++

W

not provide. In this chapter we will examine one of them: the

An expression parser is used to evaluate an algebraic expression, such as

(10 – 8) * 3. Expression parsers are quite useful and are applicable to a wide range of

applications. They are also one of programming's more elusive entities. For various

reasons, the procedures used to create an expression parser are not widely taught or

disseminated. Indeed, many otherwise accomplished programmers are mystified by

the process of expression parsing.

Expression parsing is actually very straightforward, and in many ways easier than

other programming tasks. The reason for this is that the task is well defined and works

according to the strict rules of algebra. This chapter will develop what is commonly

referred to as a

enable you to evaluate complex numeric expressions. Three versions of the parser

will be created. The first two are nongeneric versions. The final one is generic and

may be applied to any numeric type. However, before any parser can be developed,

a brief overview of expressions and parsing is necessary.

hile Standard C++ is quite extensive, there are still a few things that it doesexpression parser.recursive-descent parser and all the necessary support routines that

Expressions

Since an expression parser evaluates an algebraic expression, it is important to

understand what the constituent parts of an expression are. Although expressions can

be made up of all types of information, this chapter deals only with numeric

expressions. For our purposes, numeric expressions are composed of the following

items:

Numbers

The operators +, −, /, *, ^, %, =

Parentheses

For our parser, the operator

and = is the assignment operator. These items can be combined in expressions

according to the rules of algebra. Here are some examples:

10 – 8

(100 – 5) * 14/6

a + b – c

10^5

a = 10 – b

Variables^ indicates exponentiation (not the XOR as it does in C++),

960

C + + : T h e C o m p l e t e R e f e r e n c e

Assume this precedence for each operator:

highest + – (unary)

^

* / %

+ –

lowest =

Operators of equal precedence evaluate from left to right.

In the examples in this chapter, all variables are single letters (in other words, 26

variables,

treated as the same variable). For the first version of the parser, all numeric values are

elevated to

of values. Finally, to keep the logic clear and easy to understand, only a minimal

amount of error checking is included.

A through Z, are available). The variables are not case sensitive (a and A aredouble, although you could easily write the routines to handle other types

Parsing Expressions: The Problem

If you have not thought much about the problem of expression parsing, you might

assume that it is a simple task. However, to better understand the problem, try to

evaluate this sample expression:

10 – 2 * 3

You know that this expression is equal to the value 4. Although you could easily create

a program that would compute that

program that gives the correct answer for any

think of a routine something like this:

a = get first operand

while(operands present) {

op = get operator

b = get second operand

a = a op b

}

specific expression, the question is how to create aarbitrary expression. At first you might

C h a p t e r 4 0 : A n O b j e c t - O r i e n t e d E x p r e s s i o n P a r s e r

961

This routine gets the first operand, the operator, and the second operand to perform

the first operation and then gets the next operator and operand to perform the next

operation, and so on. However, if you use this basic approach, the expression 10 – 2 * 3

evaluates to 24 (that is, 8 * 3) instead of 4 because this procedure neglects the

precedence of the operators. You cannot just take the operands and operators in order

from left to right because the rules of algebra dictate that multiplication must be done

before subtraction. Some beginners think that this problem can be easily overcome, and

sometimes, in very restricted cases, it can. But the problem only gets worse when you

add parentheses, exponentiation, variables, unary operators, and the like.

Although there are a few ways to write a routine that evaluates expressions, the

one developed here is the one most easily written by a person. It is also the most

common. The method used here is called a

this chapter you will see how it got its name. (Some of the other methods used to write

parsers employ complex tables that must be generated by another computer program.

These are sometimes called

recursive-descent parser, and in the course oftable-driven parsers.)

Parsing an Expression

There are a number of ways to parse and evaluate an expression. For use with a

recursive-descent parser, think of expressions as

expressions that are defined in terms of themselves. If, for the moment, we assume that

expressions can only use

the following rules:

expression

term

factor

The square brackets designate an optional element, and the -> means

fact, the rules are usually called the

could say: "Term produces factor times factor or factor divided by factor" for the

definition of

an expression is defined.

The expression

10 + 5 * B

recursive data structures—that is,+, −, *, /, and parentheses, all expressions can be defined with−> term [+ term] [− term]−> factor [* factor] [/ factor]−> variable, number, or (expression)produces. Inproduction rules of the expression. Therefore, youterm. Notice that the precedence of the operators is implicit in the way

962

C + + : T h e C o m p l e t e R e f e r e n c e

has two terms: 10, and 5 * B . The second term contains two factors: 5 and B. These

factors consist of one number and one variable.

On the other hand, the expression

14 * (7 – C)

has two factors: 14 and (7 – C). The factors consist of one number and one parenthesized

expression. The parenthesized expression contains two terms: one number and one variable.

This process forms the basis for a recursive-descent parser, which is a set of

mutually recursive functions that work in a chainlike fashion and implement the

production rules. At each appropriate step, the parser performs the specified

operations in the algebraically correct sequence. To see how the production rules are

used to parse an expression, let's work through an example using this expression:

9/3 – (100 + 56)

Here is the sequence that you will follow:

1. Get the first term, 9/3.

2. Get each factor and divide the integers. The resulting value is 3.

3. Get the second term, (100 + 56). At this point, start recursively analyzing the

second subexpression.

4. Get each term and add. The resulting value is 156.

5. Return from the recursive call, and subtract 156 from 3. The answer is –153.

If you are a little confused at this point, don't feel bad. This is a fairly complex

concept that takes some getting used to. There are two basic things to remember about

this recursive view of expressions. First, the precedence of the operators is implicit in

the way the production rules are defined. Second, this method of parsing and

evaluating expressions is very similar to the way humans evaluate mathematical

expressions.

The remainder of this chapter develops three parsers. The first will parse and

evaluate floating-point expressions of type

double that consist only of constant values.

Next, this parser is enhanced to support the use of variables. Finally, in the third

version, the parser is implemented as a template class that can be used to parse

expressions of any type.

C h a p t e r 4 0 : A n O b j e c t - O r i e n t e d E x p r e s s i o n P a r s e r

963

The Parser Class

The expression parser is built upon the

shown here. Subsequent versions of the parser build upon it.

parser class. The first version of parser is

class parser {

char *exp_ptr; // points to the expression

char token[80]; // holds current token

char tok_type; // holds token's type

void eval_exp2(double &result);

void eval_exp3(double &result);

void eval_exp4(double &result);

void eval_exp5(double &result);

void eval_exp6(double &result);

void atom(double &result);

void get_token();

void serror(int error);

int isdelim(char c);

public:

parser();

double eval_exp(char *exp);

};

The

evaluated is contained in a null-terminated string pointed to by

parser evaluates expressions that are contained in standard ASCII strings. For example,

the following strings contain expressions that the parser can evaluate:

"10

"2 * 3.3 / (3.1416 * 3.3)"

When the parser begins execution,

expression string. As the parser executes, it works its way through the string until the

null-terminator is encountered.

The meaning of the other two member variables,

in the next section.

The entry point to the parser is through

pointer to the expression to be analyzed. The functions

parser class contains three private member variables. The expression to beexp_ptr. Thus, the− 5"exp_ptr must point to the first character in thetoken and tok_type, are describedeval_exp() , which must be called with aeval_exp2() through

eval_exp6()

enhanced set of the expression production rules discussed earlier. In subsequent

versions of the parser, a function called

along with atom() form the recursive-descent parser. They implement aneval_exp1() will also be added.

964

C + + : T h e C o m p l e t e R e f e r e n c e

The

serror() handles syntax errors in the expression. The functions get_token()

and

in the next section.

isdelim() are used to dissect the expression into its component parts, as described

Dissecting an Expression

In order to evaluate expressions, you need to be able to break an expression into its

components. Since this operation is fundamental to parsing, let's look at it before

examining the parser itself.

Each component of an expression is called a

A * B – (W + 10)

contains the tokens A, *, B, –, (, W, +, 10, and ). Each token represents an indivisible

unit of the expression. In general, you need a function that sequentially returns each

token in the expression individually. The function must also be able to skip over spaces

and tabs and detect the end of the expression. The function that we will use to perform

this task is called

Besides the token, itself, you will also need to know what type of token is being

returned. For the parser developed in this chapter, you need only three types:

token. For example, the expressionget_token() , which is a member function of the parser class.

VARIABLE

and parentheses.)

The

expression pointed to by

the type of the token into the member variable

, NUMBER, and DELIMITER. (DELIMITER is used for both operatorsget_token() function is shown here. It obtains the next token from theexp_ptr and puts it into the member variable token. It putstok_type.

// Obtains the next token.

void parser::get_token()

{

register char *temp;

tok_type = 0;

temp = token;

*temp = '\0';

if(!*exp_ptr) return; // at end of expression

while(isspace(*exp_ptr)) ++exp_ptr; // skip over white space

if(strchr("+-*/%^=()", *exp_ptr)){

tok_type = DELIMITER;

C h a p t e r 4 0 : A n O b j e c t - O r i e n t e d E x p r e s s i o n P a r s e r

965

// advance to next char

*temp++ = *exp_ptr++;

}

else if(isalpha(*exp_ptr)) {

while(!isdelim(*exp_ptr)) *temp++ = *exp_ptr++;

tok_type = VARIABLE;

}

else if(isdigit(*exp_ptr)) {

while(!isdelim(*exp_ptr)) *temp++ = *exp_ptr++;

tok_type = NUMBER;

}

*temp = '\0';

}

// Return true if c is a delimiter.

int parser::isdelim(char c)

{

if(strchr(" +-/*%^=()", c) || c==9 || c=='\r' || c==0)

return 1;

return 0;

}

Look closely at the preceding functions. After the first few initializations,

get_token()

so by checking the character pointed to by

expression being analyzed, if it points to a null, the end of the expression has been

reached. If there are still more tokens to retrieve from the expression,

skips over any leading spaces. Once the spaces have been skipped,

to either a number, a variable, an operator, or if trailing spaces end the expression, a

null. If the next character is an operator, it is returned as a string in

checks to see if the null terminating the expression has been found. It doesexp_ptr. Since exp_ptr is a pointer to theget_token() firstexp_tpr is pointingtoken, and

DELIMITER

to be one of the variables. It is returned as a string in

the value

placed in its string form in

is none of the preceding, it is assumed that the end of the expression has been reached.

In this case,

As stated earlier, to keep the code in this function clean, a certain amount of error

checking has been omitted and some assumptions have been made. For example, any

unrecognized character may end an expression. Also, in this version, variables may be

of any length, but only the first letter is significant. You can add more error checking

and other details as your specific application dictates.

is placed in tok_type. If the next character is a letter instead, it is assumedtoken, and tok_type is assignedVARIABLE. If the next character is a digit, the entire number is read andtoken and its type is NUMBER. Finally, if the next charactertoken is null, which signals the end of the expression.

966

C + + : T h e C o m p l e t e R e f e r e n c e

To better understand the tokenization process, study what it returns for each token

and type in the following expression:

A + 100 – (B * C) /2

Token Token type

A VARIABLE

+ DELIMITER

100 NUMBER

−

( DELIMITER

BVARIAB LE

* DELIMITER

C VARIABLE

) DELIMITER

/ DELIMITER

2 NUMBER

null null

Remember that

a single character.

DELIMITERtoken always holds a null-terminated string, even if it contains just

A Simple Expression Parser

Here is the first version of the parser. It can evaluate expressions that consist solely of

constants, operators, and parentheses. It cannot accept expressions that contain

variables.

/* This module contains the recursive descent

parser that does not use variables.

*/

#include <iostream>

#include <cstdlib>

#include <cctype>

#include <cstring>

C h a p t e r 4 0 : A n O b j e c t - O r i e n t e d E x p r e s s i o n P a r s e r

967

using namespace std;

enum types { DELIMITER = 1, VARIABLE, NUMBER};

class parser {

char *exp_ptr; // points to the expression

char token[80]; // holds current token

char tok_type; // holds token's type

void eval_exp2(double &result);

void eval_exp3(double &result);

void eval_exp4(double &result);

void eval_exp5(double &result);

void eval_exp6(double &result);

void atom(double &result);

void get_token();

void serror(int error);

int isdelim(char c);

public:

parser();

double eval_exp(char *exp);

};

// parser constructor

parser::parser()

{

exp_ptr = NULL;

}

// Parser entry point.

double parser::eval_exp(char *exp)

{

double result;

exp_ptr = exp;

get_token();

if(!*token) {

serror(2); // no expression present

return 0.0;

}

eval_exp2(result);

968

C + + : T h e C o m p l e t e R e f e r e n c e

if(*token) serror(0); // last token must be null

return result;

}

// Add or subtract two terms.

void parser::eval_exp2(double &result)

{

register char op;

double temp;

eval_exp3(result);

while((op = *token) == '+' || op == '-') {

get_token();

eval_exp3(temp);

switch(op) {

case '-':

result = result - temp;

break;

case '+':

result = result + temp;

break;

}

}

}

// Multiply or divide two factors.

void parser::eval_exp3(double &result)

{

register char op;

double temp;

eval_exp4(result);

while((op = *token) == '*' || op == '/' || op == '%') {

get_token();

eval_exp4(temp);

switch(op) {

case '*':

result = result * temp;

break;

case '/':

result = result / temp;

break;

C h a p t e r 4 0 : A n O b j e c t - O r i e n t e d E x p r e s s i o n P a r s e r

969

case '%':

result = (int) result % (int) temp;

break;

}

}

}

// Process an exponent

void parser::eval_exp4(double &result)

{

double temp, ex;

register int t;

eval_exp5(result);

if(*token== '^') {

get_token();

eval_exp4(temp);

ex = result;

if(temp==0.0) {

result = 1.0;

return;

}

for(t=(int)temp-1; t>0; --t) result = result * (double)ex;

}

}

// Evaluate a unary + or -.

void parser::eval_exp5(double &result)

{

register char op;

op = 0;

if((tok_type == DELIMITER) && *token=='+' || *token == '-') {

op = *token;

get_token();

}

eval_exp6(result);

if(op=='-') result = -result;

}

// Process a parenthesized expression.

void parser::eval_exp6(double &result)

970

C + + : T h e C o m p l e t e R e f e r e n c e

{

if((*token == '(')) {

get_token();

eval_exp2(result);

if(*token != ')')

serror(1);

get_token();

}

else atom(result);

}

// Get the value of a number.

void parser::atom(double &result)

{

switch(tok_type) {

case NUMBER:

result = atof(token);

get_token();

return;

default:

serror(0);

}

}

// Display a syntax error.

void parser::serror(int error)

{

static char *e[]= {

"Syntax Error",

"Unbalanced Parentheses",

"No expression Present"

};

cout << e[error] << endl;

}

// Obtain the next token.

void parser::get_token()

{

register char *temp;

tok_type = 0;

temp = token;

C h a p t e r 4 0 : A n O b j e c t - O r i e n t e d E x p r e s s i o n P a r s e r

971

*temp = '\0';

if(!*exp_ptr) return; // at end of expression

while(isspace(*exp_ptr)) ++exp_ptr; // skip over white space

if(strchr("+-*/%^=()", *exp_ptr)){

tok_type = DELIMITER;

// advance to next char

*temp++ = *exp_ptr++;

}

else if(isalpha(*exp_ptr)) {

while(!isdelim(*exp_ptr)) *temp++ = *exp_ptr++;

tok_type = VARIABLE;

}

else if(isdigit(*exp_ptr)) {

while(!isdelim(*exp_ptr)) *temp++ = *exp_ptr++;

tok_type = NUMBER;

}

*temp = '\0';

}

// Return true if c is a delimiter.

int parser::isdelim(char c)

{

if(strchr(" +-/*%^=()", c) || c==9 || c=='\r' || c==0)

return 1;

return 0;

}

The parser as it is shown can handle the following operators:

addition, it can handle integer exponentiation (^) and the unary minus. The parser can

also deal with parentheses correctly. The actual evaluation of an expression takes place

in the mutually recursive functions

+, –, *, /, %. Ineval_exp2() through eval_exp6() , plus the atom()

function, which returns the value of a number. The comments at the start of each

function describe what role it plays in parsing the expression.

The simple

main() function that follows demonstrates the use of the parser.

int main()

{

972

C + + : T h e C o m p l e t e R e f e r e n c e

char expstr[80];

cout << "Enter a period to stop.\n";

parser ob; // instantiate a parser

for(;;) {

cout << "Enter expression: ";

cin.getline(expstr, 79);

if(*expstr=='.') break;

cout << "Answer is: " << ob.eval_exp(expstr) << "\n\n";

};

return 0;

}

Here is a sample run.

Enter a period to stop.

Enter expression: 10-2*3

Answer is: 4

Enter expression: (10-2)*3

Answer is: 24

Enter expression: 10/3

Answer is: 3.33333

Enter expression: .

Understanding the Parser

To understand exactly how the parser evaluates an expression, work through the

following expression. (Assume that

10 – 3 * 2

When

the token is null, the function prints the message

However, in this case, the token contains the number

null,

exp_ptr points to the start of the expression.)eval_exp(), the entry point into the parser, is called, it gets the first token. IfNo Expression Present and returns.10. Since the first token is noteval_exp2() is called. As a result, eval_exp2() calls eval_exp3(), and eval_exp3()

C h a p t e r 4 0 : A n O b j e c t - O r i e n t e d E x p r e s s i o n P a r s e r

973

calls

the token is a unary plus or minus, which in this case it is not, so

At this point

parenthesized expression) or calls

token is not a left parentheses,

Next, another token is retrieved, and the functions begin to return up the chain. Since

the token is now the operator

eval_exp4(), which in turn calls eval_exp5(). Then eval_exp5() checks whethereval_exp6() is called.eval_exp6() either recursively calls eval_exp2() (in the case of aatom() to find the value of a number. Since theatom() is executed and result is assigned the value 10.–, the functions return up to eval_exp2().

What happens next is very important. Because the token is

parser then gets the next token, which is

again. As before,

read. This causes a return back up the chain to

read. At this point, the first arithmetic operation occurs—the multiplication of 2 and 3.

The result is returned to

subtraction yields the answer 4. Although the process may at first seem complicated,

work through some other examples to verify that this method functions correctly

every time.

This parser would be suitable for use by a simple desktop calculator, as is

illustrated by the previous program. Before it could be used in a computer language,

database, or in a sophisticated calculator, however, it would need the ability to handle

variables. This is the subject of the next section.

–, it is saved in op. The3, and the descent down the chain beginsatom() is entered. The value 3 is returned in result, and the token * iseval_exp3(), where the final token 2 iseval_exp2(), and the subtraction is performed. The

Adding Variables to the Parser

All programming languages, many calculators, and spreadsheets use variables to store

values for later use. Before the parser can be used for such applications, it needs to be

expanded to include variables. To accomplish this, you need to add several things to

the parser. First, of course, are the variables themselves. As stated earlier, we will use

the letters

A through Z for variables. The variables will be stored in an array inside the

parser

Therefore, add the following to the

class. Each variable uses one array location in a 26-element array of doubles.parser class:

double vars[NUMVARS]; // holds variables' values

You will also need to change the

parser constructor, as shown here.

// parser constructor

parser::parser()

{

int i;

exp_ptr = NULL;

974

C + + : T h e C o m p l e t e R e f e r e n c e

for(i=0; i<NUMVARS; i++) vars[i] = 0.0;

}

As you can see, the variables are initialized to 0 as a courtesy to the user.

You will also need a function to look up the value of a given variable. Because the

variables are named

subtracting the ASCII value for

A through Z, they can easily be used to index the array vars byA from the variable name. The member function

find_var(),

shown here, accomplishes this:

// Return the value of a variable.

double parser::find_var(char *s)

{

if(!isalpha(*s)){

serror(1);

return 0.0;

}

return vars[toupper(*token)-'A'];

}

As this function is written, it will actually accept long variable names, but only the first

letter is significant. You may modify this to fit your needs.

You must also modify the

The new version is shown here:

atom() function to handle both numbers and variables.

// Get the value of a number or a variable.

void parser::atom(double &result)

{

switch(tok_type) {

case VARIABLE:

result = find_var(token);

get_token();

return;

case NUMBER:

result = atof(token);

get_token();

return;

default:

serror(0);

}

}

C h a p t e r 4 0 : A n O b j e c t - O r i e n t e d E x p r e s s i o n P a r s e r

975

Technically, these additions are all that is needed for the parser to use variables

correctly; however, there is no way for these variables to be assigned a value. Often this

is done outside the parser, but you can treat the equal sign as an assignment operator

(which is how it is handled in C++) and make it part of the parser. There are various

ways to do this. One method is to add another function, called

eval_exp1() , to the

parser

it, not

class. This function will now begin the recursive-descent chain. This means thateval_exp2() , must be called by eval_exp() to begin parsing the expression.

eval_exp1()

is shown here:

// Process an assignment.

void parser::eval_exp1(double &result)

{

int slot;

char ttok_type;

char temp_token[80];

if(tok_type==VARIABLE) {

// save old token

strcpy(temp_token, token);

ttok_type = tok_type;

// compute the index of the variable

slot = toupper(*token) - 'A';

get_token();

if(*token != '=') {

putback(); // return current token

// restore old token - not assignment

strcpy(token, temp_token);

tok_type = ttok_type;

}

else {

get_token(); // get next part of exp

eval_exp2(result);

vars[slot] = result;

return;

}

}

eval_exp2(result);

}

976

C + + : T h e C o m p l e t e R e f e r e n c e

As you can see, the function needs to look ahead to determine whether an

assignment is actually being made. This is because a variable name always precedes an

assignment, but a variable name alone does not guarantee that an assignment

expression follows. That is, the parser will accept A = 100 as an assignment, but is also

smart enough to know that A/10 is not. To accomplish this,

token from the input stream. If it is not an equal sign, the token is returned to the input

stream for later use by calling

included in the

eval_exp1() reads the nextputback() . The putback() function must also beparser class. It is shown here:

// Return a token to the input stream.

void parser::putback()

{

char *t;

t = token;

for(; *t; t++) exp_ptr--;

}

After making all the necessary changes, the parser will now look like this.

/* This module contains the recursive descent

parser that recognizes variables.

*/

#include <iostream>

#include <cstdlib>

#include <cctype>

#include <cstring>

using namespace std;

enum types { DELIMITER = 1, VARIABLE, NUMBER};

const int NUMVARS = 26;

class parser {

char *exp_ptr; // points to the expression

char token[80]; // holds current token

char tok_type; // holds token's type

double vars[NUMVARS]; // holds variables' values

void eval_exp1(double &result);

void eval_exp2(double &result);

C h a p t e r 4 0 : A n O b j e c t - O r i e n t e d E x p r e s s i o n P a r s e r

977

void eval_exp3(double &result);

void eval_exp4(double &result);

void eval_exp5(double &result);

void eval_exp6(double &result);

void atom(double &result);

void get_token();

void putback();

void serror(int error);

double find_var(char *s);

int isdelim(char c);

public:

parser();

double eval_exp(char *exp);

};

// parser constructor

parser::parser()

{

int i;

exp_ptr = NULL;

for(i=0; i<NUMVARS; i++) vars[i] = 0.0;

}

// Parser entry point.

double parser::eval_exp(char *exp)

{

double result;

exp_ptr = exp;

get_token();

if(!*token) {

serror(2); // no expression present

return 0.0;

}

eval_exp1(result);

if(*token) serror(0); // last token must be null

return result;

}

978

C + + : T h e C o m p l e t e R e f e r e n c e

// Process an assignment.

void parser::eval_exp1(double &result)

{

int slot;

char ttok_type;

char temp_token[80];

if(tok_type==VARIABLE) {

// save old token

strcpy(temp_token, token);

ttok_type = tok_type;

// compute the index of the variable

slot = toupper(*token) - 'A';

get_token();

if(*token != '=') {

putback(); // return current token

// restore old token - not assignment

strcpy(token, temp_token);

tok_type = ttok_type;

}

else {

get_token(); // get next part of exp

eval_exp2(result);

vars[slot] = result;

return;

}

}

eval_exp2(result);

}

// Add or subtract two terms.

void parser::eval_exp2(double &result)

{

register char op;

double temp;

eval_exp3(result);

while((op = *token) == '+' || op == '-') {

get_token();

C h a p t e r 4 0 : A n O b j e c t - O r i e n t e d E x p r e s s i o n P a r s e r

979

eval_exp3(temp);

switch(op) {

case '-':

result = result - temp;

break;

case '+':

result = result + temp;

break;

}

}

}

// Multiply or divide two factors.

void parser::eval_exp3(double &result)

{

register char op;

double temp;

eval_exp4(result);

while((op = *token) == '*' || op == '/' || op == '%') {

get_token();

eval_exp4(temp);

switch(op) {

case '*':

result = result * temp;

break;

case '/':

result = result / temp;

break;

case '%':

result = (int) result % (int) temp;

break;

}

}

}

// Process an exponent

void parser::eval_exp4(double &result)

{

double temp, ex;

register int t;

980

C + + : T h e C o m p l e t e R e f e r e n c e

eval_exp5(result);

if(*token== '^') {

get_token();

eval_exp4(temp);

ex = result;

if(temp==0.0) {

result = 1.0;

return;

}

for(t=(int)temp-1; t>0; --t) result = result * (double)ex;

}

}

// Evaluate a unary + or -.

void parser::eval_exp5(double &result)

{

register char op;

op = 0;

if((tok_type == DELIMITER) && *token=='+' || *token == '-') {

op = *token;

get_token();

}

eval_exp6(result);

if(op=='-') result = -result;

}

// Process a parenthesized expression.

void parser::eval_exp6(double &result)

{

if((*token == '(')) {

get_token();

eval_exp2(result);

if(*token != ')')

serror(1);

get_token();

}

else atom(result);

}

// Get the value of a number or a variable.

void parser::atom(double &result)

C h a p t e r 4 0 : A n O b j e c t - O r i e n t e d E x p r e s s i o n P a r s e r

981

{

switch(tok_type) {

case VARIABLE:

result = find_var(token);

get_token();

return;

case NUMBER:

result = atof(token);

get_token();

return;

default:

serror(0);

}

}

// Return a token to the input stream.

void parser::putback()

{

char *t;

t = token;

for(; *t; t++) exp_ptr--;

}

// Display a syntax error.

void parser::serror(int error)

{

static char *e[]= {

"Syntax Error",

"Unbalanced Parentheses",

"No expression Present"

};

cout << e[error] << endl;

}

// Obtain the next token.

void parser::get_token()

{

register char *temp;

tok_type = 0;

temp = token;

982

C + + : T h e C o m p l e t e R e f e r e n c e

*temp = '\0';

if(!*exp_ptr) return; // at end of expression

while(isspace(*exp_ptr)) ++exp_ptr; // skip over white space

if(strchr("+-*/%^=()", *exp_ptr)){

tok_type = DELIMITER;

// advance to next char

*temp++ = *exp_ptr++;

}

else if(isalpha(*exp_ptr)) {

while(!isdelim(*exp_ptr)) *temp++ = *exp_ptr++;

tok_type = VARIABLE;

}

else if(isdigit(*exp_ptr)) {

while(!isdelim(*exp_ptr)) *temp++ = *exp_ptr++;

tok_type = NUMBER;

}

*temp = '\0';

}

// Return true if c is a delimiter.

int parser::isdelim(char c)

{

if(strchr(" +-/*%^=()", c) || c==9 || c=='\r' || c==0)

return 1;

return 0;

}

// Return the value of a variable.

double parser::find_var(char *s)

{

if(!isalpha(*s)){

serror(1);

return 0.0;

}

return vars[toupper(*token)-'A'];

}

C h a p t e r 4 0 : A n O b j e c t - O r i e n t e d E x p r e s s i o n P a r s e r

983

To try the enhanced parser, you may use the same

for the simple parser. With the enhanced parser, you can now enter expressions like

A = 10/4

A – B

C = A * (F – 21)

main() function that you used

Syntax Checking in a Recursive-Descent Parser

Before moving on to the template version of the parser, let's briefly look at syntax

checking. In expression parsing, a syntax error is simply a situation in which the input

expression does not conform to the strict rules required by the parser. Most of the time,

this is caused by human error, usually typing mistakes. For example, the following

expressions are not valid for the parsers in this chapter:

10 ** 8

(10 – 5) * 9)

/8

The first contains two operators in a row, the second has unbalanced parentheses, and

the last has a division sign at the start of an expression. None of these conditions is

allowed by the parsers. Because syntax errors can cause the parser to give erroneous

results, you need to guard against them.

As you studied the code of the parsers, you probably noticed the

which is called under certain situations. Unlike many other parsers, the

recursive-descent method makes syntax checking easy because, for the most part, it

occurs in

problem with the syntax checking as it now stands is that the entire parser is not

terminated on syntax error. This can lead to multiple error messages.

The best way to implement the

reset. For example, all C++ compilers come with a pair of companion functions called

serror() function,atom(), find_var(), or eval_exp6() , where parentheses are checked. The onlyserror() function is to have it execute some sort of

setjmp()

and longjmp() . These two functions allow a program to branch to a different

function. Therefore,

program outside the parser.

Depending upon the use you put the parser to, you might also find that C++'s

exception handling mechanism (implemented through

beneficial when handling errors.

If you leave the code the way it is, multiple syntax-error messages may be issued.

This can be an annoyance in some situations but a blessing in others because multiple

errors may be caught. Generally, however, you will want to enhance the syntax

checking before using it in commercial programs.

serror() could execute a longjmp() to some safe point in yourtry, catch, and throw) will be

984

C + + : T h e C o m p l e t e R e f e r e n c e

Building a Generic Parser

The two preceding parsers operated on numeric expressions in which all values were

assumed to be of type

double. While this is fine for applications that use double

values, it is certainly excessive for applications that use only integer values, for

example. Also, by hard-coding the type of values being evaluated, the application of

the parser is unnecessarily restricted. Fortunately, by using a class template, it is an

easy task to create a generic version of the parser that can work with any type of data

for which algebraic-style expressions are defined. Once this has been done, the parser

can be used both with built-in types and with numeric types that you create.

Here is the generic version of the expression parser.

// A generic parser.

#include <iostream>

#include <cstdlib>

#include <cctype>

#include <cstring>

using namespace std;

enum types { DELIMITER = 1, VARIABLE, NUMBER};

const int NUMVARS = 26;

template <class PType> class parser {

char *exp_ptr; // points to the expression

char token[80]; // holds current token

char tok_type; // holds token's type

PType vars[NUMVARS]; // holds variable's values

void eval_exp1(PType &result);

void eval_exp2(PType &result);

void eval_exp3(PType &result);

void eval_exp4(PType &result);

void eval_exp5(PType &result);

void eval_exp6(PType &result);

void atom(PType &result);

void get_token(), putback();

void serror(int error);

PType find_var(char *s);

int isdelim(char c);

public:

C h a p t e r 4 0 : A n O b j e c t - O r i e n t e d E x p r e s s i o n P a r s e r

985

parser();

PType eval_exp(char *exp);

};

// parser constructor

template <class PType> parser<PType>::parser()

{

int i;

exp_ptr = NULL;

for(i=0; i<NUMVARS; i++) vars[i] = (PType) 0;

}

// Parser entry point.

template <class PType> PType parser<PType>::eval_exp(char *exp)

{

PType result;

exp_ptr = exp;

get_token();

if(!*token) {

serror(2); // no expression present

return (PType) 0;

}

eval_exp1(result);

if(*token) serror(0); // last token must be null

return result;

}

// Process an assignment.

template <class PType> void parser<PType>::eval_exp1(PType &result)

{

int slot;

char ttok_type;

char temp_token[80];

if(tok_type==VARIABLE) {

// save old token

strcpy(temp_token, token);

ttok_type = tok_type;

chapter designs and implements a small string class. As you know, Standard

C++ provides a full-featured, powerful string class called

purpose of this chapter is not to develop an alternative to this class, but rather to

give you insight into how any new data type can be easily added and integrated into

the C++ environment. The creation of a string class is the quintessential example of this

process. In the past, many programmers honed their object-oriented skills developing

their own personal string classes. In this chapter, we will do the same.

While the example string class developed in this chapter is much simpler than the

one supplied by Standard C++, it does have one advantage: it gives you full control

over how strings are implemented and manipulated. You may find this useful in

certain situations. It is also just plain fun to play with!

3basic_string. The

The StrType Class

Our string class is loosely modeled on the one provided by the standard library. Of

course, it is not as large or as sophisticated. The string class defined here will meet the

following requirements:

Strings may be assigned by using the assignment operator.

Both string objects and quoted strings may be assigned to string objects.

Concatenation of two string objects is accomplished with the + operator.

Substring deletion is performed using the – operator.

String comparisons are performed with the relational operators.

string object.

String objects may be initialized by using either a quoted string or another

storage for each string is dynamically allocated.

Strings must be able to be of arbitrary and variable lengths. This implies that

provided.

Although our string class will, in general, be less powerful than the standard string

class, it does include one feature not defined by

A method of converting string objects to null-terminated strings will bebasic_string: substring deletion via the

–

The class that will manage strings is called

operator.StrType. Its declaration is shown here:

class StrType {

char *p;

int size;

public:

StrType();

932

Chapter 39

Integrating New Classes:

A Custom String Class
C9

e Relational Operators

art Five of this book provides two sample C++ applications.
Chapter 39