Here is an example of a technique for processing a string that can be adapted for use in Project 3.
A service for tourists to a city provides self-guided walking tours that visit points of interest that the tourist selects from a list. If the tourist wants to visit points B, F, and H (the points are coded by capital letters), the service prints a set of instructions (e.g., "Turn right and proceed for 10 blocks. Stop at point of interest F.") The code that takes the requested points and determines an optimal route has already been written, but it produces a route in coded form; our job is to write a function that takes the coded string and prints human-readable instructions.
A coded string looks something like this: 10R3LSH12L5RSB3RSF.
It is a sequence of steps, where each step takes one of three forms, with
an associated meaning
integerRintegerLSletterThe function that we are to write has the following prototype:
bool translateInstructionString(string text);
For each step in the argument string, the function writes a human-readable
instruction. As an example, for the step 10R, the function writes
Turn right and proceed for 10 blocks. If it encounters no errors
in the string, it returns true when it's done; otherwise, it does not finish
processing the string and returns false, possibly after having printed some
instructions before the point where it encountered the error. For example,
if the function is called with the argument 10R3LSH12L5RSB3RSF,
it prints the following and returns true:
Turn right and proceed for 10 blocks. Turn left and proceed for 3 blocks. Stop at point of interest H. Turn left and proceed for 12 blocks. Turn right and proceed for 5 blocks. Stop at point of interest B. Turn right and proceed for 3 blocks. Stop at point of interest F.
Our solution strategy will be to visit the steps of the string from left to right. Pictorially, we'd start like this:
10R3LSH12L5RSB3RSF ^
Examining the indicated character, we see it's a digit. We'll call a function
to process an R or L step, which looks for a
sequence of digits followed by the letter, writes the human-readable
"Turn right" or "Turn left" instruction, and advances the position in the
string, resulting in
10R3LSH12L5RSB3RSF ^
We examine the indicated character, call the same function to process the
3L step, and advance the position, resulting in
10R3LSH12L5RSB3RSF ^
Continuing in this manner, we eventually reach
10R3LSH12L5RSB3RSF ^
We examine the indicated character, process the SF step, and
advance the position, resulting in
10R3LSH12L5RSB3RSF ^
Since we've reached the end of the string, we're done; since we didn't encounter any error, we return true.
The functions to process the various kinds of steps need the coded string and
the current position in the string; when they return, they need to let their
caller know the position in the string just after the step. Also, they may
encounter an error (e.g., digits not followed by R or
L), so they need to indicate that as well. One design is this:
bool processRorLstep(string text, int& pos);
If this function is called with the example string we've been using and a
integer variable k whose value is 7, representing the following
situation:
11111111
012345678901234567
10R3LSH12L5RSB3RSF
^
the function should write "Turn left and proceed for 12 blocks.", set
k to 10, and return true. (Because k is passed by
reference, since the parameter was declared to be of type int&
instead of int, the function can change k.) Setting
k to 10 indicates this:
11111111
012345678901234567
10R3LSH12L5RSB3RSF
^
If the function encounters an error (no R or L after
the digits), it should return false.
Here then is our initial version of translateInstructionString:
bool translateInstructionString(string text) // not the final version
{
int k = 0;
while (k != text.size())
{
// Decide what to do based on start of instruction
if (isdigit(text.at(k)))
{
// Process R or L step, but if it detects an error,
// we're done
if (!processRorLstep(text, k))
return false;
}
else if (text.at(k) == 'S')
{
if (!processSstep(text, k))
return false;
}
else
{
// Not an R, L, or S step, so error
return false;
}
}
// We got through the whole text without error
return true;
}
The easiest function to implement next is processSstep:
bool processSstep(string text, int& pos)
{
// When this function is called we know text.at(pos) is 'S',
// so advance to the next position
pos++;
// If there is no character after the S, error
if (pos == text.size())
return false;
// Points of interest are indicated by upper case letters
if (!isupper(text.at(pos)))
return false;
// Everything's OK. Write message and advance position
cout << "Stop at point of interest " << text.at(pos) << "." << endl;
pos++;
return true;
}
Here is processRorLstep:
bool processRorLstep(string text, int& pos)
{
// Get distance. We know text.at(pos) is a digit
string distance;
for (distance = ""; isdigit(text.at(pos)); pos++)
distance += text.at(pos);
// We're past the digits, so check direction
if (text.at(pos) != 'R' && text.at(pos) != 'L')
return false;
// Everything's OK. Write message
cout << "Turn ";
if (text.at(pos) == 'R')
cout << "right";
else
cout << "left";
cout << " and proceed for " << distance << " blocks." << endl;
// Advance position
pos++;
return true;
}
Here's one way to test our code:
int main()
{
for (;;)
{
cout << "Enter coded string (or just hit Enter to quit): ";
string coded;
getline(cin, coded);
if (coded == "")
break;
if (!translateInstructionString(coded))
cout << " *** There is an error in the string! ***" << endl;
}
}