#include <iostream>
#include <random>
#include <string>
#include <vector>
#include <sstream>
#include <algorithm>
#include <stdexcept>
#include <functional>
#include <cctype>
#include <numeric>
#include <ctime>

using namespace std;

#ifndef NDEBUG
bool debugOutput = true;
#else
bool debugOutput = false;
#endif

default_random_engine generator;

void debugPrint( string in ) {
    if( debugOutput )
        cout << in << endl;
}

typedef vector<string> StringList;

StringList mergeArguments( int argc , char* argv[] )
{
    stringstream merged;
    for( int i=1 ; i<argc ; ++i ) // argv[0] is the program path.
    {
        merged << argv[i];
    }

    // Reset the stream.
    merged = stringstream(merged.str());
    StringList rv;
    while( merged.good() )
    {
        string temp;
        getline( merged , temp , ';' );
        rv.push_back( temp );
    }
    return rv;
}

// Parse the dice roll.
int parseArg( const string& in );

int main( int argc , char* argv[] )
{
    generator.seed(time(nullptr));
    // Check that the argument exists.
    if( argc < 2 ) {
        debugPrint( "Nothing supplied." );
        return -1;
    }

    // Stuff all the arguments together, for processing. The argv is split by spaces, but I want to ignore spaces and split by semi-colons.
    const auto argList = mergeArguments( argc , argv );

    // Handle top level arguments: -help and -debug
    if( end(argList) != find( begin(argList),end(argList) , "-debug" ) )
    {
        debugOutput = true;
        debugPrint( "Turning on debug output." );

    }
    if( end(argList) != find( begin(argList),end(argList) , "-help" ) )
    {
        debugPrint( "Argument found: '-help'" );
        cout << "Dice Roller, by /u/arkadye\n"
            "Usage dice_roller [args]\n"
            "Valid args:\n"
            "\t-debug: turns on debug messages.\n"
            "\t-help: displays this message.\n"
            "\tA dice roll. Supported syntax includes:\n"
            "\t\tNdX: rolls N X-sided dice\n"
            "\t\tNdXkY: roll N X-sided dice and keep Y results\n"
            "\t\tNdXsY: roll N X-sided dice, and count the results that are Y or higher.\n"
            "\t\tNdXsYrZ: as above, but dice scoring Z or higher are counted and then rerolled.\n"
            "\t\tConstant values: put '3' into an expression to get '3' out. Integers only, commas and dots are ignored.\n"
            "\t\tMultiplication: use 'x' or '*' to multiply two dice rolls, or by a constant.\n"
            "\t\tAddition / subtraction: '+' and '-' are both supported.\n"
            "\t\tBrackets work as expected.\n"
            "\tIf numbers are omitted, they are assumed to be 1, so d6 = 1d6, 2d6- = 2d6 - 1\n";
        return 0;
    }

    for( const auto& arg : argList )
    {
        if( arg != "-debug" )
        {
            try
            {
                const auto val = parseArg(arg);
                cout << "Roll: " << arg << " - Result: " << val << endl;
            } catch( exception ex )
            {
                cout << "Failed roll: " << arg << "Reason: " << ex.what() << endl;
            }
        }
    }
    cin.get();
    return 0;

}

vector<int> rollDice( int no_dice , int no_sides )
{
    if( no_dice <= 0 )
    {
        stringstream message;
        message << no_dice << " requested. Returning no values." ;
        debugPrint( message.str() );
    }
    vector<int> result;
    result.reserve( no_dice );
    uniform_int_distribution<> die(1 , no_sides );
    stringstream message;
    message << "Rolling " << no_dice << " " << no_sides << "-sided dice. Results:";
    for( int i(0) ; i<no_dice ; ++i )
    {
        const int value = die(generator);
        message << " " << value;
        result.push_back( value );
    }
    debugPrint( message.str() );
    return result;
}

int NdXkY( int no_dice , int no_sides , int keep )
{
    auto rolls = rollDice( no_dice , no_sides );
    if( keep >= no_dice )
    {
        const int result = accumulate( begin(rolls) , end(rolls) , 0 );
        debugPrint( "Total: " + to_string(result) );
        return result;
    }
    nth_element( begin(rolls) , begin(rolls)+keep , end(rolls) , [](int l , int r) { return l>r; } );
    const int result = accumulate( begin(rolls) , begin(rolls)+keep , 0 );
    stringstream message;
    message << "Keep " << keep << ". Total: " << result;
    debugPrint( message.str() );
    return result;
}

