Daily Archives: September 20, 2014

C++, Programming

Accelerated C++ Solution to Exercise 7-3

3 Comments

Exercise 7-3

The cross-reference program from S7.3/126 could be improved: As it stands, if a word occurs more than once on the same input line, the porgram will report that line multiple times. Change the code so that it detects multiple occurences of the same line number and inserts the line number only once.

Background

Remember that when we run the Chapter 7 cross-reference program (i.e. Solution to Exercise 7-0 (Part 2 / 3) ), we have the following test results:

apple orange banana
orange orange
apple banana
mango
^Z
apple occurs on line(s): 1, 3
banana occurs on line(s): 1, 3
mango occurs on line(s): 4
orange occurs on line(s): 1, 2, 2

Note:

  1. Recall that the xref program assumes the first line as line 1 (instead of 0), second line as line 2 (instead of 1). This is as designed.
  2. The word “orange” appears on line 2 twice. So when it comes to being displayed in the summary, it shows the line number “2” twice.
  3. The objective of this exercise is to only store non-duplicated line number.

Solution Strategy

We only need to make a very small enhancement – to adjust the xref function by adding a small bit of code. Include a if condition to check whether the line number already exists for the corresponding associative array. Use the find utility of the <algorithm> directive to help us do this.

The Project

We can reuse the entire project as per Solution to Exercise 7-0 (Part 2 / 3). Simply replace the xref.cpp file with this new one:

xref.cpp


#include <iostream>   // std::cin, std::istream
#include <map>        // std::map
#include <string>     // std::string
#include <vector>     // std::vector
#include <algorithm>  // std::find
#include "split.h"    // split


using std::cin;
using std::map;
using std::string;
using std::vector;
using std::istream;
using std::find;

// Find all the lines that refer to each word in the input
// In this program, the first line is represented by line 1,
// second line is represented by line 2, etc.
// (S7.3/126)
// Adjusted as per Exercise 7-3: store only non-duplicated line numbers.
map<string, vector<int> >
xref(istream& in, vector<string> find_words(const string&) = split)
{
  string line;
  int line_number = 0;
  map<string, vector<int> > ret;  // map string to vector<int>

  // Read the next line
  while (getline(in, line)) {
    ++line_number;

    // Break the input line into words
    vector<string> words = find_words(line);

    // remember that each word occurs on the current line
    for (vector<string>::const_iterator it = words.begin();
         it != words.end(); ++it) {

      // store only non-duplicated line numbers.
      if ( find( ret[*it].begin(), ret[*it].end(), line_number) == ret[*it].end() )
        ret[*it].push_back(line_number);
    }
  }

  return ret;
}

Test Program

Re-submitting the program with the same input, the program now produces non-duplicated line numbers per associative array (word).

apple orange banana
orange orange
apple banana
mango
^Z
apple occurs on line(s): 1, 3
banana occurs on line(s): 1, 3
mango occurs on line(s): 4
orange occurs on line(s): 1, 2

Reference

Koenig, Andrew & Moo, Barbara E., Accelerated C++, Addison-Wesley, 2000
C++, Programming

Accelerated C++ Solution to Exercise 7-2

Exercise 7-2

Extend the program in S4.2.3/64 to assign letter grades by ranges:

A 90-100
B 80-89.99...
C 70-79.99...
D 60-69.99...
F < 60

Solution

The strategy:

  1. Make a copy of the entire projects from Solution to Exercise 4-0. (i.e. the sample programs in Chapter 4 of the textbook).
  2. Write a new home-made getLetterGrade function that returns a string letterGrade given an input (numeric) double grade, using if/else condition.
  3. In the main program, use the getletterGrade function to compute the student’s string letterGrade. Have an associative array letterGradeCount that maps a string (letter grade) to integer (to keep track of letter grade occurrences).

The Program

Here summarises the entire Code::Block Project, including the header and source files.

Acpp7p2MgntTree

Source File List

Header File List

Source Files

main.cpp


#include <algorithm>
#include <iomanip>
#include <ios>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>
#include <map>
#include "grade.h"
#include "Student_info.h"
#include "getLetterGrade.h"

using std::cin;
using std::cout;
using std::endl;
using std::domain_error;
using std::max;
using std::setprecision;
using std::sort;
using std::streamsize;
using std::string;
using std::vector;
using std::map;

int main()
{
  vector<Student_info> students;
  Student_info record;
  string::size_type maxlen = 0;   // the length of the longest name

  // read and store all the student's data.
  // Invariant:   students contain all the student records read so far
  //              maxlen contains the length of the longest name in students
  while (read(cin, record))
  {
    // find the length of longest name
    maxlen = max(maxlen, record.name.size());
    students.push_back(record);
  }

  // alphabetize the student records
  sort(students.begin(), students.end(), compare);

  // write the names and grades
  map<string, int> letterGradeCount;   // To store letter grade occurrences.
  for (vector<Student_info>::size_type i = 0;
       i != students.size(); ++i)
  {
    //write the name, padded on teh right to maxlen + 1 characters
    cout << students[i].name
         << string(maxlen + 1 - students[i].name.size(), ' ');

     //compute and write the grade
    try
    {
      double final_grade = grade(students[i]);
      string letterGrade = getLetterGrade(final_grade);
      letterGradeCount[letterGrade]++;         // Count Letter Grades.
      streamsize prec = cout.precision();
      cout << setprecision(3) << final_grade
           << setprecision(prec) << " (" << letterGrade << ")";
    }
    catch (domain_error e)
    {
      cout << e.what();
    }
    cout << endl;
  }
  // Display letter grade summary
  cout << "\nLetter Grade Summary" << endl;
  for (map<string, int>::const_iterator i = letterGradeCount.begin();
      i != letterGradeCount.end(); ++i)
    cout << i->first << ": " << i->second << endl;

  return 0;
}

