123456789 = 100加入+ - * /个数不限使上面得表达式成立，编程实现求出所有答案(100分)

101中都在这里，请查收
1+2+3+4+5+6+7+8*9
1+2+3-4+5+6+78+9
1+2+3-4*5+6*7+8*9
1+2+3-45+67+8*9
1+2+3*4-5-6+7+89
1+2+3*4*5/6+78+9
1+2+3*4*56/7-8+9
1+2+34-5+67-8+9
1+2+34*5+6-7-8*9
1+2-3*4+5*6+7+8*9
1+2-3*4-5+6*7+8*9
1+2*3+4+5+67+8+9
1+2*3+4*5-6+7+8*9
1+2*3-4+56/7+89
1+2*3-4-5+6+7+89
1+2*3*4*5/6+7+8*9
1+2*34-56+78+9
1+23-4+5+6+78-9
1+23-4+56+7+8+9
1+23-4+56/7+8*9
1+23-4-5+6+7+8*9
1+23*4+5-6+7-8+9
1+23*4+56/7+8-9
1+23*4-5+6+7+8-9
1+234-56-7-8*9
1+234*5*6/78+9
1+234*5/6-7-89
1-2+3+45+6+7*8-9
1-2+3*4+5+67+8+9
1-2+3*4*5+6*7+8-9
1-2+3*4*5-6+7*8-9
1-2-3+4*5+67+8+9
1-2-3+4*56/7+8*9
1-2-3+45+6*7+8+9
1-2-3+45-6+7*8+9
1-2-3+45-6-7+8*9
1-2-34+56+7+8*9
1-2*3+4*5+6+7+8*9
1-2*3-4+5*6+7+8*9
1-2*3-4-5+6*7+8*9
1-23+4*5+6+7+89
1-23-4+5*6+7+89
1-23-4-5+6*7+89
1*2+3+4*5+6+78-9
1*2+3+45+67-8-9
1*2+3-4+5*6+78-9
1*2+3*4+5-6+78+9
1*2+34+5+6*7+8+9
1*2+34+5-6+7*8+9
1*2+34+5-6-7+8*9
1*2+34+56+7-8+9
1*2+34-56/7+8*9
1*2-3+4+56/7+89
1*2-3+4-5+6+7+89
1*2-3+4*5-6+78+9
1*2*3+4+5+6+7+8*9
1*2*3-4+5+6+78+9
1*2*3-4*5+6*7+8*9
1*2*3-45+67+8*9
1*2*3*4+5+6+7*8+9
1*2*3*4+5+6-7+8*9
1*2*3*4-5-6+78+9
1*2*34+56-7-8-9
1*2/3+4*5/6+7+89
1*23+4+5+67-8+9
1*23+4+56/7*8+9
1*23-4+5-6-7+89
1*23-4-56/7+89
1*23*4-56/7/8+9
1*234+5-67-8*9
1/2*3/4*56+7+8*9
1/2*34-5+6-7+89
1/2/3*456+7+8+9
12+3+4+5-6-7+89
12+3+4-56/7+89
12+3-4+5+67+8+9
12+3*4+5+6+7*8+9
12+3*4+5+6-7+8*9
12+3*4-5-6+78+9
12+3*45+6*7-89
12+34+5*6+7+8+9
12+34-5+6*7+8+9
12+34-5-6+7*8+9
12+34-5-6-7+8*9
12-3+4*5+6+7*8+9
12-3+4*5+6-7+8*9
12-3-4+5-6+7+89
12-3-4+5*6+7*8+9
12-3-4+5*6-7+8*9
12*3-4+5-6+78-9
12*3-4-5-6+7+8*9
12*3-4*5+67+8+9
12/3+4*5-6-7+89
12/3+4*5*6-7-8-9
12/3+4*5*6*7/8-9
12/3/4+5*6+78-9
123+4-5+67-89
123+4*5-6*7+8-9
123+45-67+8-9
123-4-5-6-7+8-9
123-45-67+89

下面给出穷尽表达式的算法。
var ExpressList: TStringList;
procedure TForm1.Button1Click(Sender: TObject);
var s1,s2,Text: string;
i: integer;
begin
Text := '123456789';
ExpressList := TStringList.Create;
Screen.Cursor := crHourGlass;
for i := 1 to 9do
begin
s1 := Copy(Text,1,i);
s2 := Copy(Text,i+1,Length(text)-i);
cal(s1,s2);
end;
Memo1.Lines.Assign(ExpressList);
Screen.Cursor := crDefault;
end;

