LFC-T4-AFD

//
//  main.cpp
//  T4-AFD
//
//  Created by Andrei Gavrila on 21/10/2019.
//  Copyright © 2019 Andrei Gavrila. All rights reserved.
//

#include <iostream>
#include <iomanip>
#include <set>
#include <map>
#include <string>
#include <fstream>
#include <regex>

#define LOG_DEBUG(x)
//#define LOG_DEBUG(x) std::cout << "DEBUG: " << x << std::endl
#define LOG_WARNING(x) std::cout << "WARNING: " << x << std::endl
#define LOG_ERROR(x) std::cout << "ERROR: " << x << std::endl

#define OS "[\\s]*"
#define STARE "[a-zA-Z0-9]+"
#define STARI OS "Stari" OS "=" OS "\\{((" OS STARE OS "[,]{1}" OS ")*(" OS STARE OS "){1})\\}"

class AFD
{
private:
    std::set<std::string> Stari;
    std::set<std::string> Sigma;
    std::map<std::string, std::map<std::string, std::string>> Delta;
    std::string StareInit;
    std::set<std::string> Finale;

    bool attempt_to_read_stari(const std::string &line)
    {
        std::match_results<std::string::const_iterator> mr;

//        std::regex r("[\\s]*Stari[\\s]*=[\\s]*\\{(([\\s]*[a-zA-Z0-9]+[\\s]*[,]{1}[\\s]*)*([\\s]*[a-zA-Z0-9]+[\\s]*){1})\\}");
        std::regex r(STARI);

        if (std::regex_match(line, mr, r))
        {
            LOG_DEBUG("Detected Stari line: " << line);

//            std::regex ri("[a-zA-Z0-9]+");
            std::regex ri(STARE);
            std::match_results<std::string::const_iterator> mri;

            std::string haystack = mr[1].str();

            while (regex_search(haystack, mri, ri))
            {
                LOG_DEBUG("Adding Stari item: " << mri.str());

                Stari.insert(mri.str());

                haystack = mri.suffix();
            }

            return true;
        }

        return false;
    }

    bool attempt_to_read_sigma(const std::string &line)
    {
        std::match_results<std::string::const_iterator> mr;

        std::regex r("[\\s]*Sigma[\\s]*=[\\s]*\\{(([\\s]*[a-zA-Z0-9\\+=]+[\\s]*[,]{1}[\\s]*)*([\\s]*[a-zA-Z0-9\\+=]+[\\s]*){1})\\}");

        if (std::regex_match(line, mr, r))
        {
            LOG_DEBUG("Detected Sigma line: " << line);

            std::regex ri("[a-zA-Z0-9\\+=]+");
            std::match_results<std::string::const_iterator> mri;

            std::string haystack = mr[1].str();

            while (regex_search(haystack, mri, ri))
            {
                LOG_DEBUG("Adding Sigma item: " << mri.str());

                Sigma.insert(mri.str());

                haystack = mri.suffix();
            }

            return true;
        }

        return false;
    }

    bool attempt_to_read_delta(const std::string &line)
    {
        std::match_results<std::string::const_iterator> mr;

        std::regex r("[\\s]*Delta[\\s]*\\([\\s]*([a-zA-Z0-9]+)[\\s]*,[\\s]*([a-zA-Z0-9\\+=]+)[\\s]*\\)[\\s]*=[\\s]*([a-zA-Z0-9]+)[\\s]*");

        if (std::regex_match(line, mr, r))
        {
            LOG_DEBUG("Detected Delta line: " << line);

            if ((Delta.find(mr[1].str()) != Delta.end()) && (Delta[mr[1].str()].find(mr[2].str()) != Delta[mr[1].str()].end()))
            {
                LOG_WARNING("Replacing Delta item (" + mr[1].str() + ", " + mr[2].str() + ", " + Delta[mr[1].str()][mr[2].str()] + ") with: " << mr[1].str() << ", " << mr[2].str() << ", " << mr[3].str());
            }
            else
            {
                LOG_DEBUG("Adding Delta item with: " << mr[1].str() << ", " << mr[2].str() << ", " << mr[3].str());
            }

            Delta[mr[1].str()][mr[2].str()] = mr[3].str();

            return true;
        }

        return false;
    }

