Alessio Sclocco

Hello everyone.

While working on some other things, like my MSc thesis, I saw a simple problem on a form to apply for a job, and I wanted to solve it. The problem is quite simple, but I enjoyed it and wanted to share my solution with the whole Internet; moreover the main reason I thought about modifying my ArgumentList class derives from this problem :)

The problem

Given a sequence of digits in some order, print all the expressions obtainable inserting a + (plus), – (minus), * (multiplication) or nothing, that evaluate to a given number. The solution should be written in C++ using the std library.

My solution

The solution is straightforward and is composed by two steps: generating all the possible expressions and then evaluate them.
To generate all the possible expressions what I did is the following. I used a pair to represent an expression: the pair is formed by an integer, representing the element after which the operators can be inserted, and a string, representing the expression to operate on. The first pair is just (0, sequence), where sequence is the one provided as input.
Now it is possible to use a queue to iteratively get a pair, evaluate the expression in it, and then generate the new expressions  and put them into the queue to get successively evaluated.
The code is the following:

while ( !queue.empty() ) {
		pair< unsigned int, string > *toEvaluate = queue.back();

		if ( evaluate(target, toEvaluate->second) ) {
			found.insert(toEvaluate->second);
		}

		if ( toEvaluate->first < (toEvaluate->second).length() - 1 ) {
			queue.push_front(new pair< unsigned int, string >(toEvaluate->first + 1, toEvaluate->second));
			for ( unsigned int i(0); i < NR_OPERATORS; i++ ) {
				queue.push_front(new pair< unsigned int, string>(toEvaluate->first + 2, (toEvaluate->second).substr(0, toEvaluate->first + 1) + operators[i] + (toEvaluate->second).substr(toEvaluate->first + 1)));
			}
		}

		queue.pop_back();
	}

The evaluation is quite simple too. When an expression has to be evaluated is first parsed and divided into two components: the operands and the operators. After that each operator is applied to its operands (starting with the multiplication in our case) and a total is computed. If it matches with the goal number the boolean value true is returned.

The code is the following:

bool evaluate(int target, string &item) {

	vector< int > operands;
	vector< char > operators;
	unsigned int i(0);

	while ( i < item.length() ) {
		unsigned int counter(i);
		while ( counter < item.length() && isdigit(item.at(counter)) ) {
			counter++;
		}
		operands.push_back(atoi((item.substr(i, counter - i)).c_str()));
		if ( counter < item.length() ) {
			operators.push_back(item.at(counter));
		}
		i = counter + 1;
	}

	// Performs the multiplies first
	for ( unsigned int op(0); op < operators.size(); op++ ) {
		if ( operators[op] == '*' ) {
			operands[op] *= operands[op + 1];
			operands[op + 1] = 1;
		}
	}

	int total(operands[0]);
	unsigned int opCounter(0);
	for ( unsigned int i(1); i < operands.size(); i++ ) {
		switch( operators[opCounter++] ) {
			case '+':
				total += operands[i];
				break;
			case '-':
				total -= operands[i];
				break;
			case '*':
				total *= operands[i];
				break;
		}
	}

	if ( total == target ) {
		return true;
	}

	return false;
}

Notes

The original problem was less general and asked just to print all the expressions evaluating the number 3141 given the sequence 987654321, I generalized it for the sake of fun.
The complete code, with a Makefile, is available here. It needs to have my ArgumentList installed to work.

Post scriptum

The answer of the original question are the expressions “9*8*7*6+54+3*21” and “987-6+5*432*1” :)

Hello everyone, this is just a minor update of the ArgumentList class.

Two are the differences between this one and the previous version:

1. CMake will now produce also the “install” directive for Make
2. The getSwitchArgument() method, instead of returning a zero in case of failure, will throw a std::exception

So it will be safe, from now on, to call the getSwitchArgument method inside a try/catch block, like in the following example:

int i(0);
float f(0.0);
try {
    i = args.getSwitchArgument< int >("-i");
    f = args.getSwitchArgument< float >("-f");
}
catch (std::exception) {
    std::cerr << "Ops :)" << std::endl;
}

The new version or ArgumentList can be downloaded from this link.

In version 0.1 of my ArgumentList there was an annoying problem, that is if we want to extract a parameter from command line that wasn’t a string, we had to write a converter by ourselves.
To solve this issue I modified  the getSwitchArgument() method in order to accept a type as a template parameter. I hope this modification can simplify the use of the class.

So now, if we suppose to have something like that in our command line:

some-executable -i 10 -f 0.004

what we have to write in our code, in order to get the numerical values “10″ and “0.004″ is the following:

int i(0);
float f(0.0);
i = args.getSwitchArgument< int >("-i");
f = args.getSwitchArgument< float >("-f");

So right now, to have a string argument like before, it is necessary to pass the string parameter to the template, like in the following example:

string tempString;
tempString = args.getSwitchArgument< std::string >("-s");

An example is presented in the test directory included with the package. CMake is needed to build the package.

ArgumentList 0.2 can be downloaded here.