const operator: string = '+-*/';
procedure cal(s1,s2: string);
var s11,s22: string;
d:do
uble;
i,j:integer;
begin
d := 0;
if s2 = '' then
begin
EvaluateExpression(s1,d);
if d = 100 then
ExpressList.Add(s1);
exit;
end;
for i := 1 to 4do
begin
for j := 1 to Length(s2)do
begin
s11 := s1 + operator + Copy(s2,1,j);
s22 := Copy(s2,j+1,Length(s2)-j);
cal(s11,s22);
end;
end;
end;

有了穷尽表达式的算法，下一步就是挑选符合条件的表达式
EvaluateExpression(s1,d);
这个函数我就不贴了，数据结构中有的是，顺便说一句，我这个EvaluateExpression函数可以处理括号（）的，只要穷尽表达式的算法中加入（）就可以。
这个算法用了19秒，耗时不少(AMD 1800+ 512M)

这个比凑24的游戏简单多了，我编凑24的游戏用了半天多才完全搞定（还要提高速度，为了程序员杂志上的编程擂台2002。10，不过可惜的是虽然我的算法速度和正确性等都优于当期的优胜者，但是投稿完了，主持人把我漏掉了，我向主持人要了那两个人的程序，都是VC++做的（绝大部分都用VC做），可是速度比我的Delphi差多了，哈哈），
这个也就用了不到一个小时，不过EvaluateExpression的函数是我以前编过的，不计算时间在内。（凑24的游戏不用EvaluateExpression函数）

睡觉了。
对了，如果把
procedure cal(s1,s2: string);
简单的定义为
procedure cal(const s1,s2: string);
可以节约25%的效率，可以提高到不到15秒（在我的机器上）

哦,原来不能整除的不算在内啊?
要考虑实数运算的,我只考虑了整数运算

呵呵,我也得到101种结果了,
算法耗时 2.2s 机器配置 PII392MHz RAM256M
下面是我的全部源代码,我使用了分数来进行运算,
同时处理分母和分子,但不支持括号,
解析表达式的算法花了不少时间来编写,而且还几番修改,
老弄错了题意,还是SS2000 兄比较厉害
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls;
type
TFenNum = record
X: Integer;
Y: Integer;
end;

TForm1 = class(TForm)
Button1: TButton;
Edit1: TEdit;
Memo1: TMemo;
Button3: TButton;
procedure Button1Click(Sender: TObject);
procedure FormCreate(Sender: TObject);
procedure Button3Click(Sender: TObject);
private
{ Private declarations }
public
end;

var
Form1: TForm1;
oPrioritys: array[1..5, 1..5] of Integer = (
// +, -, *, /, _,
{+} (0, 0,-1,-1,-1),
{-} (0, 0,-1,-1,-1),
{*} (1, 1, 0, 0,-1),
{/} (1, 1, 0, 0,-1),
{_} (1, 1, 1, 1, 0)
);
function IdOfOp(C: Char): Integer;
function ValueOf(C: Char): TFenNum;
function PrioOfOp(C1, C2: Integer): Integer;
function Calc(N1, N2: TFenNum;
C: Integer;
var Fail: Boolean): TFenNum;
function TrimExpr(var S: String): Boolean;
function ParExpr(const Tkens: String;
var Fail: Boolean): TFenNum;

implementation
{$R *.dfm}
function TrimExpr(var S: String): Boolean;
var
m: String;
i: Integer;
ct: Integer;
begin
Result := False;
m := S;
ct := 0;
for i := 1 to Length(m)do
begin
if m <> '_' then
begin
ct := ct + 1;
if Result then
begin
S[ct] := m;
end;
end
else
begin
Result := True;
end;
end;
if Length(m) <> ct then
SetLength(S, ct);
end;

function IdOfOp(C: Char): Integer;
begin
case C of
'+': Result := 1;
'-': Result := 2;
'*': Result := 3;
'/': Result := 4;
'_': Result := 5;
else
Result := 0;
end;
end;

function ValueOf(C: Char): TFenNum;
begin
if C in ['0'..'9'] then
begin
Result.X := Ord(C) - Ord('0');
Result.Y := 1;
end
else
begin
Result.X := -1;
Result.Y := -1;
end;
end;

