Vérifiez si l'ordre de support est valide

Question

ce que j'essaie de faire, est de déterminer si les crochets sont dans le bon ordre. Par exemple ([][[]]<<>>) est vallid, mais ][]<<(>>) ne l'est pas.

J'ai obtenu une version de travail, mais il a une efficacité terrible et quand il obtient 1000+ supports, c'est juste fou lent. J'espérais que quelqu'un pourrait suggérer des améliorations possibles ou une autre façon de le faire.

Voici mon code:

program Codex; 

const 
    C_FNAME = 'zavorky.in'; 

var TmpChar  : char; 
    leftBrackets, rightBrackets : string; 
    bracketPos   : integer; 
    i,i2,i3   : integer; 
    Arr, empty : array [0..10000] of String[2]; 
    tfIn : Text; 
    result : boolean; 

begin 
    leftBrackets := ' ([ /* ($ <! << '; 
    rightBrackets := ') ] */ $) !> >> '; 
    i := 0; 
    result := true; 
    Assign(tfIn, C_FNAME); 
    Reset(tfIn); 

    { load data into array } 
    while not eof(tfIn) do 
    begin 
     while not eoln(tfIn) do 
     begin 
      read(tfIn, TmpChar); 
      if (TmpChar <> ' ') then begin 
       if (TmpChar <> '') then begin 
        Arr[i] := Arr[i] + TmpChar; 
        end 
       end 
      else 
       begin          
        i := i + 1; 
       end 
     end; 

     i2 := -1; 
     while (i2 < 10000) do begin  
      i2 := i2 + 1; 
      {if (i2 = 0) then 
       writeln('STARTED LOOP!');} 
      if (Arr[i2] <> '') then begin 
       bracketPos := Pos(' ' + Arr[i2] + ' ',rightBrackets); 
       if (bracketPos > 0) then begin 
        if (i2 > 0) then begin 
         if(bracketPos = Pos(' ' + Arr[i2-1] + ' ',leftBrackets)) then begin 
          {write(Arr[i2-1] + ' and ' + Arr[i2] + ' - MATCH ');} 

          Arr[i2-1] := ''; 
          Arr[i2] := ''; 
          { reindex our array } 
          for i3 := i2 to 10000 - 2 do begin 
           Arr[i3 - 1] := Arr[i3+1]; 
           end; 

          i2 := -1; 
          end; 
         end;      
        end; 
       end; 
      end; 

     {writeln('RESULT: ');} 
     For i2:=0 to 10 do begin 
      if (Arr[i2] <> '') then begin 
       {write(Arr[i2]);} 
       result := false; 
      end; 
      {else 
      write('M');} 
     end; 

     if (result = true) then begin 
      writeln('true'); 
      end 
     else begin 
      writeln('false'); 
     end; 

     result := true; 

     { move to next row in file } 
     Arr := empty; 
     i := 0; 
     readln(tfIn); 
    end; 

    Close(tfIn); 

    readln; 
end. 

Les données d'entrée dans le fichier zavorky.in chercher par exemple comme ceci:

<< $) >> << >> ($ $) [ ] <! () !> 
() /* << /* [ ] */ >> <! !> */ 

je détermine pour chaque ligne si elle est valide ou non. Le nombre maximal de parenthèses sur une ligne est 10000.

Answer 1

Vous lisez les caractères de votre fichier. Le fichier lu en mode byte by byte est très lent. Vous devez optimiser la façon de lire les chaînes (tampons) ou charger le fichier en mémoire en premier.

Ci-dessous, je propose l'autre façon de traiter la chaîne récupérée.

D'abord, je déclare les consts qui énonceront les supports que vous pourriez avoir:

const 
    OBr: array [1 .. 5{6}] of string = ('(', '[', '/*', '<!', '<<'{, 'begin'}); 
    CBr: array [11 .. 15{16}] of string = (')', ']', '*/', '!>', '>>'{, 'end'}); 

j'ai décidé de le faire que maintenant, vous n'êtes pas limité à la longueur de l'expression des supports et/ou le nombre de supports ' les types. Chaque fermeture et le support d'ouverture correspondant a l'indice de différence égal à 10.

Et voici le code de la fonction:

function ExpressionIsValid(const InputStr: string): boolean; 
var 
    BracketsArray: array of byte; 
    i, Offset, CurrPos: word; 
    Stack: array of byte; 
begin 
    result := false; 
    Setlength(BracketsArray, Length(InputStr) + 1); 
    for i := 0 to High(BracketsArray) do 
    BracketsArray[i] := 0; // initialize the pos array 

    for i := Low(OBr) to High(OBr) do 
    begin 
    Offset := 1; 
    Repeat 
     CurrPos := Pos(OBr[i], InputStr, Offset); 
     if CurrPos > 0 then 
     begin 
     BracketsArray[CurrPos] := i; 
     Offset := CurrPos + 1; 
     end; 
    Until CurrPos = 0; 
    end; // insert the positions of the opening brackets 

    for i := Low(CBr) to High(CBr) do 
    begin 
    Offset := 1; 
    Repeat 
     CurrPos := Pos(CBr[i], InputStr, Offset); 
     if CurrPos > 0 then 
     begin 
     BracketsArray[CurrPos] := i; 
     Offset := CurrPos + 1; 
     end; 
    Until CurrPos = 0; 
    end; // insert the positions of the closing brackets 

    Setlength(Stack, 0); // initialize the stack to push/pop the last bracket 
    for i := 0 to High(BracketsArray) do 
    case BracketsArray[i] of 
     Low(OBr) .. High(OBr): 
     begin 
      Setlength(Stack, Length(Stack) + 1); 
      Stack[High(Stack)] := BracketsArray[i]; 
     end; // there is an opening bracket 
     Low(CBr) .. High(CBr): 
     begin 
      if Length(Stack) = 0 then 
      exit(false); // we can not begin an expression with Closing bracket 
      if Stack[High(Stack)] <> BracketsArray[i] - 10 then 
      exit(false) // here we do check if the previous bracket suits the 
         // closing bracket 
      else 
      Setlength(Stack, Length(Stack) - 1); // remove the last opening 
               // bracket from stack 
     end; 
    end; 
    if Length(Stack) = 0 then 
    result := true; 