int NdX( int no_dice , int no_sides )
{
    return NdXkY(no_dice,no_sides,no_dice);
}

int NdXsYrZ( int no_dice , int no_sides , int success_val , int reroll_val )
{
    const auto rolls = rollDice( no_dice , no_sides );
    int successes = count_if( begin(rolls) , end(rolls) , [&](int in) { return in > success_val; } );
    stringstream message;
    message << "Success threshold: " << success_val << ". " << successes << " successes";
    if( reroll_val <= no_sides )
    {
        int rerolls = count_if( begin(rolls) , end(rolls) , [&](int in) { return in > reroll_val; } );
        message << " and " << rerolls << " rerolls. (" << reroll_val << "+)";
        debugPrint( message.str() );
        successes += rerolls > 0 ? NdXsYrZ( rerolls , no_sides , success_val , reroll_val ) : 0;
    }
    debugPrint( "Total successes: " + to_string( successes ) );
    return successes;
}

int NdXsY( int no_dice , int no_sides , int success_val )
{
    return NdXsYrZ(no_dice,no_sides,success_val,no_sides+1);
}

// Returns position of the operator, or -1 if not found in reverse, or in.size() if not found forward.
int findIgnoringBrackets( const string& in , function<bool(char)> criteria , bool reverseDirection = false )
{
    int pos = reverseDirection ? in.size() - 1 : 0;
    int openBrackets = 0;
    auto openBracket = [&]() { ++openBrackets; };
    auto closeBracket = [&]() {
        if( --openBrackets < 0 )
            {
                stringstream message;
                message << "Error parsing expression \"" << in << "\". " <<
                    (reverseDirection ? "Unopened" : "Unclosed") << "bracket " <<
                    (reverseDirection ? "closed" : "opened") << " at position " << pos << ".";
                debugPrint( message.str() );
                throw runtime_error( message.str() );
            }
    };
    // Get the position of the operator
    do
    {
        // Handle brackets.
        switch( in[pos] )
        {
        case '(':
            reverseDirection ? closeBracket() : openBracket();
            break;
        case ')':
            reverseDirection ? openBracket() : closeBracket();
            break;
        default:
            break;
        }
        if( openBrackets == 0 && criteria( in[pos] ) )
            break;
        reverseDirection ? --pos : ++pos;
    } while( pos < int(in.size()) && pos >= 0 );
    if( openBrackets > 0 )
    {
        throw runtime_error( (reverseDirection ? "Unclosed" : "Unopened") + string(" brackets in expression \"") + in + "\"." );
    }
    return pos;
}

pair<string,string> splitString( const string& in , int pos )
{
    pair<string,string> rv;
    rv.first = in.substr(0,pos);
    rv.second = in.substr(pos+1,in.size());
    return rv;
}