    bool attempt_to_read_stare_init(const std::string &line)
    {
        std::match_results<std::string::const_iterator> mr;

        std::regex r("[\\s]*StareInit[\\s]*\\=[\\s]*([a-zA-Z0-9]+)[\\s]*");

        if (std::regex_match(line, mr, r))
        {
            LOG_DEBUG("Detected StareInit line: " << line);

            LOG_DEBUG("Adding StareInit item: " << mr[1].str());

            StareInit = mr[1].str();

            return true;
        }

        return false;
    }

    bool attempt_to_read_finale(const std::string &line)
    {
        std::match_results<std::string::const_iterator> mr;

        std::regex r("[\\s]*Finale[\\s]*=[\\s]*\\{(([\\s]*[a-zA-Z0-9]+[\\s]*[,]{1}[\\s]*)*([\\s]*[a-zA-Z0-9]+[\\s]*){1})\\}");

        if (std::regex_match(line, mr, r))
        {
            LOG_DEBUG("Detected Finale line: " << line);

            std::regex ri("[a-zA-Z0-9]+");
            std::match_results<std::string::const_iterator> mri;

            std::string haystack = mr[1].str();

            while (regex_search(haystack, mri, ri))
            {
                LOG_DEBUG("Adding Finale item: " << mri.str());

                Finale.insert(mri.str());

                haystack = mri.suffix();
            }

            return true;
        }

        return false;
    }

public:
    void citire(const std::string filename)
    {
        std::ifstream file(filename);
        std::string line;

        while (std::getline(file, line))
        {
            if (!line.length() || line[0] == '#')
            {
                continue;
            }

            if (attempt_to_read_stari(line))
            {
                continue;
            }

            if (attempt_to_read_sigma(line))
            {
                continue;
            }

            if (attempt_to_read_delta(line))
            {
                continue;
            }

            if (attempt_to_read_stare_init(line))
            {
                continue;
            }

            if (attempt_to_read_finale(line))
            {
                continue;
            }

            LOG_WARNING("Invalid line: " << line);
        }
    }

    bool isValid() const
    {
        if (Stari.size() == 0)
        {
            LOG_ERROR("Multimea de stari este nedefinita!");

            return false;
        }

        if (Sigma.size() == 0)
        {
            LOG_ERROR("Alfabetul de intrare este nedefinit!");

            return false;
        }

        if (Delta.size() == 0)
        {
            LOG_ERROR("Functia de tranzitie este nedefinita!");

            return false;
        }

        for (auto &e0: Delta)
        {
            for (auto &e1: e0.second)
            {
                if (Stari.find(e0.first) == Stari.end())
                {
                    LOG_ERROR("Delta(" << e0.first << ", " << e1.first << ") = " << e1.second << ": " << e0.first << " nu se afla in multimea de stari!");

                    return false;
                }

                if (Sigma.find(e1.first) == Sigma.end())
                {
                    LOG_ERROR("Delta(" << e0.first << ", " << e1.first << ") = " << e1.second << ": " << e1.first << " nu se afla in alfabetul de intrare!");

                    return false;
                }

                if (Stari.find(e1.second) == Stari.end())
                {
                    LOG_ERROR("Delta(" << e0.first << ", " << e1.first << ") = " << e1.second << ": " << e1.second << " nu se afla in multimea de stari!");

                    return false;
                }
            }
        }

        if (StareInit.length() == 0)
        {
            LOG_ERROR("Starea initiala este nedefinita!");

            return false;
        }

        if (Stari.find(StareInit) == Stari.end())
        {
            LOG_ERROR("Starea initiala " << StareInit << " nu se afla in multimea de stari!");

            return false;
        }

        if (Finale.size() == 0)
        {
            LOG_ERROR("Multimea starilor finale este nedefinita!");

            return false;
        }

        for (auto &e: Finale)
        {
            if (Stari.find(e) == Stari.end())
            {
                LOG_ERROR("Starea finale " << e << " nu se afla in multimea de stari!");

                return false;
            }
        }

        return true;
    }

