/*---------------------------------------------------------------------------
File name: ExprEvaluator.cpp
Author: HJin (email: fish_sea_bird [at] yahoo [dot] com )
Created on: 8/24/2007 07:02:12
Environment: Windows XP Professional SP2 English +
Visual Studio 2005 v8.0.50727.762

Modification history:
===========================================================================

Problem statement:
---------------------------------------------------------------------------

For a given string of numbers and a key, you need to put + and *
between the numbers so that the resulting expression evaluates to
the key. For example,

"1231231234", 11353 -> "12*3+1+23*123*4"

Here is the break-down of the above line:

The string is: 1231231234
The key is: 11353
A soltuion is: 12*3+1+23*123*4

Requirements:

1. You don't need to put any parentheses to change
the precedence of evaluation.
2. In case there is more than one solution, you
are only asked to output one of them;
3. In case there are no solutions, output
"no solution".
4. Your ouput should follow the format shown in the
examples section below;
5. The input string has length less than 11. The key is
between 1 and 2147483647, inclusive.

Examples:
---------------------------------------------------------------------------

"1231231234", 11353 -> "12*3+1+23*123*4"
"3456237490", 1185 -> "3*4*56+2+3*7+490"
"3456237490", 9191 -> "no solution"

Analysis:
---------------------------------------------------------------------------

I used a burte force approach which takes long time. I am hoping that
you can develop an efficient algorithm and/or appropriate data structure
to solve this problem.

I provide my source code for you to start with.

Sample output:
---------------------------------------------------------------------------
(Note that my ouput format does not obey the problem statement).

3*4*56+2+3*7+490
34*5*6+23*7+4+9*0
34*5+6*23*7+49+0
Press any key to continue . . .
*/

#include <iostream>
#include <string>
#include <vector>
#include <map>

#include <algorithm>
#include <functional>
#include <numeric>

#include "ExpressionEvaluator.h"

using namespace std;

class ExprEvaluator
{
public:
ExprEvaluator(const string& s) : in(s), mSize(s.size())
{
out.resize(2*mSize-1);
//out.reserve(2*mSize-1); /// don't know why this reserve causes crash
for(size_t i=0; i<mSize; ++i)
out[2*i] = in[i];
}

void Display()
{
for(map<string, int>::iterator iter = strIntMap.begin(); iter != strIntMap.end(); ++iter)
{
cout<<iter->first<<"\t\t"<<iter->second<<endl;
}

}

void BuildMap(int n)
{
if(n==1)
{
size_t index = 2*mSize - 3;
out[index] = ' ';
AddToMap(out);
out[index] = '*';
AddToMap(out);
out[index] = '+';
AddToMap(out);
}
else
{
size_t k=2*(mSize-n)+1;
out[k] = ' ';
BuildMap(n-1);
out[k] = '*';
BuildMap(n-1);
out[k] = '+';
BuildMap(n-1);
}
}

void FindSoln(int key, vector<string>& vs)
{
vector<string>().swap(vs);
vs.reserve(5);

for(map<string, int>::iterator it = strIntMap.begin(); it!=strIntMap.end(); ++it)
if(it->second == key)
vs.push_back(it->first);
}

private:
void RemoveSpace(string& s) // erase/remove trick
{
s.erase(remove_if(s.begin(), s.end(), bind2nd(equal_to<char>(), ' ')), s.end() );
}

void AddToMap(const string& s)
{
string temp(s);
RemoveSpace(temp);
long res;

ExpressionEvaluator::calculateLong(temp, res);
strIntMap.insert(make_pair(temp, res));
}

private:
string in;
size_t mSize;
string out;
std::map<string, int> strIntMap;
};

int main()
{
string s="3456237490";
int key = 1185;
size_t n = s.size();

ExprEvaluator ee(s);
ee.BuildMap(n);
vector<string> vs;
ee.FindSoln(key, vs);

for(size_t i=0; i<vs.size(); ++i)
cout<<vs[i]<<endl;

return 0;
}

[此贴子已经被作者于2007-8-24 22:29:49编辑过]