foil evaluator

#include <vector>
#include <iterator>
#include <algorithm>
#include <string>
#include <set>
#include <sstream>
#include <iostream>
#include <cassert>
#include <cstring>
#include <map>
#include <utility>

class exp_parser
{
private:
    typedef std::string::size_type str_size;

public:
    exp_parser() : operator_str("+-")
    {
        operators =  {'+', '-'};
    }

    ~exp_parser() = default;
    exp_parser(const exp_parser& rhs) = default;
    exp_parser& operator=(const exp_parser& rhs) = default;

    std::string simplify(const std::string& expression);

private:
    std::set<char> operators;
    std::string operator_str;

    void break_expression(const std::string& expression, std::vector<std::vector<std::string>>& vec);

    std::string reduce(const std::vector<std::vector<std::string>>& vec);
    std::string multiply(const std::string& s1, const std::string& s2);
    str_size last_digit(const std::string& s);
    std::string simplify_power(const std::string& expression);
    std::string group_like_terms(const std::string& expression);

    std::pair<char, str_size> find_any_of(const std::string& expression, const std::string& values, str_size start_pos = 0);

    std::string remove_duplicate_symbols(const std::string& expression);
};

int safe_atoi(const std::string& input)
{
    int temp;
    std::stringstream ss(input);
    ss >> temp;
    return temp;
}

using namespace std;

void exp_parser::break_expression(const string& expression, vector<vector<string>>& vec)
{
    size_t i = 0;
    stringstream ss, op;

    string::const_iterator it = expression.begin() + 1;
    while(it != expression.end()) {
        if((*it) == ')') {
            vec[i].push_back(ss.str());
            ss.str("");
            ++i;
        }
        else if(operators.find(*it) != operators.end()) {
            vec[i].push_back(ss.str());
            op << *it;
            vec[i].push_back(op.str());
            ss.str("");
            op.str("");
        }
        else if((*it) != '(' && (*it) != ' ') {
            ss << *it;
        }
        ++it;
    }
}

string exp_parser::reduce(const vector<vector<string>>& vec)
{
    if(vec.size() == 2) {
        stringstream ss;
        auto it = vec.begin();
        auto it2 = vec.begin() + 1;
        char curr_op = '+';

        for(auto str_it = it->begin(); str_it != it->end(); ++str_it) {
            if(operators.find(str_it->at(0)) != operators.end()) {
                ss << *str_it;
                curr_op = str_it->at(0);
            } else {
                for(auto str_it2 = it2->begin(); str_it2 != it2->end(); ++str_it2) {
                    if(operators.find(str_it2->at(0)) != operators.end()) {
                        ss << curr_op << *str_it2;
                    } else {
                        ss << multiply(*str_it, *str_it2);
                    }
                }
            }
        }
        return ss.str();
    }
    else {
        //Reduce the first two in the set
        stringstream reduce_1;
        vector<vector<string>> first_set(vec.begin(), vec.begin() + 2);
        reduce_1 << "(" << reduce(first_set) << ")";
        string dupes_removed = remove_duplicate_symbols(reduce_1.str());

        //Now we can create a system with (n-1) expressions to evaluate
        //and recurse on that (since polynomial multiplication is closed)
        //to get down to our base case
        vector<vector<string>> smaller_by_one(vec.size() - 1);
        break_expression(dupes_removed, smaller_by_one);
        auto it = vec.begin() + 2;
        size_t i = 1;

        while(it != vec.end()) {
            smaller_by_one[i] = *it;
            ++i;
            ++it;
        }

        return reduce(smaller_by_one);
    }
}

string exp_parser::simplify_power(const string& expression)
{
    int power = 1;

    stringstream ss;
    char start;
    string::const_iterator it = expression.begin();

    while(it != expression.end()) {
        if(operators.find(*it) == operators.end()) {
            if(!isdigit(*it)) {
                start = *it;
                auto it2 = it;
                while(it2 != expression.end() && *(++it2) == start) {
                    ++power;
                }
                if(power > 1) {
                    ss << start << "^" << power;
                    power = 1;
                    it = it2;
                } else {
                    while(it != it2) {
                        ss << *it;
                        ++it;
                    }
                }
            } else {
                ss << *it;
                ++it;
            }
        } else {
            ss << *it;
            ++it;
        }
    }

    return ss.str();
}

string exp_parser::group_like_terms(const string& expression)
{
    map<string, int> term_map;
    stringstream ss, digit_ss;
    auto it = expression.begin();
    exp_parser::str_size next_operator =  0;
    char current_op;
    pair<char, exp_parser::str_size> next_op;

    (expression[0] == '-') ? (current_op = '-') : (current_op = '+');

    while(next_operator != expression.size()) {
        next_op = find_any_of(expression, operator_str, next_operator + 1);
        next_operator = next_op.second;
        digit_ss << current_op;
        current_op = next_op.first;

        if(next_operator == string::npos) {
            next_operator = expression.size();
        }

        auto it2 = expression.begin() + next_operator;

        while(isdigit(*it)) {
            digit_ss << *it;
            ++it;
        }

        string key(it, it2);
        term_map[key] += safe_atoi(digit_ss.str());
        digit_ss.str("");
        it = it2 + 1;
    }

    for(auto it = term_map.begin(); it != term_map.end(); ++it) {
        ss << it->second << it->first << "+";
    }
    string to_ret = ss.str();
    return string(to_ret.begin(), to_ret.end() - 1);
}