    void afisareDetaliata() const
    {
        if (!isValid())
        {
            return;
        }

        std::string prefix;

        prefix = "";
        std::cout << "Stari = {";
        for (auto &e: Stari)
        {
            std::cout << prefix << e;

            prefix = ", ";
        }
        std::cout << "}" << std::endl;

        prefix = "";
        std::cout << "Sigma = {";
        for (auto &e: Sigma)
        {
            std::cout << prefix << e;

            prefix = ", ";
        }
        std::cout << "}" << std::endl;

        for (auto &e0: Delta)
        {
            for (auto &e1: e0.second)
            {
                std::cout << "Delta(" << e0.first << ", " << e1.first << ") = " << e1.second << std::endl;
            }
        }

        std::cout << "StareInit = " << StareInit << std::endl;

        prefix = "";
        std::cout << "Finale = {";
        for (auto &e: Finale)
        {
            std::cout << prefix << e;

            prefix = ", ";
        }
        std::cout << "}" << std::endl;
    }

    void afisareScurta()
    {
        if (!isValid())
        {
            return;
        }

        std::string prefix;

        std::cout << "M = (";

        prefix = "";
        std::cout << "{";
        for (auto &e: Stari)
        {
            std::cout << prefix << e;

            prefix = ", ";
        }
        std::cout << "}, ";

        prefix = "";
        std::cout << "{";
        for (auto &e: Sigma)
        {
            std::cout << prefix << e;

            prefix = ", ";
        }
        std::cout << "}, ";

        std::cout << "Delta, ";

        std::cout <<  StareInit << ", ";

        prefix = "";
        std::cout << "{";
        for (auto &e: Finale)
        {
            std::cout << prefix << e;

            prefix = ", ";
        }
        std::cout << "})" << std::endl;

        std::cout << std::endl;

        size_t StariMaxLen = 0;

        std::for_each(Stari.begin(), Stari.end(), [&] (auto &e) {
            StariMaxLen = (e.size() > StariMaxLen ? e.size() : StariMaxLen);
        });

        size_t SigmaMaxLen = 0;

        std::for_each(Sigma.begin(), Sigma.end(), [&] (auto &e) {
            SigmaMaxLen = (e.size() > SigmaMaxLen ? e.size() : SigmaMaxLen);
        });

        std::cout << std::setw(static_cast<int>(SigmaMaxLen) + 1) << " " << " |";
        std::for_each(Stari.begin(), Stari.end(), [&] (auto &e) {
            std::cout << std::setw(static_cast<int>(StariMaxLen) + 2) << e;
        });

        std::cout << std::endl;

        std::cout << std::setw(static_cast<int>(SigmaMaxLen) + 1) << std::setfill('-') << "-" << "-+" << std::setw(static_cast<int>(Stari.size())*(static_cast<int>(StariMaxLen) + 2)) << std::setfill('-') << "-" << std::endl;

        std::for_each(Sigma.begin(), Sigma.end(), [&] (auto &e1) {
            std::cout << std::setw(static_cast<int>(SigmaMaxLen) + 1) << std::setfill(' ') << e1 << " |";

            std::for_each(Stari.begin(), Stari.end(), [&] (auto &e2) {
                if (Delta.find(e2) != Delta.end() && Delta[e2].find(e1) != Delta[e2].end())
                {
                    std::cout << std::setw(static_cast<int>(StariMaxLen) + 2) << Delta[e2][e1];
                }
                else
                {
                    std::cout << std::setw(static_cast<int>(StariMaxLen) + 2) << "MV";
                }
            });

            std::cout << std::endl;
        });

        std::cout << std::endl;
    }

    uint8_t verificare(const std::string cuvant)
    {
        std::cout << "Verificare: " << cuvant << std::endl;

        std::string stare = StareInit;

        std::regex r("[a-zA-Z0-9\\+=]+");
        std::match_results<std::string::const_iterator> mr;

        std::string haystack = cuvant;

        while (regex_search(haystack, mr, r))
        {
            if (Sigma.find(mr.str()) == Sigma.end())
            {
                std::cout << "Simbolul " << mr.str() << " nu se afla in alfabetul de intrare!" << std::endl;

                return 0;
            }

            haystack = mr.suffix();
        }

        haystack = cuvant;

        while (regex_search(haystack, mr, r))
        {
            std::cout << "Delta(" << stare << ", \"";

            bool begin = true;
            for (auto &e: haystack)
            {
                if (e != ' ' || !begin)
                {
                    std::cout << e;

                    begin = false;
                }
                else if (e != ' ')
                {
                    begin = false;
                }
            }
            std::cout << "\") = ";

            if (Delta.find(stare) != Delta.end() && Delta[stare].find(mr.str()) != Delta[stare].end())
            {
                stare = Delta[stare][mr.str()];
            }
            else
            {
                std::cout << "Multimea Vida - blocaj" << std::endl;

                return 1;
            }

            haystack = mr.suffix();
        }

        std::cout << stare;

        if (Finale.find(stare) == Finale.end())
        {
            std::cout << ", nu apartine Finale - neacceptat" << std::endl;

            return 2;
        }

        std::cout << ", apartine Finale - acceptat" << std::endl;

        return 3;
    }
};

