fork download
copy 
  1. #include <iostream>
  2. #include <sstream>
  3. #include <string>
  4.  
  5. using namespace std;
  6.  
  7. string getFileData()
  8. {
  9.     string data;
  10.  
  11.     data += "6\n";
  12.  
  13.     data += "b\n"; data += "Second Letter in the Alphabet (Rhymes with 'Bee')\n";
  14.     data += "a\n"; data += "The first letter in the alphabet (Vowel)\n";
  15.     data += "why\n"; data += "Why what?\n";
  16.     data += "why?\n"; data += "Why what?\n";
  17.     data += "hello\n"; data += "Hello!\n";
  18.     data += "hi\n"; data += "Hello!\n";
  19.  
  20.     return data;
  21. }
  22.  
  23. struct MyPairOfStrings
  24. {
  25.     string first;
  26.     string second;
  27. };
  28.  
  29. bool operator < (const MyPairOfStrings & p1, const MyPairOfStrings & p2)
  30. {
  31.     return p1.first < p2.first;
  32. }
  33.  
  34. int binarySearch(MyPairOfStrings * A, string key, int imin, int imax)
  35. {
  36.     if (imax < imin) return -1;
  37.  
  38.     int imid = (imin + imax) / 2;
  39.  
  40.     if (A[imid].first > key)
  41.         return binarySearch(A, key, imin, imid - 1);
  42.     else if (A[imid].first < key)
  43.         return binarySearch(A, key, imid + 1, imax);
  44.     else return imid;
  45. }
  46.  
  47. void siftDown(MyPairOfStrings * array, int start, int end)
  48. {
  49.     int root = start;
  50.  
  51.     while (2 * root + 1 <= end)
  52.     {
  53.         int child = 2 * root + 1;
  54.         int swap_with = root;
  55.  
  56.         if (array[swap_with] < array[child])
  57.             swap_with = child;
  58.  
  59.         if (child + 1 <= end && array[swap_with] < array[child + 1])
  60.             swap_with = child + 1;
  61.  
  62.         if (root != swap_with)
  63.         {
  64.             MyPairOfStrings temp = array[swap_with];
  65.             array[swap_with] = array[root];
  66.             array[root] = temp;
  67.  
  68.             root = swap_with;
  69.         }
  70.         else return;
  71.     }
  72. }
  73.  
  74. void heapify(MyPairOfStrings * array, int size)
  75. {
  76.     int start = (size - 2) / 2;
  77.  
  78.     while (start >= 0)
  79.     {
  80.         siftDown(array, start, size - 1);
  81.         start --;
  82.     }
  83. }
  84.  
  85. void heapsort(MyPairOfStrings * array, int size)
  86. {
  87.     heapify(array, size);
  88.  
  89.     int end = size - 1;
  90.  
  91.     while (end > 0)
  92.     {
  93.         MyPairOfStrings temp = array[0];
  94.         array[0] = array[end];
  95.         array[end] = temp;
  96.  
  97.         end --;
  98.  
  99.         siftDown(array, 0, end);
  100.     }
  101. }
  102.  
  103. int main()
  104. {
  105.     // let's pretend this is our file
  106.     stringstream file(getFileData());
  107.  
  108.     int n;
  109.  
  110.     file >> n; // get number of entries
  111.     file.get(); // ignore newline
  112.  
  113.     MyPairOfStrings * dataArr = new MyPairOfStrings[n];
  114.  
  115.     for (int i = 0; i < n; ++ i)
  116.     {
  117.         getline(file, dataArr[i].first);
  118.         getline(file, dataArr[i].second);
  119.     }
  120.  
  121.     heapsort(dataArr, n); // sort the data in
  122.     // order to be able to perform binary search
  123.  
  124.     string input;
  125.  
  126.     while (true)
  127.     {
  128.         getline(cin, input);
  129.  
  130.         if (input.empty()) break; // empty line == quit
  131.  
  132.         for (int i = 0; i < input.length(); ++ i)
  133.             if (input[i] >= 'A' && input[i] <= 'Z')
  134.                 input[i] += 'a' - 'A';
  135.  
  136.         // search the array for the entered string
  137.         int i = binarySearch(dataArr, input, 0, n - 1);
  138.  
  139.         // if it's found, print the appropriate message
  140.         if (i != -1) cout << dataArr[i].second << endl;
  141.         // otherwise, print an error message
  142.         else cout << "Sorry, I don't understand..." << endl;
  143.     }
  144.  
  145.     delete[] dataArr;
  146. }
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ojv1H
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!