end; 

Peut-être, nous faisons un travail supplémentaire en créant un tableau d'octets, mais il semble que cette méthode est i) plus facile à comprendre et ii) est flexible car nous pouvons changer la longueur des expressions de parenthèses par exemple utiliser et vérifier begin/end parenthèses etc.

Annexés

Dès que je vois que le problème majeur est dans l'organisation de la lecture du bloc de fichier que je donne ici une idée de la façon de le faire:

procedure BlckRead; 
var 
    f: file; 
    pc, pline: { PChar } PAnsiChar; 
    Ch: { Char } AnsiChar; 
    LngthLine, LngthPc: word; 
begin 
    AssignFile(f, 'b:\br.txt'); //open the file 
    Reset(f, 1); 
    GetMem(pc, FileSize(f) + 1); //initialize memory blocks 
    inc(pc, FileSize(f)); //null terminate the string 
    pc^ := #0; 
    dec(pc, FileSize(f)); //return the pointer to the beginning of the block 

    GetMem(pline, FileSize(f)); //not optimal, but here is just an idea. 
    pline^ := #0;//set termination => length=0 
    BlockRead(f, pc^, FileSize(f)); // read the whole file 
            //you can optimize that if you wish, 
            //add exception catchers etc. 
    LngthLine := 0; // current pointers' offsets 
    LngthPc := 0; 
    repeat 
    repeat 
     Ch := pc^; 
     if (Ch <> #$D) and (Ch <> #$A) and (Ch <> #$0) then 
     begin // if the symbol is not string-terminating then we append it to pc 
     pline^ := Ch; 
     inc(pline); 
     inc(pc); 
     inc(LngthPc); 
     inc(LngthLine); 
     end 
     else 
     begin //otherwise we terminate pc with Chr($0); 
     pline^ := #0; 
     inc(LngthPc); 
     if LngthPc < FileSize(f) then 
      inc(pc); 
     end; 
    until (Ch = Chr($D)) or (Ch = Chr($A)) or (Ch = Chr($0)) or 
     (LngthPc = FileSize(f)); 

    dec(pline, LngthLine); 
    if LngthLine > 0 then //or do other outputs 
     Showmessage(pline + #13#10 + Booltostr(ExpressionIsValid(pline), true)); 

    pline^ := #0; //actually can be skipped but you know your file structure better 
    LngthLine := 0; 
    until LngthPc = FileSize(f); 

    FreeMem(pline);       //free the blocks and close the file 
    dec(pc, FileSize(f) - 1); 
    FreeMem(pc); 
    CloseFile(f); 
end; 

Answer 2

Vous sauvegardez toutes les données en mémoire (même plusieurs fois) et vous avez beaucoup de vérifications. Je pense que vous êtes sur la bonne voie, mais il y a des étapes beaucoup plus faciles que vous pourriez suivre.

1. Faire un tableau de nombres entiers (par défaut = 0) avec la longueur du nombre de supports que vous avez (par exemple '([ /* ($ <! << ' ==> 6)
2. Maintenant, pour vous assurer que vous suivez les exigences. Lire le fichier ligne par ligne et ne prendre en compte que le premier 10000. This pourrait aider.
3. Chaque fois que vous trouvez un élément du premier ensemble (par exemple leftBrackets) ajouter +1 à la valeur de l'indice du tableau lui correspondant de l'étape 1. Exemple serait: '[' ==> checkArray[1] += 1
4. Faites la même chose pour rightBrackets mais cette heure de départ si la valeur est supérieure à 0. Si oui, alors soustraire 1 de la même manière (par exemple ']' ==> checkArray[1] -= 1) sinon vous venez de trouver le support invalide

J'espère que cette aide et bonne chance.

Answer 3

Je pense que ce qui suit devrait travailler, et sera ordre O (n), où n est la longueur de la chaîne. Première construction de deux fonctions.

IsLeft (soutien-gorge: TBracket) peut déterminer si un support est un support gauche ou un crochet droit, si IsLeft ('< ') = TRUE, IsLeft (' >>') = FAUX.

IsMatchingPair (soutien-gorge, ket: TBracket) peut déterminer si deux supports sont de la même 'type', de sorte IsMatchingPair ('(', ')') = TRUE, mais IsMatchingPair ('{', '> > ') = FAUX.

ensuite construire une pile TBracketStack avec trois fonctions procédure poussoirs (soutien-gorge: TBracket) et fonction Pop: TBracket et fonction IsEmpty: booléennes.

Maintenant, l'algorithme devrait fonctionner (avec un peu de code supplémentaire nécessaire pour vous assurer de ne pas tomber à la fin de la chaîne de façon inattendue):

BracketError := FALSE; 
while StillBracketsToProcess(BracketString) and not BracketError do 
begin 
    bra := GetNextBracket(BracketString); 
    if IsLeft(bra) then 
    Stack.Push(bra) 
    else 
    BracketError := Stack.IsEmpty or not IsMatchingPair(Stack.Pop,bra) 
end;