main.cpp

/* 
 * File:   main.cpp
 * Author: frex
 *
 * Created on February 19, 2016, 9:56 PM
 */

#include <vector>
#include <string>
#include <iostream>
#include <sstream>

class PARule
{
public:
    std::string state;
    std::string token;
    std::string stacktop;
    std::string newstate;
    std::string newstacktop; //separated by ;
};

class PushdownAutomata
{
public:

    void setState(const std::string& state)
    {
        m_state = state;
    }

    void addRule(const PARule& rule)
    {
        m_rules.push_back(rule);
    }

    bool transition(const std::string& token)
    {
        for(const PARule& rule : m_rules)
        {
            if(rule.state == m_state && rule.token == token && rule.stacktop == getStackTop())
            {
                m_state = rule.newstate;
                popStackTop();
                pushStackTop(rule.newstacktop);
                return true;
            }
        }
        return false;
    }

    bool isStackEmpty() const
    {
        return m_stack.empty();
    }

private:

    const std::string& getStackTop() const
    {
        if(m_stack.empty())
            return m_empty;

        return m_stack.back();
    }

    void popStackTop()
    {
        if(!m_stack.empty())
            m_stack.pop_back();
    }

    void pushStackTop(const std::string& newstacktop)
    {
        std::istringstream ss(newstacktop);
        std::string str;
        while(std::getline(ss, str, ';'))
            m_stack.push_back(str);
    }

    std::vector<PARule> m_rules;
    std::vector<std::string> m_stack;
    const std::string m_empty;
    std::string m_state;

};

int main(int argc, char ** argv)
{
    PushdownAutomata pa;
    pa.setState("start");
    PARule rule;
    rule.state = "start";
    rule.newstate = "start";

    rule.token = "a";
    rule.stacktop = "";
    rule.newstacktop = "A";
    pa.addRule(rule);

    rule.token = "b";
    rule.stacktop = "";
    rule.newstacktop = "B";
    pa.addRule(rule);

    rule.token = "a";
    rule.stacktop = "A";
    rule.newstacktop = "A;A";
    pa.addRule(rule);

    rule.token = "a";
    rule.stacktop = "B";
    rule.newstacktop = "";
    pa.addRule(rule);

    rule.token = "b";
    rule.stacktop = "B";
    rule.newstacktop = "B;B";
    pa.addRule(rule);

    rule.token = "b";
    rule.stacktop = "A";
    rule.newstacktop = "";
    pa.addRule(rule);

    std::string text;
    while(std::cin >> text)
    {
        for(char c : text)
        {
            if(!pa.transition(std::string(1u, c)))
            {
                std::cout << "ERROR" << std::endl;
                break;
            }
        }//for c in text
        std::cout << text << ':' << std::boolalpha << pa.isStackEmpty() << std::endl;
    }
    return 0;
}