function PrioOfOp(C1, C2: Integer): Integer;
begin
if (C1 > 0) and (C2 > 0) then
Result := oPrioritys[C1, C2]
else
Result := 0;
end;

function Calc(N1, N2: TFenNum;
C: Integer;
var Fail: Boolean): TFenNum;
var
m1, m2: TFenNum;
n: Integer;
begin
m1 := N1;
m2 := N2;
n := C;
Result.X := 0;
Result.Y := 1;
case n of
1:
begin
Result.X := m1.X * m2.Y + m2.X * m1.Y;
Result.Y := m1.Y * m2.Y;
end;
2:
begin
Result.X := m1.X * m2.Y - m2.X * m1.Y;
Result.Y := m1.Y * m2.Y;
end;
3:
begin
Result.X := m1.X * m2.X;
Result.Y := m1.Y * m2.Y;
end;
4:
begin
if (m2.X = 0) then
Fail := True
else
begin
Result.X := m1.X * m2.Y;
Result.Y := m1.Y * m2.X;
end;
end;
5:
begin
m1.X := m1.X * 10;
Result.X := m1.X * m2.Y + m2.X * m1.Y;
Result.Y := m1.Y * m2.Y;
end;
else
raise Exception.Create('invalidoperator');
end;
if Result.X mod Result.Y = 0 then
begin
//进行简单归约
Result.X := Result.X div Result.Y;
Result.Y := 1;
end;
end;

function ParExpr(const Tkens: String;
var Fail: Boolean): TFenNum;
var
i: Integer;
stk: array[0..20] of TFenNum;
//数据栈
opstk: array[0..20] of Integer;
//运算符栈
sp1, sp2: Integer;
op, lastop: Integer;
t, n1, n2: TFenNum;
begin
//解析表达式,假设每个符号或数字都是一个字符
sp1 := 0;
sp2 := 0;
n1.X := 0;
n1.Y := 1;
n2.X := 0;
n2.Y := 1;
for i := 1 to Length(Tkens)do
begin
t := ValueOf(Tkens);
if t.X >= 0 then
begin
//数字入栈
stk[sp1] := t;
sp1 := sp1 + 1;
end
else
//如果不是数字,则认为是运算符
begin
lastop := IdOfOp(Tkens);
if sp2 > 0 then
begin
//取符号栈顶元素
op := opstk[sp2 - 1];
//循环,直到所有前面的运算都完成
if PrioOfOp(op, lastop) >= 0 then
begin
//将前面运算优先级高的运算全部完成
while (sp2 > 0) and (PrioOfOp(op, lastop) >= 0)do
begin
sp2 := sp2 - 1;
if sp1 > 0 then
begin
//从栈中弹出操作数2
sp1 := sp1 - 1;
n2 := stk[sp1];
end;
if sp1 > 0 then
begin
//从栈中弹出操作数1
sp1 := sp1 - 1;
n1 := stk[sp1];
end;
//进行计算
t := Calc(n1, n2, op, Fail);
//计算结果入栈
stk[sp1] := t;
sp1 := sp1 + 1;
//再取符号栈顶元素,直到前面优先级高的运算全部完成
op := opstk[sp2 - 1];
end;
//运算符入栈
opstk[sp2] := lastop;
sp2 := sp2 + 1;
end
else
begin
//符号入栈
opstk[sp2] := lastop;
sp2 := sp2 + 1;
end;
end
else
//符号入栈
begin
opstk[sp2] := lastop;
sp2 := sp2 + 1;
end;
end;
end;
//处理栈中剩余的所有数值和运算符
while sp1 > 1do
begin
sp1 := sp1 - 1;
n2 := stk[sp1];
sp1 := sp1 - 1;
n1 := stk[sp1];
if sp2 > 0 then
begin
sp2 := sp2 - 1;
op := opstk[sp2];
stk[sp1] := Calc(n1, n2, op, Fail);
sp1 := sp1 + 1;
end;
end;
Result := stk[0];
end;

