//
//  Experimental Spirit parser
//
#include <cctype>
#include <cassert>

///////////////////////////////////////////////////////////////////////////////
struct nil_t {};    //  As always... Our special nil type...

///////////////////////////////////////////////////////////////////////////////
template <typename DerivedT>
struct parser {

    DerivedT const& derived() const { return *static_cast<DerivedT const*>(this); }
};

///////////////////////////////////////////////////////////////////////////////
struct match {

    operator bool() const { return data >= 0; }
    int data;
};

///////////////////////////////////////////////////////////////////////////////
template <typename IteratorT>
struct basic_parser_arg {

    typedef IteratorT iterator_t;
    typedef match result_t;

    basic_parser_arg(IteratorT const& first_, IteratorT const& last_)
    :   first(first_), last(last_) {}

    static match
    no_match()
    { match m; m.data = -1; return m; }

    static match
    create_match(unsigned len, IteratorT const& first, IteratorT const& last)
    { match m; m.data = len; return m; }

    static void
    concat_match(match& lhs, match const& rhs)
    { assert(lhs && rhs); lhs.data += rhs.data; }

    IteratorT first;
    IteratorT const last;
};
///////////////////////////////////////////////////////////////////////////////
template <typename CharT>
struct char_parser : parser<char_parser<CharT> > {

    char_parser(CharT ch_)
    :   ch(ch_) {}

    template <typename ArgT>
    typename ArgT::result_t
    parse(ArgT& arg) const
    {
        if ((arg.first != arg.last) && (ch == *arg.first))
        {
            typename ArgT::iterator_t s(arg.first);
            ++arg.first;
            return arg.create_match(1, s, arg.first);
        }
        return arg.no_match();
    }

    CharT ch;
};

template <typename CharT>
char_parser<CharT>
ch_p(CharT ch)
{
    return char_parser<CharT>(ch);
}

///////////////////////////////////////////////////////////////////////////////
struct digit_parser : parser<digit_parser> {

    template <typename ArgT>
    typename ArgT::result_t
    parse(ArgT& arg) const
    {
        if ((arg.first != arg.last) && std::isdigit(*arg.first))
        {
            typename ArgT::iterator_t s(arg.first);
            ++arg.first;
            return arg.create_match(1, s, arg.first);
        }
        return arg.no_match();
    }
};

digit_parser const digit_p = digit_parser();

///////////////////////////////////////////////////////////////////////////////
template <typename LHS, typename RHS>
struct sequence : public parser<sequence<LHS, RHS> > {

    sequence(LHS const& lhs_, RHS const& rhs_)
    :   lhs(lhs_), rhs(rhs_) {}

    template <typename ArgT>
    typename ArgT::result_t
    parse(ArgT& arg) const
    {
        typename ArgT::result_t ra, rb;
        if ((ra = lhs.parse(arg)) && (rb = rhs.parse(arg)))
        {
            arg.concat_match(ra, rb);
            return ra;
        }
        return arg.no_match();
    }

    LHS lhs;
    RHS rhs;
};

template <typename LHS, typename RHS>
sequence<LHS, RHS>
operator>>(parser<LHS> const& lhs, parser<RHS> const& rhs)
{
    return sequence<LHS, RHS>(lhs.derived(), rhs.derived());
}

template <typename LHS>
sequence<LHS, char_parser<char> >
operator>>(parser<LHS> const& lhs, char rhs)
{
    return sequence<LHS, char_parser<char> >(lhs.derived(), rhs);
}

template <typename RHS>
sequence<char_parser<char>, RHS>
operator>>(char lhs, parser<RHS> const& rhs)
{
    return sequence<char_parser<char>, RHS>(lhs, rhs.derived());
}

///////////////////////////////////////////////////////////////////////////////
template <typename LHS, typename RHS>
struct alternative : public parser<alternative<LHS, RHS> > {

    alternative(LHS const& lhs_, RHS const& rhs_)
    :   lhs(lhs_), rhs(rhs_) {}

    template <typename ArgT>
    typename ArgT::result_t
    parse(ArgT& arg) const
    {
        { // scope for save
            typename ArgT::iterator_t save = arg.first;
            if (typename ArgT::result_t r = lhs.parse(arg))
                return r;
            arg.first = save;
        }
        return rhs.parse(arg);
    }

    LHS lhs;
    RHS rhs;
};

template <typename LHS, typename RHS>
alternative<LHS, RHS>
operator|(parser<LHS> const& lhs, parser<RHS> const& rhs)
{
    return alternative<LHS, RHS>(lhs.derived(), rhs.derived());
}

///////////////////////////////////////////////////////////////////////////////
template <typename SubjectT>
struct kleene_star : public parser<kleene_star<SubjectT> > {

    kleene_star(SubjectT const& subject_)
    :   subject(subject_) {}

