uva 11988 - Broken Keyboard (a.k.a. Beiju Text)

  1 /*
  2  Problem link
  3  Type: Data structure - link list
  4  Algorithm:
  5      I know that we can use C++ fancy library for link list but
  6      since I'm taking a data structure course, I'll do this exercise
  7      the OOP style with my own link list.
  8  
  9      This is a very rare programming problem that we MUST use the
 10      link list to maintain the following procedure: insert at the head,
 11      insert at the tail, insert at the current position.
 12  */
 13  #include <iostream>
 14  #include <cstdio>
 15  #include <cstring>
 16  #include <string>
 17  
 18  using namespace std;
 19  const char* fi = "11988.inp";
 20  const char* fo = "11988.out";
 21  
 22  struct Node
 23  {
 24      char data;
 25      Node* pNext;
 26      Node() { pNext = NULL; }
 27  };
 28  
 29  class CharList
 30  {
 31  public:
 32      CharList()                      // Default constructor
 33      {
 34          pHead = new Node();
 35          pTail = new Node();
 36          pHead->pNext = pTail;
 37          pPreTail = pHead;
 38      }
 39  
 40      Node* getHead() { return pHead; }       // Get the head
 41      Node* getTail() { return pPreTail; }    // Get the tail
 42  
 43      void insert(char data, Node* index)     // Insert new node with data after the index node
 44      {
 45          Node* x = new Node();
 46          x->data = data;
 47          x->pNext = index->pNext;
 48          index->pNext = x;
 49  
 50          while (pPreTail->pNext != pTail) pPreTail = pPreTail->pNext;    // update the last (pre tail) node
 51      }
 52  
 53      void show()     // Function to print out all the list
 54      {
 55          Node* pos = pHead;
 56          while (pos->pNext != pTail)
 57          {
 58              pos = pos->pNext;
 59              cout << pos->data;
 60          }
 61      }
 62  
 63      ~CharList()     // Default destructor to free memory
 64      {
 65          while (pHead->pNext != pTail)
 66          {
 67              Node* tmp = pHead->pNext;
 68              pHead->pNext = tmp->pNext;
 69              delete tmp;
 70          }
 71          delete pHead;
 72          delete pTail;
 73      }
 74  private:
 75      Node* pHead;
 76      Node* pTail;
 77      Node* pPreTail;
 78  };
 79  
 80  int main()
 81  {
 82      string s;
 83      while (!cin.eof())
 84      {
 85          cin >> s;
 86          if (cin.eof()) break;    // If you use cin.eof(), remember this line or WA
 87          CharList result;
 88          Node* pos = result.getHead();
 89          for (unsigned int i = 0; i < s.length(); i++)
 90          {
 91              if (s[i] == '[') pos = result.getHead();        // Meet [: jump to head
 92              else if (s[i] == ']') pos = result.getTail();   // Meet ]: jump to tail
 93              else
 94              {
 95                  result.insert(s[i], pos);                   // insert at current position
 96                  pos = pos->pNext;                           // jump to next position
 97              }
 98          }
 99          result.show();                                      // print the result
100          cout << endl;
101      }
102      return 0;
103  }