Finding target number with given numbers using arithmetic operations

Question

I coded a program in C++, it tries to get target value with given numbers using arithmetic operations. Most of the time, there are several solutions. Finding one of them is enough. For example, target number is:410 and given numbers are:2,3,5,20,44,50 My program should find a solution like the following:(2*5)*(44-3)

However, my program is adding parentheses to the left-most expression only. My program only finds solutions like the following: (((((2+3)+5)*44)+20)-50) Therefore, sometimes my program can't find solutions although there is a solution. How should I change my algorithm?

Here is my code:

#include 
#include 
using namespace std;

int TargetNumber = 302;
int Numbers[6];
bool isNumberUsed[6] = { 0,0,0,0,0,0 };

int calculate(int x, char operation, int y) {
    if (operation == '+')
        return (x + y);

    if (operation == '-')
        return (x - y);

    if (operation == '*')
        return (x * y);

    if (operation == '/' && y != 0 && x%y == 0)
        return (x / y);
}

bool isSolutionFound = 0, isOperationUsed = 0;
std::string answer = "";
int result;

void searchSolution(int TargetNumber, std::string term, int value)
{
    if (TargetNumber == value)
    {
        isSolutionFound = 1;
        answer = term;
        return;
    }

    for (int a = 0; a < 6; a++)
    {
        for (int b = 0; b < 4; b++)
        {
            isOperationUsed = 0;
            if (isNumberUsed[a] == 1)
            {
                isNumberUsed[a] = 0;
                if (b == 0)
                {
                    result = calculate(value, '+', Numbers[a]);
                    isOperationUsed = 1;
                }
                if (b == 1)
                {
                    result = calculate(value, '-', Numbers[a]);
                    isOperationUsed = 1;
                }
                if (b == 2)
                {
                    result = calculate(value, '*', Numbers[a]);
                    isOperationUsed = 1;
                }
                if (b == 3 && (value % Numbers[a] == 0) && Numbers[a] != 0)
                {
                    result = calculate(value, '/', Numbers[a]);
                    isOperationUsed = 1;
                }
                if (isOperationUsed == 1 && isSolutionFound == 0)
                {
                    if (b == 0)
                        searchSolution(TargetNumber, "(" + term + "+" + std::to_string(Numbers[a]) + ")", result);
                    if (b == 1)
                        searchSolution(TargetNumber, "(" + term + "-" + std::to_string(Numbers[a]) + ")", result);
                    if (b == 2)
                        searchSolution(TargetNumber, "(" + term + "*" + std::to_string(Numbers[a]) + ")", result);
                    if (b == 3)
                        searchSolution(TargetNumber, "(" + term + "/" + std::to_string(Numbers[a]) + ")", result);
                }
                isNumberUsed[a] = 1;
            }
        }
    }
}

int main()
{
    TargetNumber = 302;

    string inputstring = "2 3 7 10 25 50";

    int ConvertToInt = 0, ArrayIndex = 0;
    for (int a = 0; a < inputstring.length(); a++) // Taking values from string & changing to int
    {

        if (inputstring[a] != ' ')
        {
            if (ConvertToInt == 0)
            {
                ConvertToInt = inputstring[a] - '0';
            }
            else
            {
                ConvertToInt = ConvertToInt * 10 + inputstring[a] - '0';
            }
        }
        if (inputstring[a] == ' ')
        {
            Numbers[ArrayIndex] = ConvertToInt;
            ConvertToInt = 0;
            ArrayIndex++;
        }
    }
    Numbers[ArrayIndex] = ConvertToInt; // For the last number in the string

    for (int i = 0; i < 6; i++)
    {
        isNumberUsed[i] = 0;
        searchSolution(TargetNumber, std::to_string(Numbers[i]), Numbers[i]);
        isNumberUsed[i] = 1;
    }
    if (answer == "")
        answer = "No Solution";

    cout <<  answer<<"
";
}

user_6221024 · Answer

The easiest way that you can handle this problem is to avoid infix notation, where you need explicit parenthesization, and instead use either prefix or postfix notation. Consider, for example, the expression 2 * (3 + 4). We could rewrite this to 2 3 4 + * in postfix notation, with no parentheses.

To iterate through every possible expression, you just need to permute your numbers, and then scatter in operators. However, there are two rules you must observe:

at any point (reading left to right) you must have passed fewer operators than values
the entire expression must have exactly one more value than operator

Of course, you can adjust these rules for prefix notation.

Simplest way to implement will likely be a recursive function that attempts to draw a value (without replacement) and push it to the stack, and also attempts (separately) to pop the top two values from the stack, draw a random operation (with replacement), apply that operator to the popped values and push to the top of the stack. The function recurses until the pool of values is empty and the stack has only a single value on it.

Note that you'll of course have a lot of redundancy- we completely ignore any associative / commutative properties of these operations, and you could probably cache a set of intermediate values produced from subsets of the values, but that's a whole different topic.

Finding target number with given numbers using arithmetic operations

1 Answers