pair<char, exp_parser::str_size> exp_parser::find_any_of(const string& expression, const string& values, exp_parser::str_size start_pos)
{
    if(start_pos > expression.size()) {
        return pair<char, exp_parser::str_size>(static_cast<char>(0), string::npos);
    }

    for(auto it = expression.begin() + start_pos; it != expression.end(); ++it) {
        for(auto it2 = values.begin(); it2 != values.end(); ++it2) {
            if(*it == *it2) {
                return pair<char, exp_parser::str_size>(*it, start_pos);
            }
        }
        ++start_pos;
    }

    return pair<char, exp_parser::str_size>(static_cast<char>(0), string::npos);
}

string exp_parser::remove_duplicate_symbols(const std::string& expression)
{
    stringstream ss;
    auto it = expression.begin();

    while(it != expression.end() - 1) {
        if(operators.find(*it) != operators.end() && operators.find(*(it+1)) != operators.end()) {
            if(*it == '-' && *(it+1) == '-') {
                ss << '+';
            }
            else if(*it == '-') {
                ss << '-';
            }
            else if(*(it+1) == '-') {
                ss << "-";
            } else {
                ss << "+";
            }
            it += 2;
        } else {
            ss << *it;
            ++it;
        }
    }

    ss << *(expression.end() - 1);
    return ss.str();
}

string exp_parser::multiply(const string& s1, const string& s2)
{
    if(s1.size() < 1 || s2.size() < 1) { return ""; }

    stringstream result_ss;
    exp_parser::str_size non_digit1 = last_digit(s1);
    exp_parser::str_size non_digit2 = last_digit(s2);

    int s1_intval = safe_atoi(string(s1.begin(), s1.begin() + non_digit1));
    int s2_intval = safe_atoi(string(s2.begin(), s2.begin() + non_digit2));
    int final_int_value = s1_intval * s2_intval;
    result_ss << final_int_value;
    int final_int_length = result_ss.str().size();

    for_each(s1.begin() + non_digit1, s1.end(), [&result_ss](char v) { result_ss << v; });
    for_each(s2.begin() + non_digit2, s2.end(), [&result_ss](char v) { result_ss << v; });

    string result = result_ss.str();
    sort(result.begin() + final_int_length, result.end());
    return result;
}

exp_parser::str_size exp_parser::last_digit(const string& s)
{
    exp_parser::str_size non_digit = s.find_first_not_of("-+0123456789");
    if(non_digit == string::npos) { return s.size(); }
    return non_digit;
}

//An expression below is defined as anything delineated by (), thus (2x+1),
//(3x+4y+z), and so on are all expressions.

string exp_parser::simplify(const std::string& expression)
{
    //Since we need to allocate the exact amount of space for our
    //vector of vectors (as we're using [], not push_back),
    //we need some way to see how many expressions we have.
    //Utilize the count of '(' for this - thus if we have an unbalanced
    //expression, everything will fall over
    ptrdiff_t vec_size = count(expression.begin(), expression.end(), '(');

    //If we have 0 or 1 brakcets, then we have either a constant expression
    //or an expression like (ax+b), which is already simplified
    if(vec_size <= 1) { return expression; }

    //Allocate our vector of vectors with the proper amount of space
    vector<vector<string>> pv(vec_size);
    //Breaks each of our expressions into the component parts,
    //adding the parts of expression number i to the vector contained in
    //pv[i]
    break_expression(expression, pv);
    //This collapses all the expressions down into a single
    //expression
    string reduced = reduce(pv);
    //Because of the way reduce is implemented, we will get repeated
    //operators, like +-, -+, -- or ++. This replaces each of these with
    //their single operator equivalents.
    string de_duplicated = remove_duplicate_symbols(reduced);
    //Our expression then needs all the like terms grouped,
    //for example, 6x + 5y + 5x + 6y == 11x + 11y
    string grouped = group_like_terms(de_duplicated);
    //Finally, anything with repeated values such as 3xxx is
    //converted to its proper power form, thus 3x^3
    string simple = simplify_power(grouped);
    //Some of the above methods may re-introduce duplicate operators
    //along the way, so we require a final cull
    return remove_duplicate_symbols(simple);
}

int main()
{
    exp_parser parser;
    string simplified = parser.simplify("(2x+3)(4x+2)(5x+1)(6x+5)");
    std::cout << simplified << "\n";
    return 0;
}