Правильная скобка

Question

Я наткнулся на эту проблему:.

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

например.

)())

Ответ: 1

Прежде всего, я думаю, что было бы полезно использовать синтаксический, но программа, кажется, не работает правильно.

void X() { 
    if(first=='(') { 
     firt=fgetc(fi); 
     X(); 
     if(first!=')') 
      er++; 
     first=fgetc(fi); 
    } 
    else { 
     .. 
    } 
} 

Что было бы началом?

Thanks

Answer 1

Я хотел бы предложить алгоритм. Сначала псевдо-код:

For each input character C: 
    If C is '(' then 
     increment counter 
    else if counter is 0 then // The closing paren has no matching opening 
     increment moves   // so we "flip" it and counting as the opening 
     increment counter 
    else 
     decrement counter  // This closing paren is balanced 
    end if 
end For 
// Now the counter is containing the number of unbalanced opening parentheses, 
// so we add half of this number to moves, as half of them have to be balanced 
moves = moves + counter/2 

return moves 

Сейчас в C:

#include <stdio.h> 
#include <string.h> 
int main(void) { 

    char input[] = "(((("; 
    int len = strlen(input); 
    int i; 
    int moves = 0; 
    int count = 0; 

    for (i=0; i < len; i++) 
    { 
     if (input[i] == '(') 
     { 
      count ++; 
     } 
     else 
     { 
      if (count == 0) 
      { 
       count ++; 
       moves ++; 
      } 
      else 
      { 
       count --; 
      } 
     } 
    } 

    moves += count/2; 
    printf("Moves: %d\n", moves); 
    return 0; 
} 

Вы приглашены, чтобы проверить его с различными входами here, доказать это правильность или опровергнуть с входом контрпример :)

Answer 2

Вот в одном направлении (в Паскале). Исправляет фактическую строку и показывает до и после.

function FixBrackets(s: string): Integer; 
var 
    LeftToProcess, OpenCount: Integer; 
    I: Integer; 
begin 
    writeln('in:', S); 
    Result := 0; 
    LeftToProcess := length(s); 
    OpenCount := 0; 
    for I := 1 to LeftToProcess do begin 
    case S[I] of 
    '(' : 
     if LeftToProcess <= OpenCount then begin 
     // we must close all 
      S[I] := ')'; 
      inc(Result); 
     end else 
     inc(OpenCount); 
    ')' : 
     if OpenCount = 0 then begin 
     // we have no open pars to close, so this has to be a new open 
     S[I] := '('; 
     inc(Result); 
     inc(OpenCount); 
     end else 
     dec(OpenCount); 
    end; 
    dec(LeftToProcess); 
    end; 
    writeln('out:', s); 
end; 

Answer 3

Вот ответ на C++:

template<class T> 
int count_changes(T begin, T end) { 
    int offset = 0; 
    int changes = 0; 
    for (auto it = begin; it != end; ++it) { 
     if (*it == '(') ++offset; 
     else --offset; 

     if (offset < 0) { 
      offset = 1; 
      changes++; 
     } 
    } 

    return changes + ((offset + 1)/2); 
} 

int main() { 
    std::string parens { "))(()" }; 

    cout << parens << " : " << count_changes(parens.begin(), parens.end()) << endl; 
}