1: #include <iostream> 2: #include <string> 3: #include <fstream> 4: #include <vector> 5: #include <stack> 6: #include <queue> 7: #include <list> 8: using namespace std; 9: typedef stack <string> wordStack; 10: /************************ 11: * Function Prototypes * 12: ************************/ 13: string findNextWord(string word); 14: void findNewWord(); 15: /************************ 16: * Global Variables * 17: ************************/ 18: int dictIndex; 19: /******************************************************************************** 20: * class: Dictionary * 21: * purpose: To hold the word list in which to build the Ladder * 22: ********************************************************************************/ 23: class Dictionary 24: { 25: private: 26: vector <string> dictWords; 27: public: 28: Dictionary(){}; 29: /******************************************************************************** 30: * function: initVector * 31: * purpose: fill a vector with all the valid words from the * 32: * words.dat file * 33: ********************************************************************************/ 34: void initVector() 35: { 36: int wordend=0; 37: string word; 38: const string letters = "abcdefghijklmnopqrstuvwxyz"; 39: 40: ifstream textfile("words.dat"); 41: if(!textfile) 42: { 43: cerr << "Cannot open words.dat file\n"; 44: return; 45: } 46: while (!textfile.eof()) 47: { 48: getline(textfile, word); 49: wordend = word.find_first_not_of( letters, 0); 50: if( (wordend < 0) || (wordend > 0) ) 51: { 52: word=word.substr(0,wordend); 53: dictWords.push_back(word); 54: } 55: } 56: } 57: /******************************************************************************** 58: * function: BinSearch * 59: * purpose: Search the dictionary vector for the appropriate * 60: * word using a binary search algorithm * 61: ********************************************************************************/ 62: int BinSearch(string line) 63: { 64: int First=0,last = this->size(),mid; 65: int origLast = last; 66: string midvalue; 67: 68: while(First < last) 69: { 70: mid = (First+last)/2; 71: midvalue = dictWords[mid]; 72: if(line == midvalue) return mid; 73: else if(line < midvalue) last = mid; 74: else First = mid+1; 75: } 76: return origLast; 77: } 78: /******************************************************************************** 79: * function: getWord * 80: * purpose: to return a word from within the dictionary vector * 81: * using a given index * 82: ********************************************************************************/ 83: string getWord(int a){ return dictWords[a];} 84: /******************************************************************************** 85: * function: findWords * 86: * purpose: to determine if selected words are present in the * 87: * dictionary (returns 0 if word both words are present) * 88: ********************************************************************************/ 89: int findWords(string a,string c) 90: { 91: try 92: { if (a.length() != 5 || c.length() != 5) throw a; 93: } 94: catch (string a) 95: { cout << "\nThe words \"" <<a << "\" and \"" << c << "\" are not both "; 96: cout << "legitimate 5-letter words from the dictionary.\n\nPlease try again..."<<endl; 97: return 1; 98: } 99: try 100: { 101: int b = this->BinSearch(a); 102: if(b == this->size()) throw b; 103: return 0; 104: } 105: catch(int b) 106: { 107: cout << a << " could not be found in the Dictionary!\n"; 108: return 1; 109: } 110: try 111: { 112: int b = this->BinSearch(c); 113: if(b == this->size()) throw b; 114: } 115: catch(int b) 116: { 117: cout << c << " could not be found in the Dictionary!\n"; 118: return 1; 119: } 120: } 121: /******************************************************************************** 122: * function: empty * 123: * purpose: returns true if the dictionary is empty * 124: ********************************************************************************/ 125: bool empty() 126: { 127: if (dictWords.empty()) 128: return true; 129: else 130: return false; 131: } 132: /******************************************************************************** 133: * function: size * 134: * purpose: returns the size of the dictionary * 135: ********************************************************************************/ 136: int size(){ return dictWords.size(); } 137: /******************************************************************************** 138: * function: at * 139: * purpose: returns the element at the given index * 140: ********************************************************************************/ 141: string at(int index){ return dictWords[index]; } 142: }; 143: // Variable to hold our dictionary which will be used throughout the program 144: Dictionary MyDictionary; 145: /******************************************************************************** 146: * function: main * 147: * purpose: The beginning of the program * 148: ********************************************************************************/ 149: int main() 150: { 151: string start,final; 152: MyDictionary.initVector(); 153: if(!MyDictionary.empty()) 154: { 155: cout << "\nPlease enter the starting word (or STOP to quit the program):\n"; 156: cin >> start; 157: cout << "Please enter the final word:\n"; 158: cin >> final; 159: while(start != "STOP") 160: { 161: cout << "\nSearching for a word ladder...\n"; 162: if(!MyDictionary.findWords(start,final)) 163: { 164: //keeps track of words that have been used 165: list<string> usedWords; 166: list<string>::iterator p; 167: 168: wordStack tempStack; 169: queue <wordStack> stackQ; 170: tempStack.push(start); 171: usedWords.push_back(start); 172: stackQ.push(tempStack); 173: 174: while( stackQ.size() != 0 and (stackQ.front()).top() != final) 175: { tempStack = stackQ.front(); 176: stackQ.pop(); 177: string wordFound = findNextWord(tempStack.top()); 178: while (wordFound != "done") 179: { p = find(usedWords.begin(), usedWords.end(), wordFound); 180: if (p == usedWords.end()) //Checks if the word has already been used 181: { usedWords.push_back(wordFound); 182: //cout << wordFound << " has been used" << endl; 183: wordStack newStack = tempStack; 184: newStack.push(wordFound); 185: stackQ.push(newStack); 186: } 187: wordFound = findNextWord(tempStack.top()); 188: } 189: findNewWord(); 190: } 191: try 192: { 193: if (stackQ.size() == 0) 194: { 195: throw stackQ; 196: } 197: stack<string> leStack = stackQ.front(); 198: cout << "\nFor the input words "<< start << " and " << final; 199: cout << " the following ladder was found.\n\n"; 200: //int wordLadderSize = wordLadder.size(); 201: //cout<< "word ladder size = " << wordLadderSize<<endl; 202: 203: stack<string> wordLadder; 204: while (!leStack.empty()) 205: { wordLadder.push(leStack.top()); 206: leStack.pop(); 207: } 208: while (!wordLadder.empty()) 209: { cout << wordLadder.top() << "\n"; 210: wordLadder.pop(); 211: } 212: } 213: catch ( queue<wordStack> stackQ) 214: { cout<<"\n-- No word ladder exists for \""<<start<<"\" and \""<<final<<"\" --"<<endl; 215: } 216: cout<< endl; 217: } 218: cout << "\nEnter starting word (or STOP to stop):\n"; 219: cin >> start; 220: if (start == "STOP") 221: continue; 222: cout << "Enter ending word:\n"; 223: cin >> final; 224: } 225: } 226: else 227: { 228: return 0; 229: } 230: // The user has entered the sentinel and the program will terminate 231: cout << "\n**You have entered \"STOP\", the program will now terminate**\n"; 232: return 0; 233: } 234: /******************************************************************************** 235: * function: findNextWord * 236: * purpose: find the next word in the word ladder * 237: ********************************************************************************/ 238: string findNextWord(string word) 239: { 240: while(dictIndex < MyDictionary.size()) 241: { 242: string temp = MyDictionary.at(dictIndex); 243: int index1 = temp.find_first_not_of(word); 244: int index2 = temp.find_last_not_of(word); 245: if (index1 == index2 && index1 != -1) 246: { 247: if ((temp.substr(index1 + 1) == word.substr(index1+1)) && 248: (temp.substr(0, index1) == word.substr(0, index1))) 249: { 250: dictIndex++; 251: return temp; 252: } 253: } 254: dictIndex++; 255: } 256: //cout<< " no words found" << endl; 257: const string DONE = "done"; 258: return DONE; 259: } 260: /******************************************************************************** 261: * function: findNewWord * 262: * purpose: Resets the dictIndex * 263: ********************************************************************************/ 264: void findNewWord(){ dictIndex = 0; } 265: 266:
| w | e | b | c | p | p |
|
| |||||