int parseArg( const string& in )
{
    debugPrint( "Parsing argument: \"" + in + '"' );
    try
    {
        // Step 0: Check for the empty string:
        if( in.empty() ) {
            debugPrint( "Empty expression. Interpreting value as 1." );
            return 1;
        }

        // Step 1: Process brackets
        {
            if( *in.begin() == '(' && *in.rbegin() == ')' )
            {
                bool breakFound = false;
                int bracketsOpen = 0;
                for( int i(0) ; int(i<in.size()-1) ; ++i )
                {
                    switch( in[i] )
                    {
                    case '(':
                        ++bracketsOpen;
                        break;
                    case ')':
                        --bracketsOpen;
                        break;
                    default:
                        break;
                    }
                    if( bracketsOpen == 0 ) {
                        breakFound = true;
                        break;
                    }
                }
                if( !breakFound ) {
                    debugPrint( "Stripping brackets from front and back." );
                    return parseArg( in.substr(1,in.size()-2) );
                }
            }
        }

        // Step 2: Handle +/- arguments.
        {
            const int pos = findIgnoringBrackets( in , [](char in) { return (in=='+' || in=='-'); } , true );
            if( pos > -1 )
            {
                const auto args = splitString( in , pos );
                stringstream message;
                message << "Found operator " << in[pos] << " at position " << pos<<  ".\n"
                    "Left arg: " << args.first << "\nRight arg: " << args.second ;
                debugPrint( message.str() );
                if( in[pos] == '+' ) {
                    return parseArg(args.first) + parseArg(args.second);
                } else
                {
                    return parseArg(args.first) - parseArg(args.second);
                }
            }
        }

        // Step 3: Process multiplication.
        {
            const int pos = findIgnoringBrackets( in , [](char in) { return (in=='*' || in=='x'); } );
            // Check we found the operator, and parse each side.
            if( pos < int(in.size()) )
            {
                const auto args = splitString( in , pos );
                stringstream message;
                message << "Found operator " << in[pos] << " at position " << pos<<  ".\n"
                    "Left arg: " << args.first << "\nRight arg: " << args.second ;
                return parseArg(args.first) * parseArg(args.second);
            }
        }

        // Step 4: Process the 'd' operator. Process these backwards so 2d3d4 would roll 2 d3s, and then roll that many d4s.
        {
            const int pos = findIgnoringBrackets( in , [](char in){ return in=='d'; } , true );
            if( pos > -1 )
            {
                const auto d_args = splitString( in , pos );
                stringstream d_message;
                d_message << "Found operator 'd'. Left arg: " << d_args.first << " Right arg: " << d_args.second;
                debugPrint( d_message.str() );
                // Look for more args on the right.
                const int secondArgPos = findIgnoringBrackets( d_args.second , [](char in){ return (in=='k'||in=='s'); } );
                if( secondArgPos < int(d_args.second.size()) )
                {
                    // Process the 'k' first:
                    if( d_args.second[secondArgPos] == 'k' )
                    {
                        const auto k_args = splitString( d_args.second , secondArgPos );
                        stringstream k_message;
                        k_message << "Found operator 'k'. Left arg: " << k_args.first << " Right arg: " << k_args.second;
                        debugPrint( k_message.str() );
                        return NdXkY( parseArg(d_args.first) , parseArg(k_args.first) , parseArg(k_args.second) );
                    } else // It's 's'
                    {
                        const auto s_args = splitString( d_args.second , secondArgPos );
                        stringstream s_message;
                        s_message << "Found operator 's'. Left arg: " << s_args.first << " Right arg: " << s_args.second;
                        debugPrint( s_message.str() );
                        // Now check for the 'r' args:
                        const int r_argPos = findIgnoringBrackets( s_args.second , [](char in){ return in=='r'; } );
                        if( r_argPos < int(s_args.second.size()) ) // Found an r
                        {
                            const auto r_args = splitString( s_args.second , r_argPos );
                            stringstream r_message;
                            r_message << "Found operator 'r'. Left arg: " << r_args.first << " Right arg: " << r_args.second;
                            debugPrint( r_message.str() );
                            return NdXsYrZ( parseArg(d_args.first) , parseArg(s_args.first) , parseArg(r_args.first) , parseArg(r_args.second) );
                        } else // No 'r' arg found
                        {
                            return NdXsY( parseArg(d_args.first) , parseArg(s_args.first) , parseArg(s_args.second) );
                        }
                    }
                } else // No extra args found.
                {
                    return NdX( parseArg(d_args.first) , parseArg(d_args.second) );
                }
            }
        }

        // Step 5: Process constants
        {
            int val(0);
            for( auto ch : in )
            {
                if( isdigit(ch) )
                {
                    val *= 10;
                    val += ch - '0';
                } else
                {
                    switch( ch )
                    {
                    case '.':
                    case ',':
                        // Ignore.
                        break;
                    default:
                        // Error
                        {
                            stringstream message;
                            message << "Unidentified value: '" << ch << "' found in expression \"" << in << "\".";
                            throw runtime_error( message.str() );
                        }
                        break;
                    }
                }

            }
            stringstream message;
            message << "Found constant value: " << val << " from " << in << ".";
            debugPrint( message.str() );
            return val;
        }
    }
    catch( runtime_error ex )
    {
        stringstream message;
        message << ex.what() << " Part of expression \"" << in << "\".";
        throw runtime_error( message.str() );
    }
}