Data Structure Exercises

Home Class Info Links

Lectures Newsgroup Assignments

Below are exercises suitable for submission to the Code Critic after reading Chapters 1 through 20 of the textbook. Don't forget the rules of the queue.

The exercises are:

• Expression Parser
• Expression Evaluator OPTIONAL (depends on Expression Parser)
• Object Counter
• Count Sorter (depends on Object Counter)

Note: You can submit the Evaluator or Sorter as soon the prerequisite prior exercise has had an initial review and no major changes are needed.

Exercise: Expression Parser

Relevant Readings: Chapters 20 and 22.4.1.

Use TDD to implement the infix expression parser as described in Exercise 20.12.

Call the project parser.

Modifications and clarifications to the book version:

• Define a Parser class with this public API:
  • Parser() creates a parser instance.
  • Parser & Parser::parse(string s) parses an arithmetic expression in a string, and returns a reference to the parser.
  • string Parser::source() returns the string that was passed in to be parsed
  • string Parser::postfix() returns the postfix representation of the parsed expression
• Use C++ strings, not character arrays.
• Use the standard C++ stack, described in Chapter 22.4.1, not the book code. A simple stack of characters is fine.
• Allow multidigit integers, with optional minus sign (no space following), i.e., a valid input is "123 + 45 * -82" and the output should be "123 45 -82 * +". The input "123 + 45 * - 82" is malformed. You don't need to handled malformed inputs.

For input numbers, you should be able to make use of the number parsing code you wrote for the Dollars class.

Here's an example test:

Parser parser;
CPPUNIT_ASSERT_EQUAL( string( "12 34 56 * +" ), parser.parse( "12 + 34 * 56" ).postfix() );
CPPUNIT_ASSERT_EQUAL( string( "12 34 * 56 +" ), parser.parse( "12 * 34 + 56" ).postfix() );

There should be no printing except for error messages.

Use TDD. Start with the simplest possible expression, just a number, e.g.,

Parser parser;
CPPUNIT_ASSERT_EQUAL( string( "123" ), parser.parse( "123" ).postfix() );

Notice how have parse() return a reference to the parser itself allows us to "chain" a call to postfix() to get the result for testing in one step.

What works, try a simple binary operation, e.g.,

