CareerCup

Ok. Now you are just posting random shit.

Obiwana, hi friend.

I decided for convenience to collect all possible expressions with the post-fix notations.
This has solved out the problem of parenthesis and the problem to execute the expressions.
An expression is represented here as a queue of operations.

Funny puzzle ;-)

enum OperationType { OP_VAL, OP_SUM, OP_SUB, OP_ISUB, OP_MULT, OP_DIV, OP_IDIV };
typedef pair< OperationType, int > Operation;
typedef deque< Operation > Expression;

void find_expressions( vector< int >& input, int target )
{
	vector< Expression > collection;

	for (int i = 0; i < input.size( ); ++i )
	{
		Expression exp( 1, Operation( OP_VAL, input[i] ) );
		collect_expressions( collection, input, i, exp, target );
	}

	for( const auto& exp: collection )
	{
		print_expression( exp );
	}
}

void collect_expressions( vector< Expression >& collection,
                          const vector< int >& input,
                          int begin,
                          Expression& exp,
                          int target )
{
	int val = 0;
	if ( execute_expression( exp, val ) && val == target )
	{
		collection.push_back( exp );
	}

	for ( int i = begin + 1; i < input.size( ); ++i )
	{
		int val = input[i];

		exp.push_back( Operation( OP_SUM, val ) );
		collect_expressions( collection, input, i, exp );

		Operation& op = exp.back( );
		op.second = 1;

		op.first = OP_SUM;
		collect_expressions( collection, input, i, exp );

		op.first = OP_SUB;
		collect_expressions( collection, input, i, exp );

		op.first = OP_ISUB;
		collect_expressions( collection, input, i, exp );

		op.first = OP_MULT;
		collect_expressions( collection, input, i, exp );
	
		op.first = OP_DIV;
		collect_expressions( collection, input, i, exp );

		op.first = OP_IDIV;
		collect_expressions( collection, input, i, exp );

		exp.pop_back( );
	}

}

bool execute_expression( const Expression& exp, int& result )
{
	deque<int> stack;

	if ( exp.size( ) == 1)
	{
		val = exp[0].second;
		return exp[0].first == OP_VAL;
	}

	for (Operation op: exp)
	{
		if ( op.first == OP_VAL )
		{
			stack.push_back( op.second );
			continue;
		}

		if ( stack.size( ) < 2 )
		{
			return false;
		}

		int op1 = stack.back( ); stack.pop_back( );
		int op2 = stack.back( ); stack.pop_back( );
		int tmp_val = 0;

		switch( op.first )
		{
		case OP_SUM:
			tmp_val = op1 + op2;
			break;

		case OP_SUB:
			tmp_val = op1 - op2;
			break;

		case OP_ISUB:
			tmp_val = op2 - op1;
			break;

		case OP_MUL:
			tmp_val = op1 * op2;
			break;

		case OP_DIV:
			if ( op2 == 0 ) return false;
			tmp_val = op1 / op2;
			break;

		case OP_IDIV:
			if ( op1 == 0 ) return false;
			tmp_val = op2 / op1;
			break;

		}

		stack.push_back( tmp_val );
	}

	result = stack.front( );
	return stack.size( ) == 1;
}

void print_expression( const Expression& exp )
	{
	deque< string > stack;

	for( Operation op: exp )
	{
		if ( op.first == OP_VAL )
		{
			stringstream buf;
			buf << op.second;
			stack.push_back( buf.str( ) );
			continue;
		}

		string op1 = stack.back( ); stack.pop_back( );
		string op2 = stack.back( ); stack.pop_back( );
		if ( op.first == OP_ISUB || op.first == OP_IDIV )
		{
			op1.swap(op2);
		}

		stringstream buf;
		buf << “( “ << op1 << “ )“;

		switch( op.first )
		{
		case OP_SUM:
			buf << “ + ”;
			break;

		case OP_SUB:
		case OP_ISUB:
			buf << “ - ”;
			break;

		case OP_MUL:
			buf << “ * ”;
			break;

		case OP_DIV:
		case OP_IDIV:
			buf << “ / ”;
			break;

		}

		buf << “( “ << op2 << “ )“;
		stack.push_back( buf.str( ) );
	}

	cout << stack.front( ) << endl;
}

Recursively iterate all possible () and +-*/ group.

You could probably do something with recursive backtracking (iterate through all valid expressions given the (I assume) fixed set of symbols), but this sounds a bit too tough for a 45min interview question.

I coded a solution to a similar problem a while back. This one only finds one expression, but can be easily modified to return all expressions.

bool find_exp_aux(std::vector<int> & v, std::vector<std::string>& e, const int t, std::string& r)
{
    if (v.empty()) return false;
    auto n = v.size();
    if (1 == n)
    {
        if (t == v[0])
        {
            r = e[0];
            return true;
        }
        return false;
    }
    for (auto i = 0; i < n; ++i)
    {
        auto v1 = v[i];
        const auto& e1 = e[i];
        for (auto j = i + 1; j < n; ++j)
        {
            auto v2 = v[j];
            const auto& e2 = e[j];
            auto vc(v);
            auto ec(e);
            vc.erase(vc.begin() + j);
            vc.erase(vc.begin() + i);
            ec.erase(ec.begin() + j);
            ec.erase(ec.begin() + i);
            auto vnew = 0;
            std::string enew = "";
            vnew = v1 + v2;
            enew = "(" + e1 + ")" + "+" + "(" + e2 + ")";
            vc.push_back(vnew);
            ec.push_back(enew);
            if (find_exp_aux(vc, ec, t, r)) return true;
            ec.pop_back();
            vc.pop_back();
            vnew = v1 * v2;
            enew = "(" + e1 + ")" + "*" + "(" + e2 + ")";
            vc.push_back(vnew);
            ec.push_back(enew);
            if (find_exp_aux(vc, ec, t, r)) return true;
            ec.pop_back();
            vc.pop_back();
            vnew = v1 - v2;
            enew = "(" + e1 + ")" + "-" + "(" + e2 + ")";
            vc.push_back(vnew);
            ec.push_back(enew);
            if (find_exp_aux(vc, ec, t, r)) return true;
            ec.pop_back();
            vc.pop_back();
            vnew = v2 - v1;
            enew = "(" + e2 + ")" + "-" + "(" + e1 + ")";
            vc.push_back(vnew);
            ec.push_back(enew);
            if (find_exp_aux(vc, ec, t, r)) return true;
            ec.pop_back();
            vc.pop_back();
            if (0 != v2)
            {
                vnew = v1 / v2;
                enew = "(" + e1 + ")" + "/" + "(" + e2 + ")";
                vc.push_back(vnew);
                ec.push_back(enew);
                if (find_exp_aux(vc, ec, t, r)) return true;
                ec.pop_back();
                vc.pop_back();
            }
            if (0 != v1)
            {
                vnew = v2 / v1;
                enew = "(" + e2 + ")" + "/" + "(" + e1 + ")";
                vc.push_back(vnew);
                ec.push_back(enew);
                if (find_exp_aux(vc, ec, t, r)) return true;
                ec.pop_back();
                vc.pop_back();
            }
        }
    }
    return false;
}

bool find_exp(const std::vector<int>& v, const int t, std::string& r)
{
    std::vector<int> vc(v);
    std::vector<std::string> ec;
    for (auto i : vc)
    {
        ec.push_back(std::to_string(i));
    }
    return find_exp_aux(vc, ec, t, r);
}