Chapter 16. Pattern matching

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 16: Searching for patterns in a text string

// Pattern matching algorithm

#include "deque_list.h"

//(A*B+AC)D
char ch[10] = {' ', 'A', ' ', 'B', ' ', ' ', 'A', 'C', 'D', ' '};
int next1[10] = { 5, 2, 3, 4, 8, 6, 7, 8, 9, 0};
int next2[10] = { 5, 2, 1, 4, 8, 2, 7, 8, 9, 0};

/*
// ca*b
char ch[5] = {'c', ' ', 'a', 'b', ' '};
int next1[5] = {1,2,1,4,0};
int next2[5] = {1,3,1,4,0};
*/

const int scan = -1;

int patternmatch(char *text) {
  Deque<int> dq;
  int n1, n2;
  int j = 0, n = strlen(text), state = next1[0];
  dq.insert(scan);
  while (state) {
    if (state == scan) {
      j++; dq.insert(scan);
      state = next1[0]; continue;
    }
    else if (ch[state] == text[j])
      dq.insert(next1[state]);
    else if (ch[state] == ' ') {
      n1 = next1[state]; n2 = next2[state];
      dq.push(n1); if (n1 != n2) dq.push(n2);
    }
    if (dq.empty() || j==n) return 0;
    dq.pop(state);
  }
  return j;
}

int main() {
  char text[80];
  cout << "search pattern: (A*B+AC)D\n";
  cout << "input text in CAPITAL letter: ";
  gets(text);
  strcat(text,".");
  cout << patternmatch(text) << endl;
}

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 16: Searching for patterns in a text string


// Deque class - Double-ended queue
// File name: deque_list.h

#include <iostream>
#include <iomanip>
#include <string.h>

using namespace std;

//enum bool {false, true};

template <class Type>
class Deque {
  struct Node {
    Type data; Node *link;
    Node(Type d, Node *pt=NULL) : data(d), link(pt) {}
  };
  Node *top, *back;
public:
  Deque() {
    top = back = NULL;
  }
  ~Deque();
  bool insert(Type item);
  bool push(Type item);
  bool pop(Type& item);
  bool empty();
};

template<class Type>
Deque<Type>::~Deque() {
  Node *temp;
  while (top) {
    temp = top; top = top->link;
    delete temp;
  }
}

template<class Type>
bool Deque<Type>::pop(Type& item) {
  if(empty()) {
    cout << "Stack is empty" << endl;
    return false;
  }
  else {
    Node *temp = top;
    item = top->data;
    if(back == top) back = NULL;
    top = top->link;
    delete temp;
    return true;
  }
}

template<class Type>
bool Deque<Type>::push(Type item) {
  Node *new_node = new Node(item, top);
  if(new_node) {
    top = new_node;
    if(!back) back = top;
    return true;
  }
  else return false;
}

template <class Type>
bool Deque<Type>::insert(Type item) {
  Node *new_node = new Node(item);
  if(new_node) {
    if(empty()) top = back = new_node;
    else {
      back->link = new_node;
      back = back->link;
    }
    return true;
  }
  else return false;
}

template <class Type>
bool Deque<Type>::empty() {
   if(!top) return true;
   else return false;
}