#include <string>
#include <vector>
#include <iterator>
#include <iostream>

using string_iterator = std::string::const_iterator;

class Base_Parser
{
public:

    virtual ~Base_Parser() = default;
    virtual bool parse(string_iterator& begin, string_iterator end) const = 0;
    virtual Base_Parser* clone() const = 0;
    
};

class Match : public Base_Parser
{
public:

    Match(std::string const& match)
        : match { match }
    {
    }

    bool parse(string_iterator& begin, string_iterator end) const override
    {
        if (std::distance(begin, end) < match.size())
        {
            return false;
        }
        
        string_iterator saved { begin };
        std::advance(begin, match.size());

        std::string prefix { saved, begin };
        if (match == prefix)
        {
            return true;
        }
        begin = saved;
        return false;
    }

    Base_Parser* clone() const
    {
        return new Match { match };
    }
    
private:

    std::string match;
    
};

class Combination : public Base_Parser
{
public:

    Combination(std::vector<Base_Parser*> const& parsers)
        : parsers { parsers }
    {
    }

    ~Combination()
    {
        for (Base_Parser* parser : parsers)
        {
            delete parser;
        }
    }
    
protected:

    std::vector<Base_Parser*> clone_parsers() const
    {
        std::vector<Base_Parser*> cloned_parsers { };
        for (Base_Parser* parser : parsers)
        {
            cloned_parsers.push_back(parser->clone());
        }
        return cloned_parsers;
    }
    
    std::vector<Base_Parser*> parsers { };
};

class Alternate : public Combination
{
public:

    using Combination::Combination;
    
    bool parse(string_iterator& begin, string_iterator end) const override
    {
        for (Base_Parser* parser : parsers)
        {
            if (parser->parse(begin, end))
            {
                return true;
            }
        }
        return false;
    }

    Base_Parser* clone() const override
    {
        return new Alternate { clone_parsers() };
    }
    
};

class Sequence : public Combination
{
public:
    
    using Combination::Combination;

    bool parse(string_iterator& begin, string_iterator end) const override
    {
        string_iterator saved { begin };
        for (Base_Parser* parser : parsers)
        {
            if (!parser->parse(begin, end))
            {
                begin = saved;
                return false;
            }
        }
        return true;
    }

    Base_Parser* clone() const override
    {
        return new Sequence { clone_parsers() };
    }
    
};

int main()
{

    Alternate variable_parser
    {
        {
            new Match { "x" },
            new Match { "y" }
        }
    };

    Alternate operator_parser
    {
        {
            new Match { "+" },
            new Match { "-" }
        }
    };
    
    Sequence basic_parser
    {
        {
            variable_parser.clone(),
            operator_parser.clone(),
            variable_parser.clone()
        }
    };

    Sequence parenthesis_parser
    {
        {
            new Match { "(" },
            basic_parser.clone(),
            new Match { ")" }
        }
    };

    Sequence single_parenthesis_parser
    {
        {
            new Match { "(" },
            variable_parser.clone(),
            new Match { ")" }
        }
    };
    
    Alternate expression_parser
    {
        {
            single_parenthesis_parser.clone(),
            parenthesis_parser.clone(),
            basic_parser.clone()
        }
    };          
    
    std::string line;
    while (std::getline(std::cin, line))
    {
        std::string::const_iterator current { std::cbegin(line) };
        if (expression_parser.parse(current, std::cend(line)))
        {
            std::cout << "Matched!" << std::endl;
        }
        else
        {
            std::cout << "Didn't match!" << std::endl;
        }
    }
    
}