procedure TForm1.Button1Click(Sender: TObject);
const
ops: String = '+-*/_';
var
m: array[1..20] of Integer;
st: Integer;
t, v: String;
tc, pc: Integer;
n: TFenNum;
t1, t2: Integer;
Fail: Boolean;
ts: TStringList;
begin
//ShowMessage(IntToStr(ParExpr(Edit1.Text)));
//for test
t := '1,2,3,4,5,6,7,8,9';
Memo1.Lines.Clear;
ts := TStringList.Create;
t1 := GetTickCount;
for st := 1 to 20do
m[st] := 1;
st := 1;
tc := 0;
pc := 0;
while m[st] <= 5do
begin
t[st * 2] := ops[m[st]];
st := st + 1;
if st > 8 then
begin
tc := tc + 1;
Fail := False;
n := ParExpr(t, Fail);
if not Fail and (n.X = 100) and (n.Y = 1) then
begin
v := t;
TrimExpr(v);
ts.Add(v);
pc := pc + 1;
end;
st := st - 1;
m[st] := m[st] + 1;
while (st > 1)and (m[st] > 5)do
begin
m[st] := 1;
st := st - 1;
m[st] := m[st] + 1;
end;
end;
Application.ProcessMessages;
if Application.Terminated then
Break;
end;
t2 := GetTickCount;
Memo1.Lines := ts;
ts.Free;
Caption := Format('%d/%d, Time: %d', [pc, tc, t2-t1]);
end;

procedure TForm1.FormCreate(Sender: TObject);
begin
Memo1.Clear;
end;

procedure TForm1.Button3Click(Sender: TObject);
var
m: TFenNum;
n: Boolean;
begin
n := False;
m := ParExpr(Edit1.Text, n);
if n then
Caption := 'fail'
else
Caption := IntToStr(m.X) + '/' + IntToStr(m.Y);
end;

end.

我用了一个栈和一个单重循环来枚举所有可能的组合
算法的效率关键在 表达式的解析上

结果在这里:
101/390625, Time: 2163
1+2+3+4+5+6+7+8*9
1+2+3-4+5+6+78+9
1+2+3-4*5+6*7+8*9
1+2+3-45+67+8*9
1+2+3*4-5-6+7+89
1+2+3*4*5/6+78+9
1+2+3*4*56/7-8+9
1+2+34-5+67-8+9
1+2+34*5+6-7-8*9
1+2-3*4+5*6+7+8*9
1+2-3*4-5+6*7+8*9
1+2*3+4+5+67+8+9
1+2*3+4*5-6+7+8*9
1+2*3-4+56/7+89
1+2*3-4-5+6+7+89
1+2*3*4*5/6+7+8*9
1+2*34-56+78+9
1+23-4+5+6+78-9
1+23-4+56+7+8+9
1+23-4+56/7+8*9
1+23-4-5+6+7+8*9
1+23*4+5-6+7-8+9
1+23*4+56/7+8-9
1+23*4-5+6+7+8-9
1+234-56-7-8*9
1+234*5*6/78+9
1+234*5/6-7-89
1-2+3+45+6+7*8-9
1-2+3*4+5+67+8+9
1-2+3*4*5+6*7+8-9
1-2+3*4*5-6+7*8-9
1-2-3+4*5+67+8+9
1-2-3+4*56/7+8*9
1-2-3+45+6*7+8+9
1-2-3+45-6+7*8+9
1-2-3+45-6-7+8*9
1-2-34+56+7+8*9
1-2*3+4*5+6+7+8*9
1-2*3-4+5*6+7+8*9
1-2*3-4-5+6*7+8*9
1-23+4*5+6+7+89
1-23-4+5*6+7+89
1-23-4-5+6*7+89
1*2+3+4*5+6+78-9
1*2+3+45+67-8-9
1*2+3-4+5*6+78-9
1*2+3*4+5-6+78+9
1*2+34+5+6*7+8+9
1*2+34+5-6+7*8+9
1*2+34+5-6-7+8*9
1*2+34+56+7-8+9
1*2+34-56/7+8*9
1*2-3+4+56/7+89
1*2-3+4-5+6+7+89
1*2-3+4*5-6+78+9
1*2*3+4+5+6+7+8*9
1*2*3-4+5+6+78+9
1*2*3-4*5+6*7+8*9
1*2*3-45+67+8*9
1*2*3*4+5+6+7*8+9
1*2*3*4+5+6-7+8*9
1*2*3*4-5-6+78+9
1*2*34+56-7-8-9
1*2/3+4*5/6+7+89
1*23+4+5+67-8+9
1*23+4+56/7*8+9
1*23-4+5-6-7+89
1*23-4-56/7+89
1*23*4-56/7/8+9
1*234+5-67-8*9
1/2*3/4*56+7+8*9
1/2*34-5+6-7+89
1/2/3*456+7+8+9
12+3+4+5-6-7+89
12+3+4-56/7+89
12+3-4+5+67+8+9
12+3*4+5+6+7*8+9
12+3*4+5+6-7+8*9
12+3*4-5-6+78+9
12+3*45+6*7-89
12+34+5*6+7+8+9
12+34-5+6*7+8+9
12+34-5-6+7*8+9
12+34-5-6-7+8*9
12-3+4*5+6+7*8+9
12-3+4*5+6-7+8*9
12-3-4+5-6+7+89
12-3-4+5*6+7*8+9
12-3-4+5*6-7+8*9
12*3-4+5-6+78-9
12*3-4-5-6+7+8*9
12*3-4*5+67+8+9
12/3+4*5-6-7+89
12/3+4*5*6-7-8-9
12/3+4*5*6*7/8-9
12/3/4+5*6+78-9
123+4-5+67-89
123+4*5-6*7+8-9
123+45-67+8-9
123-4-5-6-7+8-9
123-45-67+89

