Beginning Visual C++ 2005 (2006) [eng]

More about Program Structure

How the Function Functions

You first declare a local double variable, value, in which you’ll accumulate the value of the current term. Because a term must contain at least one number, the first action in the function is to obtain the value of the first number by calling the number() function and storing the result in value. You implicitly assume that the function number()accepts the string and an index to a position in the string as arguments, and returns the value of the number found. Because the number() function must also update the index to the string to the position after the number that was found, you’ll again specify the second parameter as a reference when you come to define that function.

The rest of the term() function is a while loop that continues as long as the next character is ‘*’ or ‘/’. Within the loop, if the character found at the current position is ‘*’, you increment the variable index to position it at the beginning of the next number, call the function number() to get the value of the next number, and then multiply the contents of value by the value returned. In a similar manner, if the current character is ‘/‘, you increment the index variable and divide the contents of value by the value returned from number(). Because the function number() automatically alters the value of the variable index to the character following the number found, index is already set to select the next available character in the string on the next iteration.

The loop terminates when a character other than a multiply or divide operator is found, whereupon the current value of the term accumulated in the variable value is returned to the calling program.

The last analytical function that you require is number(), which determines the numerical value of any number appearing in the string.

Analyzing a Number

Based on the way you have used the number() function within the term() function, you need to declare it with this prototype:

double number(char* str, int& index); // Function to recognize a number

The specification of the second parameter as a reference allows the function to update the argument in the calling program directly, which is what you require.

You can make use of a function provided in a standard C++ library here. The <cctype> header file provides definitions for a range of functions for testing single characters. These functions return values of type int where positive values corresponding to true and zero corresponds to false. Four of these functions are shown in the following table:

Functions in the <cctype>	Header for Testing Single Characters
int isalpha(int c)	Returns true if the argument is alphabetic, false otherwise.
int isupper(int c)	Returns true if the argument is an upper case letter, false
	otherwise.
int islower(int c)	Returns true if the argument is a lower case letter, false
	otherwise.
int isdigit(int c)	Returns true if the argument is a digit, false otherwise.

299

Chapter 6

There are also a number of other functions provided by <cctype>, but I won’t grind through all the detail. If you’re interested, you can look them up in the MSDN Library Help. A search on “is routines” should find them.

You only need the last of the functions shown above in the program. Remember that isdigit() is testing a character, such as the character ‘9’ (ASCII character 57 in decimal notation) for instance, not a numeric 9, because the input is a string.

You can define the function number() as follows:

// Function to recognize a number in a string
double number(char* str, int& index)
{
double value = 0.0;	// Store the resulting value
while(isdigit(*(str + index)))	// Loop accumulating leading digits
value = 10*value + (*(str + index++) - ‘0’);
	// Not a digit when we get to here
if(*(str + index) != ‘.’)	// so check for decimal point
return value;	// and if not, return value
double factor = 1.0;	// Factor for decimal places
while(isdigit(*(str + (++index))))	// Loop as long as we have digits
{
factor *= 0.1;	// Decrease factor by factor of 10
value = value + (*(str + index) - ‘0’)*factor;		// Add decimal place
}
return value;	// On loop exit we are done
}

How the Function Functions

You declare the local variable value as type double that holds the value of the number that is found. You initialize it with 0.0 because you add in the digit values as you go along.

As the number in the string is a series of digits as ASCII characters, the function steps through the string accumulating the value of the number digit by digit. This occurs in two phases — the first phase accumulates digits before the decimal point; then if you find a decimal point, the second phase accumulates the digits after it.

The first step is in the while loop that continues as long as the current character selected by the variable index is a digit. The value of the digit is extracted and added to the variable value in the loop statement:

value = 10*value + (*(str + index++) - ‘0’);

300

More about Program Structure

The way this is constructed bears a closer examination. A digit character has an ASCII value between 48, corresponding to the digit 0, and 57 corresponding to the digit 9. Thus, if you subtract the ASCII code for ‘0’ from the code for a digit, you convert it to its equivalent numeric digit value from 0 to 9. You have parentheses around the subexpression *(str + index++) - ‘0’; these are not essential, but they do make what’s going on a little clearer. The contents of the variable value are multiplied by 10 to shift the value one decimal place to the left before adding in the digit value because you’ll find digits from left to right — that is, the most significant digit first. This process is illustrated in Figure 6-6.

		digits in number
		5	1	3
ASCII codes as decimal values		53	49	51
	Intial value = 0
1st digit	value = 10*value + (53 - 48)
	= 10*0.0 + 5
	= 5.0
2nd digit	value = 10*value + (49 - 48)
	= 10*5.0 + 1
	= 51.0
