M**8
发帖数: 25 | 1 Hi,
I was being asked the question below long time ago. Still I cannot figure
out the problem today. For expression 1 + 2 + 3 * 4 - 5 * 2, the maximum
combination I can get is 16. let alone 18 unique results.
Any expert ideas?
The string ‘expression’ contains the operators ’+’, ’-’, ’*’ and
positive integers (or possibly no operators and just one integer). The
expression is entirely unparenthesized. Your function should determine the
result of every possible parenthesization of the expression | t****e
发帖数: 69 | 2 My solution, some recursive function, implemented in C++:
using namespace std;
void GetUniqueValues( const string & expression, vector & uniqueValues )
{
if(expression.empty()) return;
if(expression.length()==1)
{
uniqueValues.push_back( atoi(expression[0]) );
return;
}
map uniqueMap;
for(int i = 1; i < expression.length(); i+=2)
{
vector leftValues;
vector rightValues;
GetUniqueValues( expression.substr(0, i), leftValues );
GetUnique
【在 M**8 的大作中提到】
: Hi,
: I was being asked the question below long time ago. Still I cannot figure
: out the problem today. For expression 1 + 2 + 3 * 4 - 5 * 2, the maximum
: combination I can get is 16. let alone 18 unique results.
: Any expert ideas?
: The string ‘expression’ contains the operators ’+’, ’-’, ’*’ and
: positive integers (or possibly no operators and just one integer). The
: expression is entirely unparenthesized. Your function should determine the
: result of every possible parenthesization of the expression
| t****e
发帖数: 69 | 3 Well, this assumes the numbers are all single digit, and no space in the exp
ression. To be better some interpretation of the expression needs to be done
to get the numbers and operators. But you get the idea.
uniqueValues )
【在 t****e 的大作中提到】
: My solution, some recursive function, implemented in C++:
: using namespace std;
: void GetUniqueValues( const string & expression, vector & uniqueValues )
: {
: if(expression.empty()) return;
: if(expression.length()==1)
: {
: uniqueValues.push_back( atoi(expression[0]) );
: return;
: }
| t****e
发帖数: 69 | 4 刚用cygwin试了，确实是18个。
原程序有个错误：atoi()的参数是const char *，不是char。
暂且换成 expression[0] - '0' 吧。
exp
done
【在 t****e 的大作中提到】
: Well, this assumes the numbers are all single digit, and no space in the exp
: ression. To be better some interpretation of the expression needs to be done
: to get the numbers and operators. But you get the idea.
:
: uniqueValues )
| M**8
发帖数: 25 | 5 HI tutule,
Your solution is correct. I was thinking, first bracket left, then bracket
right for every expression, like
(1+2+3*4-5)*2
1+(2+3*4-5*2)
But I did not realized middle cases like
(1+2+3)*(4-5*2)
Thanks for your time, |
|
