#include <string.h>
#include <stdio.h>

#include <list>
using namespace std;

enum Operation
{
	OPERATION_PLUS,
	OPERATION_MINUS,
	OPERATION_MULTIPLY
};

// Do one operation which shrinks the list by one then recursively call on the updated list
// with a different starting index each time
void permuationTraversal(char *expression, unsigned operationIndex, list<int> values, list<Operation> operations, list<int> *results)
{
	unsigned index;
	int value1,value2;
	Operation op;
	list<Operation>::iterator opIter;
	list<int>::iterator valueIter;

	opIter = operations.begin();
	valueIter=values.begin();

	// operationIndex is which operation to pop out of the list, and also the associated value
	for (index=0; index < operationIndex; index++)
	{
		++opIter;
		++valueIter;
	}

	// Get the operation and two values here
	op = *opIter;
	value1=*valueIter;
	valueIter++;
	value2=*valueIter;

	if (op==OPERATION_PLUS)
		*valueIter=value1+value2;
	else if (op==OPERATION_MINUS)
		*valueIter=value1-value2;
	else// if (op==OPERATION_MULTIPLY)
		*valueIter=value1*value2;

	// Remove one element from each list
	operations.erase(opIter);

	// List empty?
	if (operations.size()==0)
	{
		// Done!  Push the result (*valueIter) if it doesn't already exist
		list<int>::iterator resultIter;
		resultIter=results->begin();

		while (resultIter != results->end())
		{
			if (*resultIter==*valueIter)
				return; // Answer already exists
			resultIter++;
		}

		// Answer does not already exist.  Insert it.
		results->push_back(*valueIter);
		return;
	}

	// Erase the previous value.  The value we just wrote replaces both these values
	valueIter--;
	values.erase(valueIter);

	for (index=0; index < operations.size(); index++)
		permuationTraversal(expression, index, values, operations, results);
}

void parenPermutations(char *expression)
{
	list<int> values;
	list<Operation> operations;
	list<int> results;
	int expressionIndex=0;
	int value;
	unsigned index;

	if (expression==0)
		return;

	// Convert the string into two stacks, one of operations and one of numbers
	while (expression[expressionIndex])
	{
		if (expression[expressionIndex]>='0' && expression[expressionIndex]<='9')
		{
			value = atoi(expression+expressionIndex);
			values.push_back(value);
			// put the pointer past the number
			do {
				++expressionIndex;
			} while (expression[expressionIndex] && expression[expressionIndex]>='0' && expression[expressionIndex]<='9');
			 // Point at the end of this number so the increment at the bottom of the loop will go past
			expressionIndex--;
		}
		else if (expression[expressionIndex]=='*')
		{
			operations.push_back(OPERATION_MULTIPLY);
		}
		else if (expression[expressionIndex]=='-')
		{
			operations.push_back(OPERATION_MINUS);
		}
		else if (expression[expressionIndex]=='+')
		{
			operations.push_back(OPERATION_PLUS);
		}

		expressionIndex++;
	}

	if (values.size()==0 || operations.size()+1!=values.size())
		return; // Bad expression

	if (operations.size()==0)
	{
		list<int>::iterator valueIter;
		valueIter=values.begin();
		// Only one value
		printf("%i\n", *valueIter);
	}
	else
	{
		list<int>::iterator resultIter;
		
		// First iteration
		for (index=0; index < operations.size(); index++)
			permuationTraversal(expression, index, values, operations, &results);

		resultIter=results.begin();
		printf("%i unique: ", results.size());
		while (resultIter != results.end())
		{
			printf("%i ", *resultIter);
			resultIter++;
		}
	}
}

void main(void)
{
	parenPermutations("1 + 2 + 3 * 4 - 5 * 2");
//	parenPermutations("1+2+3");
	int a=5;	
}