3rd digit	value = 10*value + (51 - 48)
	= 10*51.0 + 3
	= 513.0

Figure 6-6

As soon as you come across something other than a digit, it is either a decimal point or something else. If it’s not a decimal point, you’ve finished, so you return the current contents of the variable value to the calling program. If it is a decimal point, you accumulate the digits corresponding to the fractional part of the number in the second loop. In this loop, you use the factor variable, which has the initial value 1.0, to set the decimal place for the current digit, and consequently factor is multiplied by 0.1 for each digit found. Thus, the first digit after the decimal point is multiplied by 0.1, the second by 0.01, the third by 0.001, and so on. This process is illustrated in Figure 6-7.

301

Chapter 6

				digits in integral					digits in fractional
					part of number				part of number
				5		1	3	.	6		0	8
ASCII codes as decimal values
					53	49	51	46	54		49	56
Before the decimal point
value = 513.0
factor = 1.0
	factor = 0.1*factor
1st digit	value = value + factor*(54 - 48)
	= 513.0 + 0.1*6
	= 513.6

	factor = 0.1*factor
2nd digit	value = value + factor*(49 - 48)
	= 513.6 + 0.01*0
	= 513.60
	factor = 0.1*factor
3rd digit	value = value + factor*(56 - 48)
	= 513.60 + 0.001*8
	= 513.608
Figure 6-7

As soon as you find a non-digit character, you are done, so after the second loop you return the value of the variable value. You almost have the whole thing now. You just need a main() function to read the input and drive the process.

Putting the Program Together

You can collect the #include statements together and assemble the function prototypes at the beginning of the program for all the functions used in this program:

//Ex6_09.cpp

//A program to implement a calculator

#include <iostream>	// For stream input/output
#include <cstdlib>	// For the exit() function
#include <cctype>	// For the isdigit() function
using std::cin;
using std::cout;
using std::endl;
void eatspaces(char* str);	// Function to eliminate blanks
double expr(char* str);	// Function evaluating an expression
double term(char* str, int& index);	// Function analyzing a term
double number(char* str, int& index);	// Function to recognize a number
const int MAX = 80;	// Maximum expression length,
	// including ‘\0’

302

More about Program Structure

