正确的括号

Question

我遇到了这个问题:

“它给出了一串圆括号。这个字符串代表一个不一定正确的括号。你可以进行下一步:你可以将左括号'('更改为右括号')'，反之亦然。你必须计算出使括号正确所需的最少移动次数。”

例如

)())

答案:1

首先，我认为使用解析会很有用，但程序似乎运行不正常。

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

开始的想法是什么？

谢谢

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 ，证明它的正确性或用反例输入反驳:)