EECS 211
Data Structure Exercises

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:

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:

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:

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:

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:

Submit to Code Critic:

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:

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:

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:

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:

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? comment icon Contact the Prof!

Valid HTML 4.01 Transitional