unit U_Expressions2002;

{Copyright  © 2002, Gary Darby,  www.DelphiForFun.org
 This program may be used or modified for any non-commercial purpose
 so long as this original notice remains in place.
 All other rights are reserved
 }

{
 Insert + or * signs as required into the string of digits 123456789 to
 form an expression that evaluates to 2002.

 Integers 1 Through 9 must appear in increasing order.  Integers used
 in the expression are may be a concatenation of digits.  Assume,
 as usual, that multiplications are performed before additions.
 }

interface

uses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
  StdCtrls, ComCtrls;

type
  TForm1 = class(TForm)
    Memo1: TMemo;
    CalcBtn: TButton;
    SolutionBox: TListBox;
    TargetEdt: TEdit;
    Label1: TLabel;
    StatusBar1: TStatusBar;
    procedure CalcBtnClick(Sender: TObject);
    procedure TargetEdtKeyPress(Sender: TObject; var Key: Char);
  end;

var Form1: TForm1;

implementation

{$R *.DFM}
type Tarray=array of integer;

{*********** Power ************}
function Power(n,exponent:integer):integer;
{raise integer, n,  to the integer ,exponent, power}
var i:integer;
begin
  result:=n;
  for i := 1 to exponent-1 do result:=result*n;
end;

{*************** Convertbase ************}
procedure convertbase (n,base:integer;var converted:Tarray);
{convert numbers to another base - 3 in this case}
var
  i,w:integer;
begin
  w:=n;
  for i := high(converted)  downto 0 do
  begin
    converted[i]:= w mod base;
    w:=w div base;
  end;
end;

var signstr:array[1..2] of char=('+','*'); {for display}

{************** TForm1.CalcBtnClick ********}
procedure TForm1.CalcBtnClick(Sender: TObject);
{Solve the problem}
{Plan is to generate 8-digit base 3 numbers from 0 to 3^8-1
 and use the resulting numbers as indicators of the operation
 to perform  for each of the 8 "slots" between the 9 digits:
   0=concatenate, 1=+, 2=*

 Because * has priority over +, we'll just push the operaands
 onto a "stack".  When we have a * operand, we can can go ahead and
 multiply the top stack operand by the next number and push the result
 back onto the stack
 }

var
  signs:Tarray; {the base 3 numbers}
  i,j:integer;
  sum, nextnum, lastop, target:integer;
  s:string;
  stack:array[1..8] of integer; {"stack" to hold interim results}
  count:integer;  {nbr of entries in the stack}

      {********* push ********}
      procedure push(n:integer);
      {a simple push procedure}
      begin
        inc(count);
        stack[count]:=n;
      end;

      {********** Pop *******}
      function pop:integer;
      {a simple Pop procedure - returns 0 if there are no items in the stack}
      begin
        if count>0 then
        begin
          result:=stack[count];
          dec(count);
        end
        else result:=0;
      end;

begin
  target:=strtoint(targetedt.text);
  Solutionbox.clear;
  setlength(signs,8);
  count:=0; {clear the stack}
  for j:= 0 to power(3,8) do
  begin
    Convertbase(j,3,signs); {get the next arrangement}
    nextnum:=1; lastop:=-1;
    for i:= 0 to 8 do
    begin
      if (i=8{handle lastop and last number}) or (signs[i]>0)  then
      begin {current op is + or *}
        case lastop of
          1: push(nextnum);
          2: push(pop*nextnum);
          else push(nextnum); {no last op, handles first time}
        end; {case}
        nextnum:=i+2;
        if i<=high(signs) then lastop:=signs[i];{save the op for next iteration}
      end
      else nextnum:=nextnum*10+i+2;{current op is concatenate, append the next digit}
    end;
    {all terms are in the stack, everything in the stack can be summed}
    sum:=0;
    while count>0 do sum:=sum+pop;
    if sum=target then {solution found}
    begin
      s:=''; {make a solution display string}
      For i:= 0 to 8 do
      begin
        s:=s+inttostr(i+1); {get a digit}
        case signs[i] of  {add a sign if necessary}
          1, 2: s:= s+ signstr[signs[i]];
        end;
      end;
      s:=s+' = '+targetedt.text;
      Solutionbox.items.add(s);
    end;
  end;
end;

{*************** TForm1.TargetEdtKeyPress ***********}
procedure TForm1.TargetEdtKeyPress(Sender: TObject; var Key: Char);
{make sure only digits (or backspace) are entered in the edit field}
begin
  If not (key in ['0'..'9',#8]) then
  begin
    key:=#0;
    beep
  end;
end;

end.