Math Programming Challenge

mathproblem.cpp

/*# The first 12 digits of pi are 314159265358. We can make these digits into an expression evaluating to 27182 (first 5 digits of e) as follows:

# 3141 * 5 / 9 * 26 / 5 * 3 - 5 * 8 = 27182   
# or 
# 3 + 1 - 415 * 92 + 65358 = 27182

# Notice that the order of the input digits is not changed. Operators (+,-,/, or *) are simply inserted to create the expression.  

# Write a function to take a list of numbers and a target, and return all the ways that those numbers can be formed into expressions evaluating to the target. Do not use the eval function in Python, Ruby or JavaScript

# For example: 
# f("314159265358", 27182) should print:      

# 3 + 1 - 415 * 92 + 65358 = 27182 
# 3 * 1 + 4 * 159 + 26535 + 8 = 27182 
# 3 / 1 + 4 * 159 + 26535 + 8 = 27182 
# 3 * 14 * 15 + 9 + 26535 + 8 = 27182 
# 3141 * 5 / 9 * 26 / 5 * 3 - 5 * 8 = 27182
*/
/////////////////////////////////////

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

using namespace std;

//"depth" parameter is needed to keep track of how many times the find() function has been called recursively
void find(const string& number, const float& target, vector<size_t>& index, size_t depth, int& count, int& ansCount) {
    const string ops("+-*/ ");
    if (depth == number.size() - 1)
    {
        ++count;						//increases count to track number of possible combinations
        vector<char> result(0);			//initalize vector to store series of digits and operators
        
        for (size_t i = 0; i < number.size() - 1; ++i)		//this for-loop will fill the "result" vector with alternating
        {													//elements from both "number" and
            result.push_back(number[i]);
            if (index[i] < ops.size() - 1) {				//"ops.size() - 1" to ensure a blank space is NOT inserted between digits
                
                result.push_back(ops[index[i]]);			//"index" vector is incrementally changed with each call to find()
            }												//to ensure the next consecutive unique combination is found - also
        }													//see the last for-loop of the find() function for more clarity
        result.push_back(number[number.size() - 1]);
        string concat = "";
        vector<string> expression;
        for (vector<char>::iterator it = result.begin(); it != result.end(); ++it) {
            if (*it >= '0' && *it <= '9') {
                concat.push_back(*it);                  //Breaks up operands and operators into different string "tokens"
                if (it == result.end() - 1) {
                    expression.push_back(concat);
                    concat.clear();
                }
            }
            else {
                expression.push_back(concat);
                concat.clear();
                concat.push_back(*it);
                expression.push_back(concat);
                concat.clear();
            }
        }
        
        //creating copy of "expression" in case we need to display the original math expression later;
        //"expression" will be changed/manipulated, so its original state needs to be preserved
        vector<string> statement;
        for (vector<string>::iterator it = expression.begin(); it != expression.end(); ++it) {
            statement.push_back(*it);
            //cout << *it;
        }
        
        //cout << "		";
        //the following two for-loops are placed in this order to account for order of operations
        //the "expression" vector will be shrunk down to just 1 element which contains the "answer"
        for (vector<string>::iterator it = expression.begin(); it != expression.end(); ++it) {
            if (*it == "*" || *it == "/") {
                float answer = 0;
                if (*it == "*") {
                    answer = (stof(*(it - 1))) * (stof(*(it + 1)));
                }
                if (*it == "/") {
                    answer = (stof(*(it - 1))) / (stof(*(it + 1)));
                }
                //above, the result is stored in "answer," so erase the unneeded info and replace it with "answer"
                it--;
                expression.erase(it, it + 3);
                expression.insert(it, to_string(answer));
                //this ran fine in xcode without it, but VS seems to need the line, "it = expression.begin();,"
                //to avoid a accessing outside bounds of the vector
                it = expression.begin();
                //uncomment below to print step-by-step operations for multiplication and division
                /*cout << "\n";
                 for (vector<string>::iterator iter = expression.begin(); iter != expression.end(); ++iter) {
                 cout << *iter;
                 }*/
            }
        }
        //same as about "*" & "/" for-loop, but this one handles "+" and "-"
        for (vector<string>::iterator it = expression.begin(); it != expression.end(); ++it) {
            if (*it == "+" || *it == "-") {
                float answer = 0;
                if (*it == "+") {
                    answer = (stof(*(it - 1))) + (stof(*(it + 1)));
                }
                if (*it == "-") {
                    answer = (stof(*(it - 1))) - (stof(*(it + 1)));
                }
                it--;
                expression.erase(it, it + 3);
                expression.insert(it, to_string(answer));
                it = expression.begin();
                //uncomment below to print step-by-step operations for addition and subtraction
                /*cout << "\n";
                 for (vector<string>::iterator iter = expression.begin(); iter != expression.end(); ++iter) {
                 cout << *iter;
                 }*/
            }
        }
        
        //will print "statement = answer" value only if "final answer," which is contained in expression[0]
        //matches the inital target value
        if (stof(expression[0]) == target/*true*/) {     //use "if (true)" instead to print all possibilities
            for (vector<string>::iterator it = statement.begin(); it != statement.end(); ++it) {
                cout << *it;
            }
            cout << " = " << expression[0] << "\n";
            ansCount++;
        }
        return;
    }
    
    for (size_t i = 0; i < ops.size(); ++i)
    {
        index[depth] = i;
        //cin.get();
        //using recursion to run through all possible combinations
        find(number, target, index, depth + 1, count, ansCount);
    }
}

int main()
{
    char again = 'n';
    do {
        //Requests manipulated number and target from user
        string number = "0";
        float target = 0;
        cout << "Enter a whole number to be manipulated: "; cin >> number;
        cout << "Enter a target number: "; cin >> target; cout << "\n";
        
        //Size of "index" can be retrieved only after user input
        int count = 0;
        int ansCount = 0;
        vector<size_t> index(number.size());
        find(number, target, index, 0, count, ansCount);
        
        //Displays matching expressions
        if (ansCount == 1) {cout << "\n" << ansCount << " expression equals target.\n";}
        else {cout << "\n" << ansCount << " expressions equal target.\n";}
        
        //Displays total possibilities
        if (count == 1) {cout << "Only 1 possibility.\n\n\n";}
        else {cout << count << " total possibilities.\n\n\n";}
        
        //Runs program again at user's request
        cout << "Would you like to run this program again? (y/n): ";
        cin >> again;
    } while (again == 'y' || again == 'Y');
    
    return 0;
}