Parser parser;
CPPUNIT_ASSERT_EQUAL( string( "12 + 34", parser.parse( "12 34 +" ).postfix() );

Then try something like "12 + -48" versus "12 - 48" versus "12 - -48" to make sure you can handle minus signs.

Then do simple precedence, such as "12 + 34 * 56" versus "12 * 34 + 56".

Finally, test parenthesized expresssions.

The algorithm given in the book is fine. The part about embedding every input inside a pair of parentheses makes coding a bit simpler. It avoids the need for a special loop to close off all open expressions. But ignore their specific function suggestions. Do what you think leads to clean, modular code.

Submit to Code Critic:

• Your test code, your header code and your implementation code

Clearly label each section of code.

Wrap Up

When the above has been approved via the Code Critic, run make handin.

Email the Zip archive produced by your Makefile with the Subject EECS 211: Expression Parser.

Exercise: Expression Evaluator -- OPTIONAL

Relevant Readings: Chapters 20 and 22.4.1.

Use TDD to implement the postfix expression evaluator as described in Exercise 20.13.

Keep this in your parser project.

Modifications and clarifications to the book version:

• Add to your Parser class the member function int Parser::evaluate(). It should return the value of the arithmetic expression that has been previously parsed.

Here's an example test:

Parser parser;
CPPUNIT_ASSERT_EQUAL( 1916, parser.parse( "12 + 34 * 56" ).evaluate() );
CPPUNIT_ASSERT_EQUAL( 464, parser.parse( "12 * 34 + 56" ).evaluate() );

Internally, the evaluation uses the algorithm described in Exercise. 20.13, with the following modifications:

• Use standard C++ strings, not character arrays. There's no need to add a \0 to a string.
• Use a standard C++ stack of integers for the calculated results.
• Handle multi-digit integers with an optional minus sign.
• Ignore the book's list of functions you might want to define.

Submit to Code Critic:

• Your new test code for the evaluator (not your entire test suite), your header code, and the code you added or modified to do evaluation.

Clearly label each section of code.

Wrap Up

When the above has been approved via the Code Critic, run make handin.

Email the Zip archive produced by your Makefile with the Subject EECS 211: Expression Evaluator.

Exercise: Object Counter

Relevant Readings: Chapter 22 and the STL container notes

Use TDD to develop a simple generic Counter. The class will hold counts of how many times each distinct object occurs in a container. In true generic form, the constructor will take two iterators to specify a range over a container.

Call the project Counter.

Here's an example of using Counter to count numbers and strings from two different kinds of containers:

// Count some integers in an array
int data[ 9 ] = { 2, 2, 3, 4, 1, 2, 1, 3, 3 };
Counter<int> c;
CPPUNIT_ASSERT_EQUAL( 4, c.count( data, data + 9 ) );
CPPUNIT_ASSERT_EQUAL( 2, c.getCount( 1 ) );
CPPUNIT_ASSERT_EQUAL( 3, c.getCount( 2 ) );

// Count strings in an input stream
istringstream in( "b b c d a b a c c" );
istream_iterator start(in);
istream_iterator end;
Counter<string> c;
CPPUNIT_ASSERT_EQUAL( 4, c.count( start, end ) );
CPPUNIT_ASSERT_EQUAL( 2, c.getCount( "a" ) );
CPPUNIT_ASSERT_EQUAL( 3, c.getCount( "b" ) );

Here's the public API:

• the default constructor is all that's needed
• count( start, end ) is a template member function that collects counts for the distinct objects in the range from start up to (but not including) end. start and end should be iterators pointing to locations in the same container.
• size() returns the number of distinct objects counted.
• getCount(T obj) returns the count for obj, or 0 if obj was never seen.
• clear() should clear the internal counts.

size() and getCount() should be constant member functions.

Use a map

You'll have to do almost no work here, except learn how to use the standard map container. The one gotcha is that aMap[key] adds the key to the map if it's not already present. This is what you want when buildin the map, but not when checking to see what it contains. For the latter, you need to use the map::find() member function.

Write a generic algorithm

The book does an OK job showing how the standard containers and algorithms work. But it completely misses the point about how containers are manipulated. All its examples pass the containers to functions. Don't do this. The Counter::count() template member function is more like what you should define: a function that takes start and end iterators. This way, you can count any subrange of any kind of container. There's a long discussion on this in the STL iterator notes.

Tasks

As always, write tests first, and start small. Start with tests to construct a counter for integers (say) and check that the size is 0 and the counts for some test numbers are zero. Run, fail, then code till the tests pass.

Then add a test where you count integers in an array, and check the results, as in the code shown above. Run, fail, code.

Submit to Code Critic:

• Your test and implementation code. Because this is so short, and the main loop is in a template member function, your code may all end up in the header file.

Clearly label each section of code.

Wrap Up

When the above has been approved via the Code Critic, run make handin.

Email the Zip archive produced by your Makefile with the Subject EECS 211: Object Counter.

Exercise: Count Sorter

Relevant Readings: Chapter 22, the STL set notes, and the STL function object notes.

Use TDD to extend the previous code to create a set of object counts sorted from most to least frequent.

Do this in the same Counter project.

Here's an example of what you should be able to do in your test code:

// convenience type
typedef Counter<string> SCtr;

// get some counts
char *data[ 9 ] = { "b", "b", "c", "d", "a", "b", "a", "c", "c" };
SCtr c;
c.count( data, data + 9 );

// this next line makes the sorted set
set<SCtr::value_type, SCtr::CountCompare> s( c.begin(), c.end() );

// test that it worked
CPPUNIT_ASSERT_EQUAL( 4, (int) s.size() );
SCtr::const_iterator iter = s.begin();
CPPUNIT_ASSERT_EQUAL( string( "b" ), iter++->first );
CPPUNIT_ASSERT_EQUAL( string( "c" ), iter++->first );
CPPUNIT_ASSERT_EQUAL( string( "a" ), iter++->first );
CPPUNIT_ASSERT_EQUAL( string( "d" ), iter++->first );
CPPUNIT_ASSERT( s.end() == iter );

To make this work, you need to typedef several public types in Counter, and define the generic function class CountCompare:

• Counter<T>::value_type for the type of the object-count pairs stored in the counter's internal map.
• Counter<T>::const_iterator for the constant iterator over object-count pairs in the internal map.
• Counter<T>::iterator for the constant iterator over object-count pairs in the internal map.
• A function class Counter<T>::CountCompare that defines operator() to take two object-count pairs and return true if the first pair should come before than the second in the set.

For our purposes, an object-count pair should precede another if it has a higher count, or the same count but a lower name, e.g., "abc" is lower than "def."

Figure 22.4 in the book shows the typedef's that the standard containers define. The Counter's types can be easily defined in terms of the internal map's types.

Tasks

As always, write tests first. Then add the typedef's to Counter, and define the function class to make it work.

Submit to Code Critic:

• Your Counter code. Your code may still all be in the header file.

Wrap Up

When the above has been approved via the Code Critic, run make handin.

Email the Zip archive produced by your Makefile with the Subject EECS 211: Counter Sorting.

Comments? Contact the Prof!