A STACKS PROBLEM

Homework?

What code do you have thus far?  If you don't have any code what algorithm do you think will work?

Please explain what makes a correct string.  Is it any string where there are equal number of open and close ( ) and [ ]?

] [  valid?
) (  valid?

Does the nesting have to match?
( ( ( [ [ ] } ] ) ) - nesting doesn't match.  valid?

mlmcc

Here is a typical stack implementation.
In TP however, where strings are 255 bytes long you could solve this stack algo using array[1..255] of byte or char
wich is faster and easier to implement and execution speed, but you will loose the main object of your excercise... as you will if you just copy this code without stuying it.


Program Stack1; { by Socrates }
  Function CheckBrackets(s : String) : Byte;
    Type
       BStackR = Record
                   Prev : Pointer;
                   Brt  : Byte;
                 end;
       Bstack = ^BStackR;

    Function PushStack(B : Byte; PrevTop: Bstack) : Bstack;
    var
      TSt : BStack;
    begin
      New(Tst);
      Tst^.Brt:=b;
      Tst^.Prev :=PrevTop;
      PushStack:=Tst;
    end;

    Function PopStack(StackTop:Bstack) : BStack;
    var
      Tst : Bstack;
    begin
      If StackTop=Nil Then Exit;
      Tst:=StackTop^.Prev;
      Dispose(StackTop);
      PopStack:=Tst;
    end;


  var
    St : Bstack;
    i,ErrorPos  : Byte;
  begin
    St:=Nil;
    ErrorPos:=0;
    i:=1;
    repeat
      Case s[i] OF
        '(' : st:=PushStack(1,st);
        '[' : st:=PushStack(2,st);
        ')' : IF st<>Nil Then
                IF (st^.Brt=1) Then st:=Popstack(st) Else ErrorPos:=i
              else Errorpos:=i;
        ']' : IF st<>Nil Then
                 IF (st^.Brt=2) Then st:=Popstack(st) Else ErrorPos:=i
              else Errorpos:=i;
      end;
      Inc(i);
    until (i>Length(s)) Or (ErrorPos>0);
    While st<>Nil do st:=Popstack(st);
    CheckBrackets:=ErrorPos;
  end;

var
  r : Byte;
begin
  r:=CheckBrackets('sdsd(sdsD)sdsd((()))sdsd([sdsd])');
  IF r>0 then WriteLn('String 1 Wrong at :',r) ELSE Writeln('String 1 ok');
  r:=CheckBrackets('sdsd(sdsD)sdsd((()/]))sdsd([sdsd])');
  IF r>0 then WriteLn('String 2 Wrong at :',r) ELSE Writeln('String 1 ok');
  r:=CheckBrackets('sdsd(sdsD)sdsd((()/))sdsd([sdsd]))');
  IF r>0 then WriteLn('String 3 Wrong at :',r) ELSE Writeln('String 1 ok');
end.

or give every bracket it's "counter" if You read "opening" bracket ( then increase counter if "closeing" decrease counter after You finish reading input check if counter equals 0.
ziolko.

...value of counter will be equal to number of items on stack (proposed by sokpas :-) )
ziolko.

This is not accurate ziolko, you want to have exact match suppose you have (([)]) this will not raise an error.

sokpas two kinds of brackets - two counters, still You can control counter's inc/dec or difference between them. Counter was alternative idea (I'm useing it to Quote/UnQoute strings), I supose mathematics2002 has homework and goal of this homework is not to play with brackets but learn how to implement stack (it was mine homework some time ago, too :-)).
ziolko.

Oops there are some trivial errors and I forgot to test if (length(s) div 2) * 2 = length(s) - that is if the length is even.

homework done no points given.
ziolko.

mathematics2002:
This old question needs to be finalized -- accept an answer, split points, or get a refund.  For information on your options, please click here-> http:/help/closing.jsp#1 
EXPERTS:
Post your closing recommendations!  No comment means you don't care.