>>算法的效率关键在 表达式的解析上
其实表达式的解析到处都是，不会有多大的差别，数据结构中是必学的嘛。
关键是表达式的解析的实现，lich，你的算法确实快，比我的快了7，8倍，佩服！
但是是因为表达式的解析方法造成的吗？
非也，我仔细看了一下，解析方法我们大同小异，原理一样，之所以有如此巨大的差异，主要是因为以下原因造成。
1：我用的是TStack类，操作的速度比数组慢很多，每次我还要Create，最后Free。
2：由于我用的是TStack类，所以每个元素都要首先new，再添加，最后dispose,这是最消耗时间的，分配内存，释放内存，和你的数组操作需要的时间简直就是差几十倍。
以上两个原因是造成你的算法整体比我的快了7，8倍的主要原因。

lich，你的枚举所有可能的组合的算法很有意思，和我的完全不一样，我用的是递归。你的那段代码原理我是看懂了，不是细节还是没有完全搞清楚，有点绕，呵呵。思路非常好。

to SS2000,
你说的很对，同样的算法，实现的方法不同，
细节的差别会导致效率的差别，
我看速度好像不只快了7，8倍吧，
你的CPU速度是我的4倍还多啊，内存也是我的两倍
在你的机子上运行一下我的程序，看需要多长时间？

枚举的算法，我用的也是递归，只不过把递归化成了循环了
具体思路在最前面的帖子上有说明，进行估计总的运算量

没错，不只7，8倍，你的枚举的算法的效率是我的十倍，递归有函数调用，开销很大，而且我用的是Copy，你用了'_'，这个思路很巧妙。
我仔细测了一下你的算法在我的机器上用540毫秒，真不错。（和内存没有关系，这个程序不占内存），我的要13406毫秒，除去枚举算法，你的效率是我的26倍，应该是这样，昨天我还想，这分配内存等操作耗时应该是你的几十倍到几百倍甚至上千倍，怎么最后总效率才差7，8倍，呵呵。当然，这个算法中还有其他代码，我们的时间就差不多了，也就是你的算法没能总的比我快100的原因了。

SS2000今天的心情如何?
我也去弄一弄,看能不能弄一个比你们更棒D.

good

还有更好的算法吗？

佩服中……

呵呵 算法的思路较为相似，但是在实现时采用了不同的策略，效率就有了非常大的改
观。
lich兄的算法效率已经非常高了，再提高的话只是对“艺术性”的追求了——不过，似乎
Delphi程序员大多都是唯美主义者，那还是再探讨一下可能提高算法效率的思路吧
考虑到本问题中采用的只是简单的四则运算，并且没有括号，我们可以考虑采用简单的“
边穷举边计算”的方法——即在每次插入运算符的时候，都对插入点之前的表达式进行计算
（结果最多有三个部分：Val1 Op Val2）。如果插入的符号是+-，那么之前的值就可以直接
计算；如果是*/（就不用说了吧）。注意到这种计算是完全顺序的，完全适用于本问题。
如果采用这种方法，我们就不再需要专门的表达式求值函数，有可能大幅度提高效率。

这问题太无聊了！

有个笑话：
某男说，某某的老婆太无聊了，和他老公吵架炒了一个上午，
老婆问他，你怎么知道的，
答曰：我看着他们吵的