#include <vector>
#include <map>
#include <utility>
#include <vector>
#include <iostream>


using namespace std;

typedef std::pair<char,char> Key;

struct E
{
  vector<char> h;

  Key get() {
    char second = h.back();
    h.pop_back();
    char first = h.back();
    h.pop_back();
    return make_pair(first, second);
  }
  bool good() { return h.size() > 1; }
  char add(char c) { h.push_back(c); }
};

struct P
{
  std::map<Key, char> actionTable_;

  P()
  {
    createActionTable();
  }

  void r(E& e)
  {
    cout << "before: ";
    for (auto it: e.h)
      cout << it;
    cout << endl;
    bool stop = false;
    while (e.good() && !stop) {
      pair<char,char> k = e.get();
      char action = actionTable_[k];
      switch (action) {
        case 'L':
          e.add('f');
          break;
        case 'R':
          e.add('f');
          stop = true;
          break;
        case 'S':
          e.add(k.first);
          e.add(k.second);
          stop = true;
          break;
        case 'I':
        default:
          e.add('u');
          stop = true;
          break;
      }
    }
    cout << " after: ";
    for (auto it: e.h)
      cout << it;
    cout << endl;
    cout << "--" << endl;
  }

  void createActionTable()
  {
    // u ->
    actionTable_[Key('u','u')] = 'S'; // Shift
    actionTable_[Key('u','f')] = 'S';
    actionTable_[Key('u','l')] = 'S';
    actionTable_[Key('u','r')] = 'I'; // Illegal

    // f ->
    actionTable_[Key('f','f')] = 'S'; // ambiguous
    actionTable_[Key('f','l')] = 'S';
    actionTable_[Key('f','r')] = 'R'; // Right-reduce

    // l ->
    actionTable_[Key('l','f')] = 'L'; // Left-reduce
    actionTable_[Key('l','l')] = 'S';
    actionTable_[Key('l','r')] = 'I';

    // r ->
    actionTable_[Key('r','f')] = 'I';
    actionTable_[Key('r','l')] = 'I';
    actionTable_[Key('r','r')] = 'I';
  }
};


int main(void)
{
  E e;
  P p;

  /*e.add('u');
  p.r(e);

  e.add('l');
  p.r(e);

  e.add('l');
  p.r(e);

  e.add('f');
  p.r(e);

  e.add('r');
  p.r(e);*/

 string s("frllllfrlllllllf");
 for (auto it: s) {
   e.add(it);
   p.r(e);
 }

  return 0;
}