    template <typename ArgT>
    typename ArgT::result_t
    parse(ArgT& arg) const
    {
        typename ArgT::result_t r = arg.create_match(0, arg.first, arg.first);
        while (true)
        {
            typename ArgT::iterator_t save = arg.first;
            if (typename ArgT::result_t next = subject.parse(arg))
            {
                save = arg.first;
                arg.concat_match(r, next);
            }
            else
            {
                arg.first = save;
                return r;
            }
        }
    }

    SubjectT subject;
};

template <typename SubjectT>
kleene_star<SubjectT>
operator*(parser<SubjectT> const& subject)
{
    return kleene_star<SubjectT>(subject.derived());
}

///////////////////////////////////////////////////////////////////////////////
template <typename FirstT, typename RestT = nil_t>
struct grammar;

template <int ID, typename RHS>
struct rule;

namespace impl {

    template <int N, typename GrammarT>
    struct get_rule {

        typedef typename get_rule<N, typename GrammarT::rest_t>::type type;
        static type const&
        get(GrammarT const& g)
        {
            return get_rule<N, typename GrammarT::rest_t>::get(g.rest);
        }
    };

    template <int ID, typename RHS, typename RestT>
    struct get_rule<ID, grammar<rule<ID, RHS>, RestT> > {

        typedef rule<ID, RHS> type;
        static type const&
        get(grammar<rule<ID, RHS>, RestT> const& g)
        {
            return g.first;
        }
    };
}

template <typename ArgT, typename GrammarT>
struct grammar_arg : public ArgT {

    grammar_arg(ArgT const& arg, GrammarT const& rules_)
    :   ArgT(arg), rules(rules_) {}

    template <int N>
    typename ArgT::result_t
    use_rule()
    {
        return impl::get_rule<N, GrammarT>::get(rules).parse(*this);
    }

    GrammarT const& rules;
};

template <typename FirstT, typename RestT>
struct grammar : parser<grammar<FirstT, RestT> > {

    typedef grammar<FirstT, RestT> self_t;
    typedef FirstT first_t;
    typedef RestT rest_t;

    grammar(FirstT const& first_, RestT const& rest_)
    :   first(first_), rest(rest_) {}

    template <typename ArgT>
    typename ArgT::result_t
    parse(ArgT& arg) const
    {
        grammar_arg<ArgT, self_t> g_arg(arg, *this);
        return impl::get_rule<0, self_t>::get(*this).parse(g_arg);
    }

    FirstT first;
    RestT rest;
};

///////////////////////////////////////////////////////////////////////////////
template <int ID, typename RHS>
struct rule : public parser<rule<ID, RHS> > {

    rule(RHS const& rhs_)
    :   rhs(rhs_) {}

    template <typename ArgT>
    typename ArgT::result_t
    parse(ArgT& arg) const
    {
        return rhs.parse(arg);
    }

    RHS rhs;
};

template <int ID1, typename RHS1, int ID2, typename RHS2>
grammar<rule<ID1, RHS1>, grammar<rule<ID2, RHS2>, nil_t> >
operator,(rule<ID1, RHS1> const& lhs, rule<ID2, RHS2> const& rhs)
{
    return grammar<rule<ID1, RHS1>, grammar<rule<ID2, RHS2>, nil_t> >
        (lhs, grammar<rule<ID2, RHS2>, nil_t>(rhs, nil_t()));
}

template <typename FirstT, typename RestT, int ID1, typename RHS1>
grammar<rule<ID1, RHS1>, grammar<FirstT, RestT> >
operator,(grammar<FirstT, RestT> const& lhs, rule<ID1, RHS1> const& rhs)
{
    return grammar<rule<ID1, RHS1>, grammar<FirstT, RestT> >(rhs, lhs);
}

///////////////////////////////////////////////////////////////////////////////
template <int ID>
struct rule_id : public parser<rule_id<ID> > {

    template <typename ArgT>
    typename ArgT::result_t
    parse(ArgT& arg) const
    {
        return arg.template use_rule<ID>();
    }

    template <typename RHS>
    rule<ID, RHS>
    operator=(const parser<RHS>& rhs) const
    {
        return rule<ID, RHS>(rhs.derived());
    }
};

///////////////////////////////////////////////////////////////////////////////




///////////////////////////////////////////////////////////////////////////////
//
//  TEST
//
///////////////////////////////////////////////////////////////////////////////
#include <iostream>
using namespace std;

match
parse(char const* first, char const* last)
{
    basic_parser_arg<char const*>   parg(first, last);

    rule_id<0> expression;
    rule_id<1> term;
    rule_id<2> factor;

    return (

        factor      =   digit_p
                    |   '(' >> expression >> ')'
                    |   ('-' >> factor)
                    ,

        term        =   factor >>
                    *(  ('*' >> factor)
                    |   ('/' >> factor)
                    )
                    ,

        expression  =   term >>
                    *(  ('+' >> term)
                    |   ('-' >> term)
                    )

    ).parse(parg);
}

int
main()
{
    while (true)
    {
        char str[256];
        cin.getline(str, 256);
        if (str[0] == 'q' || str[0] == 'Q')
            break;

        match m = parse(str, str+strlen(str));
        cout << "match.length = " << m.data << '\n';
    }
}