2 Replies - 3227 Views - Last Post: 27 July 2008 - 06:19 PM Rate Topic: -----

#1 swilson23  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 29
  • Joined: 15-June 08

Word Concordance

Posted 25 July 2008 - 01:49 PM

My program must do the following:
Write a C++ program that will build a Word Concordance for a series of text lines. A Concordance is basically an index of words in a document, and a listing of their context (line numbers).

Your program should first display your identification information, similar to our previous assignments. Then the program should read a series of lines of input from cin and keep track of the words that appear on the lines, and the line numbers of where those words appear in the input stream. Upon completing the processing of the input, the program should display an alphabetized listing of the words that were found, one word per line, and next to each word will be a list of line numbers of where that word was found in the input.

A word, for the purpose of this program, is defined as a series of non-blank characters, with leading and trailing punctuation characters (-,.;:?"'!@#$%^&*[]{}|) removed (note that embedded punctuation characters, such as Bob's and ten-thirty should be left in the word). The words are to be saved without case-sensitivity; for example: Concordance ConCorDance CONCORDance concordance are all to be considered the same word.

The words are to be stored in a statically-declared array. You can assume that the maximum number of unique words that will be submitted is 200. The words are to be stored in the array in sorted order, and you are to use the array-based binary search method as described in our course notes to locate words in the array.

For each word in the array, the list of line numbers is to be maintained by using a Linked-List Queue data structure, similar to what you used for Program 4. Although the Queue isn't necessarily the most-appropriate data structure for this job, based on what we've already done with it, it should provide a simple interface to use.



The output should do this:

Your identification

This is just some sample text
that appears on several lines. This
is a test of the Concordance program
to see how well it is able to pick out
the words. As a test, he said: "is is is is is,"
many times, over and over, until he was so
tired he collapsed.

There's more to this story; just ask the dog.
He'd say: "Ruff, Ruff, Ruff!" Who'd ask a
dog, anyway?

Concordance:

A: 3 5 10
ABLE: 4
AND: 6
ANYWAY: 11
APPEARS: 2
AS: 5
ASK: 9 10
COLLAPSED: 7
CONCORDANCE: 3
DOG: 9 11
HE: 5 6 7
HE'D: 10
HOW: 4
IS: 1 3 4 5 5 5 5 5
IT: 4
JUST: 1 9
LINES: 2
MANY: 6
MORE: 9
OF: 3
ON: 2
OUT: 4
OVER: 6 6
PICK: 4
PROGRAM: 3
RUFF: 10 10 10
SAID: 5
SAMPLE: 1
SAY: 10
SEE: 4
SEVERAL: 2
SO: 6
SOME: 1
STORY: 9
TEST: 3 5
TEXT: 1
THAT: 2
THE: 3 5 9
THERE'S: 9
THIS: 1 2 9
TIMES: 6
TIRED: 7
TO: 4 4 9
UNTIL: 6
WAS: 6
WELL: 4
WHO'D: 10
WORDS: 5




My problem is that I can't get it to sort! Can someone help me w/ this please and show me what I need to do? I'm clueless!!! My code is below.

// Example of Binary Search of an Array
#include <iostream>
#include <cstdlib>
#include <string> 
#include "queue.h"
#include <sstream>  // for istringstream


using namespace std;

const int MAX = 200; // maximum number of nodes
typedef string TreeItemType;
/*
class TreeNode { // node in the tree
private:
   TreeNode();
   TreeNode(const TreeItemType& nodeItem,
			  int left, int right);

   TreeItemType item;   // data portion
   int leftChild;	// index to left child
   int rightChild;   // index to right child

   // friend class - can access private parts
   friend class BinaryTree;
};  // end class TreeNode

//int values[] = { -23, -6, 10, 15, 20, 25, 32, 40, 55, 82, 90, 100 };
TreeNode values[MAX];

*/

typedef struct dictType{
  string str;
  Queue line;
}dictItemType;
const string Punctuation = ",.;:?\"'!@#$%^&*[]{}|";


int main () {
//int sizeValues = sizeof(values) / sizeof (int);
istringstream strLine;
string line, word;
//dictItemType dict;
dictItemType dictionary[200];
int currentLine=0;
int j;
  while (getline(cin,line)) {
	++currentLine;
	
	// clear the strstream and copy the entered line to it
	strLine.clear();
	strLine.str(line);

	// now get each word-sequence from the strLine stream
	
	while (strLine >> word){	  
	  //dictionary[i].str = word;
	  
	  //You need tokenized.
	  while (word.length() > 0 && Punctuation.find(word[0]) != string::npos)  
		word = word.substr(1);

	  for( j=0; j < MAX; j++){		
		if(dictionary[j].str.empty()){
		  cout << currentLine << ": " << word << endl; 
		  dictionary[j].str = word;		  
		  dictionary[j].line.enqueue(currentLine);		  
		  break;
		}else{
			if(dictionary[j].str.compare(word) == 0){
			  cout <<"Already there"<<endl << currentLine << ": " << word << endl; 
			  dictionary[j].line.enqueue(currentLine);
			  break;
			}//endif		   
		}//endifelse
	  }//endfor
	  //j=0;
	}//endwhile
  }//endwhile

  //SORTALGORITHM



// ********************************************************
// Header file queue.h - Pointer-based implementation.
// ********************************************************

typedef int QueueItemType;

class Queue {
public:
// constructors and destructor:
   Queue();					 // default constructor
   ~Queue();					// destructor

// Queue operations:
   bool isEmpty();
   // Determines whether the queue is empty.
   // Precondition: None.
   // Postcondition: Returns true if the queue is empty;
   //   otherwise returns false.

   void enqueue(QueueItemType newItem);
   // Inserts an item at the back of a queue.
   // Precondition: newItem is the item to be inserted.
   // Postcondition: If the insertion is successful, newItem
   //   is at the back of the queue.

   bool dequeue();
   // Dequeues the front of a queue.
   // Precondition: None.
   // Postcondition: If the queue is not empty, the item
   //   that was added to the queue earliest is deleted
   //   and returns true; if queue is empty, returns false

   bool dequeue(QueueItemType& queueFront);
   // Retrieves and deletes the front of a queue.
   // Precondition: None.
   // Postcondition: If the queue is not empty, queueFront
   //   contains the item that was added to the queue
   //   earliest, and the item is deleted and returns
   //   true; if queue is empty, returns false

   bool getFront(QueueItemType& queueFront);
   // Retrieves the item at the front of a queue.
   // Precondition: None.
   // Postcondition: If the queue is not empty, queueFront
   //   contains the item that was added to the queue
   //   earliest and returns true; if queue is empty,
   //   returns false

private:
   // The queue is implemented as a linked list
   // with one external pointer to the front of the queue
   // and a second external pointer to the back of the
   // queue.
   struct QueueNode {
	 QueueItemType  item;
	 QueueNode	 *next;
	 }; // end struct

   QueueNode *backPtr;
   QueueNode *frontPtr;
};  // end class


// *************************************************************
// Implementation file queue.cpp - Pointer-based implementation
// *************************************************************
#include "queue.h"  // header file

Queue::Queue() {
  backPtr = frontPtr = NULL;
}  // end default constructor

Queue::~Queue() {
  while (!isEmpty())
	dequeue();
}  // end destructor

bool Queue::isEmpty() {
  return backPtr == NULL;
}  // end isEmpty

void Queue::enqueue(QueueItemType newItem) {
  // create a new node
  QueueNode *newPtr = new QueueNode;

  // set data portion of new node
  newPtr->item = newItem;
  newPtr->next = NULL;

  // insert the new node
  if (isEmpty()) // insertion into empty queue
	frontPtr = newPtr;
  else // insertion into nonempty queue
	backPtr->next = newPtr;

  backPtr = newPtr;  // new node is at back
}  // end enqueue

bool Queue::dequeue() {
  if (isEmpty()) return false;

  // queue is not empty; remove front
  QueueNode *tempPtr = frontPtr;
  if (frontPtr == backPtr) {   // special case?
	// yes, one node in queue
	frontPtr = NULL;
	backPtr = NULL;
	}
  else frontPtr = frontPtr->next;

  tempPtr->next = NULL;
  delete tempPtr;
  return true;
}  // end dequeue

bool Queue::dequeue(QueueItemType& queueFront) {
  if (isEmpty()) return false;
  // queue is not empty; retrieve front
  queueFront = frontPtr->item;
  dequeue();  // delete front
  return true;
}  // end dequeue

bool Queue::getFront(QueueItemType& queueFront) {
  if (isEmpty()) return false;
  // queue is not empty; retrieve front
  queueFront = frontPtr->item;
  return true;
}  // end getFront
// End of queue.cpp


*Mod Edit: added code tags: ::code::

This post has been edited by NickDMax: 25 July 2008 - 02:50 PM


Is This A Good Question/Topic? 0
  • +

Replies To: Word Concordance

#2 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2239
  • View blog
  • Posts: 9,409
  • Joined: 29-May 08

Re: Word Concordance

Posted 25 July 2008 - 03:59 PM

I would create a new class call LineReferences made up of a string (word) and list of long(line number)
Split the text via punctuation ( space, newlines etc)

In VB.Net thus (Message To Mods: Please don't move to VB.Net forum)
Public Class LineReferences
    Protected mLines As New List(Of Long)
    Public ReadOnly Property LineRef() As List(Of Long)
        Get
            Return mLines
        End Get
    End Property

    Private mWord As String
    Public ReadOnly Property Word() As String
        Get
            Return mWord
        End Get
    End Property

    Public Sub AddLineRef(ByRef Line As Long)
        mLines.Add(Line)
    End Sub

    Public Sub New(ByRef word As String)
        mWord = word
    End Sub
End Class



Then in main code
 Dim concordance As New Collections.Generic.SortedList(Of String, LineReferences)


psuedo code
		For Each word As String In docText
			If concordance.ContainsKey(word) Then
				concordance(word).AddLineRef(lineNumber)
			Else
				concordance.Add(word, New LineReferences(word))
			End If
		Next


Display Psuedo-code
For each wordRef as LineReference in concordance
 Print wordRef.word
 For each line as long in word.lineref
  Print line
 next
next



This should help you get started.
Was This Post Helpful? 0
  • +
  • -

#3 swilson23  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 29
  • Joined: 15-June 08

Re: Word Concordance

Posted 27 July 2008 - 06:19 PM

View PostAdamSpeight2008, on 25 Jul, 2008 - 03:59 PM, said:

I would create a new class call LineReferences made up of a string (word) and list of long(line number)
Split the text via punctuation ( space, newlines etc)

In VB.Net thus (Message To Mods: Please don't move to VB.Net forum)
Public Class LineReferences
    Protected mLines As New List(Of Long)
    Public ReadOnly Property LineRef() As List(Of Long)
        Get
            Return mLines
        End Get
    End Property

    Private mWord As String
    Public ReadOnly Property Word() As String
        Get
            Return mWord
        End Get
    End Property

    Public Sub AddLineRef(ByRef Line As Long)
        mLines.Add(Line)
    End Sub

    Public Sub New(ByRef word As String)
        mWord = word
    End Sub
End Class



Then in main code
 Dim concordance As New Collections.Generic.SortedList(Of String, LineReferences)


psuedo code
		For Each word As String In docText
			If concordance.ContainsKey(word) Then
				concordance(word).AddLineRef(lineNumber)
			Else
				concordance.Add(word, New LineReferences(word))
			End If
		Next


Display Psuedo-code
For each wordRef as LineReference in concordance
 Print wordRef.word
 For each line as long in word.lineref
  Print line
 next
next



This should help you get started.







Do you think this algorithm will work for my code?



void sort(char a[], int alphabet);

int main(){

const int alpha = 10;
char x[alpha] = {'E', 'F', 'Y', 'R', 'Q', 'A', 'T', 'O', 'W', 'X'};


sort(x, alpha);

cout << endl;
cout << "Letter \n" << endl;
for (int i = 0; i < alpha; i++) {
if (x[i] > 0) {
cout << x[i]<< " "; }}
cout << endl;

system("pause");
return 0;
}
void sort(char a[], int alphabet)
{

char temp, i, j;
for (i = 0; i < (alphabet-1); i++){
for(j = (i+1); j < alphabet; j++) {
if ( a[i] < a[j] )
{
temp = a[i];
a[i] = a[j];
a[j] = temp;

}
}
}
}
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1