getletterGrade.cpp


#include <string>

using std::string;

// Convert a numeric grade into a letter grade.
// (For Exercise 7-2)
string getLetterGrade(double grade) {

  string ret;

  if (grade >= 90.0)
    ret = "A";
  else if (grade >= 80.0 && grade < 90.0)
    ret = "B";
  else if (grade >= 70.0 && grade < 80.0)
    ret = "C";
  else if (grade >= 60.0 && grade < 70.0)
    ret = "D";
  else
    ret = "F";

  return ret;
}

grade.cpp


#include <stdexcept>
#include <vector>
#include "grade.h"
#include "median.h"
#include "Student_info.h"

using std::domain_error;
using std::vector;

// definitions for the grade functions from S4.1/52, S4.1.2/54, S4.2.2/63

// compute a student's overall grade from midterm and final exam
// grades and homework grade (S4.1/52)
double grade(double midterm, double final, double homework)
{
    return 0.2 * midterm + 0.4 * final + 0.4 * homework;
}

// compute a student's overall grade from midterm and final exam grades
// and vector of homework grades.
// this function does not copy its argument, because median (function) does it for us.
// (S4.1.2/54)
double grade(double midterm, double final, const vector<double>& hw)
{
    if (hw.size() == 0)
        throw domain_error("student has done no homework");
    return grade(midterm, final, median(hw));
}

// this function computes the final grade for a Student_info object
// (S4.2.2/63)
double grade(const Student_info& s)
{
    return grade(s.midterm, s.final, s.homework);
}

median.cpp

// source file for the median function
#include <algorithm>
#include <stdexcept>
#include <vector>

using std::domain_error;
using std::sort;
using std::vector;

// compute the median of a vector<double>
// (S4.1.1/53)
double median(vector<double> vec)
{
    typedef vector<double>::size_type vec_sz;

    vec_sz size = vec.size();
    if (size == 0)
        throw domain_error("median of an empty vector");

    sort(vec.begin(),vec.end());

    vec_sz mid = size/2;

    return size % 2 == 0 ? (vec[mid] + vec[mid-1]) / 2 : vec[mid];
}

Student_info.cpp


#ifndef GUARD_STUDENT_INFO_H
#define GUARD_STUDENT_INFO_H

// Student_info.h
#include <iostream>
#include <string>
#include <vector>

struct Student_info
{
    std::string name;
    double midterm, final;
    std::vector<double> homework;
};

bool compare(const Student_info&, const Student_info&);
std::istream& read(std::istream&, Student_info&);
std::istream& read_hw(std::istream&, std::vector<double>&);

#endif // GUARD_STUDENT_INFO_H

</p>

Header Files

getletterGrade.h

#ifndef GUARD_GETLETTERGRADE_H
#define GUARD_GETLETTERGRADE_H

// getLetterGrade.h

#include <string>

std::string getLetterGrade(double);

#endif // GUARD_GETLETTERGRADE_H

grade.h


#ifndef GUARD_GRADE_H
#define GUARD_GRADE_H

//grade.h
#include <vector>
#include "Student_info.h"

double grade(double, double, double);
double grade(double, double, const std::vector<double>&);
double grade(const Student_info&);

#endif // GUARD_GRADE_H

median.h

#ifndef GUARD_MEDIAN_H
#define GUARD_MEDIAN_H

// median.h - final version
#include <vector>
double median(std::vector<double>);

#endif // GUARD_MEDIAN_H

Student_info.h


#ifndef GUARD_STUDENT_INFO_H
#define GUARD_STUDENT_INFO_H

// Student_info.h
#include <iostream>
#include <string>
#include <vector>

struct Student_info
{
    std::string name;
    double midterm, final;
    std::vector<double> homework;
};

bool compare(const Student_info&, const Student_info&);
std::istream& read(std::istream&, Student_info&);
std::istream& read_hw(std::istream&, std::vector<double>&);

#endif // GUARD_STUDENT_INFO_H

Test Program

I test the program by submitting a list of sample student grades. The program automatically compute and display the numeric and letter grades. It also creates a letter grade summary to count occurances per letter grade.

johnny   90 90 90 90 90
jason    85 85 85 85 85
billy    82 82 82 82 82
fred     80 80 80 80 80
frank    70 70 70 70 70
jay      66 66 66 66 66
bob      60 60 60 60 60
mary     50 50 50 50 50
ann      40 40 40 40 40
bill     30 30 30 30 30
goat     10 10 10 10 10
dog      0  0  0  0  0
^Z
^Z
ann    40 (F)
bill   30 (F)
billy  82 (B)
bob    60 (D)
dog    0 (F)
frank  70 (C)
fred   80 (B)
goat   10 (F)
jason  85 (B)
jay    66 (D)
johnny 90 (A)
mary   50 (F)

Letter Grade Summary
A: 1
B: 3
C: 1
D: 2
F: 5

Reference

Koenig, Andrew & Moo, Barbara E., Accelerated C++, Addison-Wesley, 2000