You have also defined a global variable MAX, which is the maximum number of characters in the expression processed by the program (including the terminating ‘\0’ character.

Now you can add the definition of the main() function and your program is complete. The main() function should read a string and exit if it is empty; otherwise, call the function expr() to evaluate the input and display the result. This process should repeat indefinitely. That doesn’t sound too difficult, so let’s give it a try.

int main()
{
char buffer[MAX] = {0};	// Input area for expression to be evaluated

cout << endl

<<“Welcome to your friendly calculator.”

<<endl

<<“Enter an expression, or an empty line to quit.”

<<endl;

for(;;)

{
cin.getline(buffer, sizeof buffer);	// Read an input line
eatspaces(buffer);	// Remove blanks from input
if(!buffer[0])	// Empty line ends calculator
return 0;
cout << “\t= “ << expr(buffer)	// Output value of expression
<< endl << endl;
}

}

How the Function Functions

In main(), you set up the char array buffer to accept an expression up to 80 characters long (including the string termination character). The expression is read within the indefinite for loop using the getline() input function and after obtaining the input, spaces are removed from the string by calling the function eatspaces().

All the other things that the function main() provides for are within the loop. They are to check for an empty string, which consists of just the null character, ‘\0’, in which case the program ends, and to output the value of the string produced by the function expr().

After you type all the functions, you should get output similar to the following:

2 * 35

= 70

2/3 + 3/4 + 4/5 + 5/6 + 6/7

=3.90714

1 + 2.5 + 2.5*2.5 + 2.5*2.5*2.5

=25.375

You can enter as many calculations as you like, and when you are fed up with it, just press Enter to end the program.

303

Chapter 6

Extending the Program

Now that you have got a working calculator, you can start to think about extending it. Wouldn’t it be nice to be able to handle parentheses in an expression? It can’t be that difficult, can it? Let’s give it a try.

Think about the relationship between something in parentheses that might appear in an expression and the kind of expression analysis that you have made so far. Look at an example of the kind of expression you want to handle:

2*(3 + 4) / 6 - (5 + 6) / (7 + 8)

Notice that the expressions in parentheses always form part of a term in your original parlance. Whatever sort of computation you come up with, this is always true. In fact, if you could substitute the value of the expressions within parentheses back into the original string, you would have something that you can already deal with. This indicates a possible approach to handling parentheses. You might be able to treat an expression in parentheses as just another number, and modify the function number() to sort out the value of whatever appears between the parentheses.

That sounds like a good idea, but ‘sorting out’ the expression in parentheses requires a bit of thought: the clue to success is in the terminology used here. An expression that appears within parentheses is a perfectly good example of a full-blown expression, and you already have the expr() function that will return the value of an expression. If you can get the number() function to work out what the contents of the parentheses are and extract those from the string, you could pass the substring that results to the expr() function, so recursion would really simplify the problem. What’s more, you don’t need to worry about nested parentheses. Because any set of parentheses contains what you have defined as an expression, they are taken care of automatically. Recursion wins again.

Take a stab at rewriting the number() function to recognize an expression between parentheses.

//Function to recognize an expression in parentheses

//or a number in a string

double number(char* str, int& index)
{
double value = 0.0;	// Store the resulting value
if(*(str + index) == ‘(‘)	// Start of parentheses
{
char* psubstr = 0;	// Pointer for substring
psubstr = extract(str, ++index);	// Extract substring in brackets
value = expr(psubstr);	// Get the value of the substring
delete[]psubstr;	// Clean up the free store
return value;	// Return substring value
}
while(isdigit(*(str + index)))	// Loop accumulating leading digits
value = 10*value + (*(str + index++) - 48);
	// Not a digit when we get to here
if(*(str + index)!= ‘.’)	// so check for decimal point
return value;	// and if not, return value
double factor = 1.0;	// Factor for decimal places
while(isdigit(*(str + (++index))))	// Loop as long as we have digits
{

304

	More about Program Structure
factor *= 0.1;	// Decrease factor by factor of 10
value = value + (*(str + index) - 48)*factor; // Add decimal place
}
return value;	// On loop exit we are done

}

This is not yet complete, because you still need the extract() function, but you’ll fix that in a moment.

How the Function Functions

Look how little has changed to support parentheses. I suppose it is a bit of a cheat because you use a function (extract()) that you haven’t written yet, but for one extra function you get as many levels of nested parentheses as you want. This really is icing on the cake, and it’s all down to the magic of recursion!

The first thing that the function number() does now is to test for a left parenthesis. If it finds one, it calls another function, extract() to extract the substring between the parentheses from the original string. The address of this new substring is stored in the pointer psubstr, so you then apply the expr() function to the substring by passing this pointer as an argument. The result is stored in value, and after releasing the memory allocated on the free store in the function extract() (as you will eventually implement it), you return the value obtained for the substring as though it were a regular number. Of course, if there is no left parenthesis to start with, the function number() continues exactly as before.

Extracting a Substring

You now need to write the function extract(). It’s not difficult, but it’s also not trivial. The main complication comes from the fact that the expression within parentheses may also contain other sets of parentheses, so you can’t just go looking for the first right parenthesis you can find. You must watch out for more left parentheses as well, and for every one you find, ignore the corresponding right parenthesis. You can do this by maintaining a count of left parentheses as you go along, adding one to the count for each left parenthesis you find. If the left parenthesis count is not zero, you subtract one for each right parenthesis. Of course, if the left parenthesis count is zero and you find a right parenthesis, you’re at the end of the substring. The mechanism for extracting a parenthesized substring is illustrated in Figure 6-8.

Finding ')' with the '(' count at zero Signals start of substring indicates the end of the parenthesized

substring has been reached

Original expression string

	(	2	+	3	*	(	5	-	2	)				/		2	*	(	1	1	+	9	)	)
'(' count: 0 0			0 0		0 1 1			1 1		0			0 0				0 1 1			1	1 1		0
											copy												r	eplace
																							with '\0'
		2	+	3	*	(	5	-	2	)				/		2	*	(	1	1	+	9	)	\0

Substring that was between parentheses

Figure 6-8

305

Chapter 6

Because the string you extract here contains subexpressions enclosed within parentheses, eventually extract() is called again to deal with those.

The function extract()also needs to allocate memory for the substring and return a pointer to it. Of course, the index to the current position in the original string needs to end up selecting the character following the substring, so the parameter for that needs to be specified as a reference. The prototype of extract(), therefore, is as follows:

char* extract(char* str, int& index); //Function to extract a substring

You can now have a shot at the definition of the function.

//Function to extract a substring between parentheses

//(requires <cstring> header file)

char* extract(char* str, int& index)
{
char buffer[MAX];	// Temporary space for substring
char* pstr = 0;	// Pointer to new string for return
int numL = 0;	// Count of left parentheses found
int bufindex = index;	// Save starting value for index

do

{

buffer[index - bufindex] = *(str + index); switch(buffer[index - bufindex])

{

case ‘)’: if(numL == 0)

{

buffer[index - bufindex] = ‘\0’; // Replace ‘)’ with ‘\0’ ++index;

pstr = new char[index - bufindex]; if(!pstr)

{

cout << “Memory allocation failed,” << “ program terminated.”;

exit(1);

}

strcpy_s(pstr, index-bufindex, buffer); // Copy substring to new memory return pstr; // Return substring in new memory

}

else

numL--; // Reduce count of ‘(‘ to be matched break;

case ‘(‘:

numL++; // Increase count of ‘(‘ to be // matched

break;

}

306

More about Program Structure

} while(*(str + index++) != ‘\0’); // Loop - don’t overrun end of string

cout << “Ran off the end of the expression, must be bad input.” << endl;

exit(1); return pstr;

}

How the Function Functions

You declare a char array to temporarily hold the substring. You don’t know how long the substring will be, but it can’t be more than MAX characters. You can’t return the address of buffer to the calling function because it is local and will be destroyed on exit from the function; therefore, you need to allocate some memory on the free store when you know how long the string is. You do this by declaring a variable pstr of type ‘pointer to char’, which you return by value when you have the substring safe and sound in the free store memory.

You declare a counter numL to keep track of left parentheses in the substring (as I discussed earlier). The initial value of index (when the function begins execution) is stored in the variable bufindex. You use this in combination with incremented values of index to index the array buffer.

The executable part of the function is basically one big do-while loop. The substring is copied from str to buffer one character on each loop iteration, with a check for left or right parentheses during each cycle. If a left parenthesis is found, numL is incremented, and if a right parenthesis is found and numL is non-zero, it is decremented. When you find a right parenthesis and numL is zero, you have found the end of the substring. The ‘)’ in the substring in buffer is then replaced by ‘\0’, and sufficient memory is obtained on the free store to hold the substring. The substring in buffer is then copied to the memory you obtained through the operator new by using the strcpy_s() function that is declared in the <cstring> header file; this is a safe version of the old strcpy() function that is declared in the same header. This function copies the string specified by the third argument, buffer, to the address specified by the first argument, pstr. The second argument is the length of the destination string, pstr.

If you fall through the bottom of the loop, it means that you hit the ‘\0’ at the end of the expression in str without finding the complementary right bracket, so you display a message and terminate the program.

Running the Modified Program

After replacing the number() function in the old version of the program, adding the #include statement for <cstring>, and incorporating the prototype and the definition for the new extract() function you have just written, you’re ready to roll with an all-singing, all-dancing calculator. If you have assembled all that without error, you can get output something like this:

Welcome to your friendly calculator.

Enter an expression, or an empty line to quit. 1/(1+1/(1+1/(1+1)))

= 0.6

(1/2-1/3)*(1/3-1/4)*(1/4-1/5) = 0.000694444

3.5*(1.25-3/(1.333-2.1*1.6))-1

307

Chapter 6

= 8.55507

2,4-3.4

Arrrgh!*#!! There’s an error

The friendly and informative error message in the last output line is due to the use of the comma instead of the decimal point in the expression above it, in what should be 2.4. As you can see, you get nested parentheses to any depth with a relatively simple extension of the program, all due to the amazing power of recursion.

C++/CLI Programming

Just about everything discussed so far in relation to functions for native C++ applies equally well to C++/CLI language code with the proviso that parameter types and return types will be fundamental types, which as you know are equivalent to value class types in a CLR program, tracking handle types, or tracking reference types. Because you cannot perform arithmetic on the address stored in a tracking handle, the coding techniques that I demonstrated for treating parameters that are native C++ arrays as pointers on which you can perform arithmetic operations do not apply to C++/CLI arrays. Many of the complications that can arise with arguments to native C++ functions disappear, but there is still the odd trap in C++/CLI for the unwary. A CLR version of the calculator can help you understand how functions look written in C++/CLI.

The throw and catch mechanism for exceptions works the same in CLR programs as it does in native C++ programs, but there are some differences. The exceptions that you throw in a C++/CLI program must always be thrown using tracking handles. Consequently you should always be throwing exception objects and as far as possible you should avoid throwing literals, especially string literals. For example, consider this try-catch code:

try

{

throw L”Catch me if you can.”;

}

catch(String^ ex) // The exception will not be caught by this

{

Console::WriteLine(L”String^: {0}”,ex);

}

The catch block cannot catch the object thrown here, because the throw statement throws an exception of type const wchar_t*, not of type String^. To catch the exception as thrown, the catch block needs to be:

try

{

throw L”Catch me if you can.”;

}

catch(const wchar_t* ex) // OK. The exception thrown is of this type

{

String^ exc = gcnew String(ex); Console::WriteLine(L”wchar_t:{0}”, exc);

}

308