int main(int argc, const char **argv)
{
    AFD afd;

    afd.citire("/Users/andreig/Documents/Xcode/LimbajeFormale/T4-AFD/T4-AFD/input.txt");

    std::cout << std::endl;

    afd.afisareDetaliata();

    std::cout << std::endl;

    afd.afisareScurta();

/*
    if (afd.isValid())
    {
        std::cout << std::endl;

        afd.verificare("a b b a");

        std::cout << std::endl;

        afd.verificare("a a b b a");

        std::cout << std::endl;

        afd.verificare("a b");
    }
*/

    if (afd.isValid())
    {
        while (true)
        {
            std::string cuvant;

            std::cout << std::endl << "Cuvant: ";

            std::getline(std::cin, cuvant);

            afd.verificare(cuvant);
        }
    }

    return 0;
}


/*
# input.txt
#
Stari = {q0, q1, q2}
Sigma = {a, b}
Delta(q0, a) = q1
Delta(q1, b) = q2
Delta(q2, a) = q2
Delta(q2, b) = q2
StareInit = q0
Finale = {q2}

#Stari = {q0, q1, q2, q3, q4, q5}
#Sigma = {1, +, =}
#Delta(q0, 1) = q1
#Delta(q1, 1) = q1
#Delta(q1, +) = q2
#Delta(q2, 1) = q3
#Delta(q3, 1) = q3
#Delta(q3, =) = q4
#Delta(q4, 1) = q5
#Delta(q5, 1) = q5
#StareInit = q0
#Finale = {q5}

# example: 1 1 1 + 1 1 = 1 1 1 1 1

#Stari = {q0, q1, q2, q3, q4, q5, q6, q7}
#Sigma = {if, 0, 1, a, b, ==, then, print, exit, else}
#Delta(q0, if) = q1
#Delta(q1, 0) = q2
#Delta(q1, 1) = q2
#Delta(q1, a) = q2
#Delta(q1, b) = q2
#Delta(q2, ==) = q3
#Delta(q3, 0) = q4
#Delta(q3, 1) = q4
#Delta(q3, a) = q4
#Delta(q3, b) = q4
#Delta(q4, then) = q5
#Delta(q5, print) = q6
#Delta(q6, 0) = q7
#Delta(q6, 1) = q7
#Delta(q6, a) = q7
#Delta(q6, b) = q7
#Delta(q5, exit) = q7
#Delta(q7, else) = q5
#StareInit = q0
#Finale = {q7}

# example: if b == 0 then print 1
# example: if a == 1 then print a else exit
*/

/*
Output:


Stari = {q0, q1, q2}
Sigma = {a, b}
Delta(q0, a) = q1
Delta(q1, b) = q2
Delta(q2, a) = q2
Delta(q2, b) = q2
StareInit = q0
Finale = {q2}

M = ({q0, q1, q2}, {a, b}, Delta, q0, {q2})

   |  q0  q1  q2
---+------------
 a |  q1  MV  q2
 b |  MV  q2  q2


Cuvant: a b a a
Verificare: a b a a
Delta(q0, "a b a a") = Delta(q1, "b a a") = Delta(q2, "a a") = Delta(q2, "a") = q2, apartine Finale - acceptat

Cuvant: a a b a
Verificare: a a b a
Delta(q0, "a a b a") = Delta(q1, "a b a") = Multimea Vida - blocaj

Cuvant: a
Verificare: a
Delta(q0, "a") = q1, nu apartine Finale - neacceptat

*/