Някаква тъпа глупост

Пример за определяне на принадлежност на низ към формален език

Това което пише в тази статия е ПЪЛЕН АБСУРД. Забравете го веднага след изпита.
И.Чернев
Сериозно, тази статия е фекалий изходен от последния прокажен в ада.
М. Минков

Формален език се дефинира с формална граматика Г = < N, T, S, P >, където N е множество от нетерминални символи, T е множество от терминални символи, S  N е начален нетерминал, P е множество от продукции, които имат синтактичен характер и те определят начина по който се строят думи в езика;
в този въпрос разглеждаме формалният език, породен от следната граматика Г = < { S }, { a, b, c}, S, { S -> aSa, S -> bSb, S -> c } >;
лесно се вижда, че езикът на тази граматика се състои от всички думи c, където  е получена от  чрез инвертиране и  се състои само от a, b;
ще разгледаме програма, която разпознава дали даден низ принадлежи на този език; за целта използваме следния алгоритъм:
- въвеждаме низа в стек до срещане на c;
- след това сравняваме останалите символи със символите в стека и ако има пълно съвпадение, то низът е в езика;
за реализацията ще опишем шаблон на стек;

файл stack2.h

#ifndef STACK2_H
#define STACK2_H
template <class T>
struct item {
 T value;
 item *next;
} ;
template <class T>
class Stack {
 public:
   Stack ();
   ~Stack ();
   void push (const T&);
   bool pop (T&);
   T top () const;
   bool isEmpty () const;
 private:
   item <T> *first;
} ;
template <class T>
Stack <T>::Stack () : first (NULL) { }
template <class T>
Stack <T>::~Stack ()
 { item <T> *ptr;
   while (first)
     { ptr = first;
       first = first -> next;
       delete ptr;
     }
  }
template <class T>
void Stack <T>::push (const T&x)
 { item <T> *ptr = new item <T>;
   //считаме, че е включена опция за стандартно прекъсване при  
   //изпълнението на new когато няма свободна памет и за това
   //не правим проверка дали операцията е успешна
   ptr -> value = x;
   ptr -> next = first;
   first = ptr;
 }
template <class T>
bool Stack <T>::pop (T &x)
 { if (isEmpty()) return false;
   item <T> *ptr = first;
   first = first -> next;
   x = ptr -> value;
   delete ptr;
   return true;
 }
template <class T>
T Stack <T>::top () const
 { return first -> value; } 
//предполагаме, че функцията top няма да се извиква за празен стек
template <class T>
bool Stack <T>::isEmpty () const
 { return first==NULL; }
#endif

сега ще опишем самата програма;
#include <iostream>
#include "stack2.h"
using std::cin;
using std::cout;
using std::endl;
void Error ()
 { cout << "Низът не е от езика!" << endl; }
void main ()
 { Stack <char> chStack;
   char ch, R;
   cout << "Въведете низ: ";
   ch = cin.get ();
   if (ch < 'a' || ch > 'c') { Error(); return; }
   while (ch != 'c')
    { chStack.push (ch);
      ch = cin.get ();
      if ( ch < 'a' || ch > 'c') { Error(); return; }
    }
   ch = cin.get ();
   if (ch != 'a' && ch != 'b' && ch != '\n') { Error(); return; }
   while (ch != '\n')
    { if (!chStack.isEmpty())
       if (ch != chStack.top())
        { Error(); return; }
       else;
      else { Error(); return; }
     chStack.pop (R);
     ch = cin.get ();
     if (ch != 'a' && ch != 'b' && ch != '\n') { Error(); return; }
    }
   if (!chStack.isEmpty ()) { Error(); return; }
   cout << "Низът е от езика!" << endl;
 }
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License