Проверьте правильность порядка скобок

Question

Что я пытаюсь сделать, определяется, находятся ли скобки в правильном порядке. Например, ([][[]]<<>>) vallid, но ][]<<(>>) нет.

У меня есть рабочая версия, но она имеет ужасную эффективность, и когда она получает 1000+ скобок, ее просто сумасшедшая медленная. Я надеялся, что кто-то может предложить некоторые возможные улучшения или другой способ сделать это.

Вот мой код:

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. 

Входные данные в файле zavorky.in выглядеть, например, так:

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

я определить для каждой строки, является ли он действительным или нет. Максимальное количество скобок в строке равно 10000.

Answer 1

Вы читаете символы из своего файла. Чтение файла в байтовом режиме происходит очень медленно. Вам нужно оптимизировать способ чтения строк (буферов) или сначала загрузить файл в память.

Далее я предлагаю другой способ обработки взятой строки.

Сначала я объявить consts, что будет утверждать, кронштейны, которые вы могли бы иметь:

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

я решил сделать это, как теперь вы не ограничены длиной выражения скобки и/или количество скобок типа. Каждое закрытие и соответствующая открывающая скобка имеет значение индекса, равное 10.

А вот код функции:

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; 

Может быть, мы делаем дополнительную работу, создав массив байтов, но, кажется, этот метод i) более прост для понимания и ii) является гибким, так как мы можем изменить длину выражений в скобках, например, использовать и установить begin/end скобки и т. д.

приложена

Как только я вижу, что главная проблема заключается в организации блока чтения файла Привожу представление о том, как это сделать:

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

Вы сохраняете все данные в памяти (даже пару раз), а затем у вас много проверок. Я думаю, что вы на правильном пути, но есть намного более простые шаги, которые вы могли бы выполнить.

1. Сделать массив целых чисел (по умолчанию = 0) с длиной число скобок у вас есть (например, '([ /* ($ <! << ' ==> 6)
2. Теперь, чтобы убедиться, что вы следуете требованиям. Прочитайте файл по строкам и учтите только первые 10000. This может помочь.
3. Каждый раз, когда вы найдете элемент из первого массива (например, leftBrackets) добавить +1 к значению индекса coresponding массива шага 1. Пример будет: '[' ==> checkArray[1] += 1
4. сделать то же самое для rightBrackets, но это проверка времени, если значение больше чем 0. Если да, то вычтите 1 таким же образом (например ']' ==> checkArray[1] -= 1), иначе вы просто нашли недействителен кронштейн

Я надеюсь, что это помогает и удачи.

Answer 3

Я думаю, следующий должен работа, и будет порядок O (n), где n - длина строки. Сначала создайте две функции.

IsLeft (бюстгальтер: TBracket) может определить, есть ли кронштейн левый кронштейн или правая скобка, так IsLeft ('< ') = TRUE, IsLeft (' >>') = FALSE.

IsMatchingPair (бюстгальтер, кет: TBracket) можно определить, если две скобы одного и того же 'типа', так что IsMatchingPair ('(', ')') = TRUE, но IsMatchingPair ('{', '> > ') = FALSE.

Затем построить стек TBracketStack с тремя функциями процедура принудительной (бюстгальтер: TBracket) и функции Pop: TBracket и функции IsEmpty: Boolean.

Теперь следующий алгоритм должен работать (с небольшим количеством дополнительного кода, необходимого для обеспечения вы не падаете от конца строки неожиданно):

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;