The C++Course provides a general introduction to programming in C++. It is based on A.B. Downey's book, How to Think Like a Computer Scientist. Click here for details.

Home Stacks Parsing
 
del.icio.us Reddit Facebook StumbleUpon MySpace Twitter

Parsing

In order to implement the algorithm from the previous section, we need to be able to traverse a string and break it into operands and operators. This process is an example of parsing

If we were to break the string up into smaller parts, we would need a specific character to use as a boundary between the chucks. A character that marks a boundary is called a delimiter.

So let's quickly build a parsing function that will store the various chunks of a pstring into a pvector<pstring>.

pvector<pstring> parse(pstring string, char delim) {

  pvector<pstring> stringParsed;

  if (string.length() == 0)
    return stringParsed.resize(0);

  for (int i = 0, j = 0; i < string.length(); i++)
  {
    if (string[i] != delim || string[i] != '\n')
      stringParsed[j] += string[i];
    else
    {
      cout << stringParsed[j] << endl;
      j++;
      stringParsed.resize(j+1);
    }
  }

  return stringParsed;
}

The function above accepts a pstring to be parsed and a char to be used as a delimiter, so that whenever the delim character appears in the string, the chunk is saved as a new pstring element in the pvector<pstring>.

Passing a string through the function with a space delimiter would look like this:

  pstring string = "Here are four tokens.";

  pvector<pstring> = parse(string, ' ');

The output of the parser is:

Here
are
four
tokens.

For parsing expressions, we have the option of specifying additional characters that will be used as delimiters:

bool checkDelim(char ch, pstring delim) {

  for (int i = 0; i < delim.length(); i++)
  {
    if (ch == delim[i])
      return true;
  }
  return false;
}

pvector<pstring> parse(pstring string, pstring delim) {

  pvector<pstring> stringParsed;

  if (string.length() == 0)
    return stringParsed.resize(0);

  for (int i = 0, j = 0; i < string.length(); i++)
  {
    if (!checkDelim(string[i], delim) || string[i] != '\n')
      stringParsed[j] += string[i];
    else
    {
      cout << stringParsed[j] << endl;
      j++;
      stringParsed.resize(j+1);
    }
  }

  return stringParsed;
}

An example of using the above functions can be seen below:Using the above functions would

    pstring string = "11 22+33*";
    pstring delim = " +-*/";
    pvector<pstring> stringParsed = parse(string, delim);

The new function checkDelim checks for whether or not a given char is a delimiter. Now the output is:

11
22
33

Home Stacks Parsing

Last Update: 2005-12-05