A STACKS PROBLEM

mathematics2002
mathematics2002 used Ask the Experts™
on
I need a program which reads a string of brackets ()[] and recognises when a string is right. A string is ok at these cases: () [] (()) ([)] ((..(](()] I would prefer Pascal language When the program find a wrong says the position of the wrong
Comment
Watch Question

Do more with

Expert Office
EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®
Mike McCrackenSenior Consultant
Most Valuable Expert 2011
Top Expert 2013

Commented:
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

Commented:
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.
Top Expert 2008

Commented:
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.
OWASP: Threats Fundamentals

Learn the top ten threats that are present in modern web-application development and how to protect your business from them.

Top Expert 2008

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

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

Commented:
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.
Commented:
I think, that in a correct string 1) the str length will be even 2) if s[1] = '(' then s[length(s)] = ')' etc.

So,

function testStr( s: string): boolean;
var n: byte;x: boolean;
begin
 x:=true;
 for n:=1 to length(s) div 2 do
  begin
   if (s[n] = '(') then if (s[length(s-n+1)] <> ')' then begin x:=false; break; end;
   if (s[n] = '[') then if (s[length(s-n+1)] <> ']' then begin x:=false; break; end;
   if (s[n] not in '[(') then begin x:=false; break; end;
  end;
 testStr:=x;
end;

I hope you understand it.

Commented:
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.
Top Expert 2008

Commented:
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.

Do more with

Expert Office
Submit tech questions to Ask the Experts™ at any time to receive solutions, advice, and new ideas from leading industry professionals.

Start 7-Day Free Trial