Com S 229 Fall 2009

                       Programming Project 1 (70 pts)
		    
                            Due at 11:59pm 
                        Wednesday, September 21


Number Parsing and Sorting 

Use the following header files and include the name space for standard input/output:

#include <string> 
#include <fstream> 
using namespace std; 



1. Description

In the first part of the project, you need to extract numbers from a file (which
could be a news article, a web page, a data sheet with English description,
etc). These numbers may be integers or reals but are not complex numbers.
Duplications should be eliminated after the extraction.  

Besides English letters, your code should also ignore all other non-digit characters
except blank space, comma (,), hyphen (-), period (.), and percentage (%). These
five characters are handled according to the following rules: 

    1) Blank spaces cannot be removed to concatenate numerical digits.

    2) Also, do not remove blank spaces in order to apply rest of the rules.  

    3) A comma between two numerical digits must be removed so the digits are
       concatenated. For example, "3,234" is parsed as 3234 while "3, 234" as
       two integers 3 and 234. (Note the blank space between ',' and '2' in the
       second string.)

    4) A hyphen preceding a numerical digit is treated as the negative sign
       unless it follows an English letter, another hyphen, or another digit.  For
       instance, "greater than -3" is parsed as the number -3, "IIS-915876" as 
       the number 918576, and "2 - 3" as two numbers 2 and 3.  

    5) Multiple hyphens preceding a digit are ignored.  For instance, "---2.57" is
       simply parsed as 2.57. 

    6) A single period in front of a digit sequence refers to a fraction. For instance,
       .025 means 0.025.  

    7) In case of a sequence of digits and more than one periods, treat all 
       periods as if they were blank spaces. For instance, "515.294.6511" yields
       three numbers 515, 294, and 6511, while ".515.294.6511" yields the same
       three numbers with the first '.' also ignored because the sequence has
       more than one periods. 

    8) An exception to rule 7) is a digit-period sequence that begins and
       ends with periods and has only digits in between.  Such a sequence represents a
       fraction with the second period ending the sentence.  For instance, "The
       number is -.25." should yield the number -0.25. 

    9) Ignore zeros preceding digits (but not preceded by a period). For
       instance, "000123" is 123 while ".000123" is "0.000123". 

   10) Convert the percentage sign following digits into division by 100. For
       instance, "increase by 34%" yields 0.34. (No need to check the range of the
       number before %.) 

The name of the text is acquired through standard input.  All numbers, after
removal of duplications, should be initially stored in an array: 

      double numbers[MAXLEN];   // MAXLEN is a constant set as, say, 10000.

Efficiency is not considered as a grading criterion for duplication removal. 

In the second part, implement a fast sorting algorithm, more specifically,
either Merge Sort, Heapsort  or Quicksort (cf. pp. 459-480 in the book Data
Structures and the Java Collections Framework by W. J. Collins).  [In case of
Heapsort, insertion maintains the heap structure and removes duplications
automatically.]

All numbers, sorted in the increasing order, are stored in the output file 
"sortedNumbers.txt". 


2. Submission

You need to have a source file proj1.cpp.  You may also write a header file
proj1.h.  Use a Makefile like the following:  


proj1.exe: proj1.o 
         g++ -o proj1.exe proj1.o 
 
proj1.o: proj1.cpp proj1.h
         g++ -c proj1.cpp 


There are two test files: testfile.txt and the HTML source code of this webpage: 

http://www.iowastatedaily.com/news/article_01b45f02-d2a2-11e0-9116-001cc4c002e0.html

Please read the Project Submission Guidelines under the Assignment subpage.  It
describes a zip file you need to create to contain all project files, and how
to submit the zip file via Blackboard. 

Before submission, you should test your code on a CS Linux machine, say, popeye
by porting your .cpp files, .h files (if any), Makefile, as well as some test
files under a directory.  From a Windows machine like your laptop, you can use
"ftp ftp.cs.iatate.edu" within a command window or SSH Secure File Transfer to
move your files over to popeye.

After the tranfer, login to popeye and go to the directory you just
created.  Type "make" at the prompt, and this should generate an executable file
"proj1.exe". Type "proj1" (or "proj1.exe" if that does not work) at the prompt
to execute your code.

    
Please post questions and comments (including errors in the description) related
to Project 1 to the discussion board of Blackboard.