找到平衡括号的最少编辑次数？

Question

我对这个问题很困惑。我知道使用递归和动态编程作为改进来查找 2 个字符串之间的编辑距离，但是我对如何使用这个感到困惑。

不确定我的想法是否正确。但是我们有一串不平衡的括号说

String s = "((())))";

如何找到需要最少编辑次数的带平衡括号的字符串？

谁能举个例子解释一下？

我仍然不确定我是否解释正确。

Answer 1

虽然这个有趣的问题可以用评论中提到的动态规划来解决，但还有一个更简单的解决方案。可以用贪心算法解决。

这个贪心算法的想法来自于我们如何检查括号表达式的有效性。你将counter设置为0，遍历括号字符串，“(”处加1，“)”处减1。如果计数器始终保持在 0 以上或 0 并以 0 结束，则您有一个有效的字符串。

这意味着如果我们在遍历时遇到的最低值是-maxi，我们需要在开始时恰好添加-maxi“(”。调整添加的“(”的最终计数器值并添加足够的“)”最后以 0 结束。

算法的伪代码如下：

counter = 0
mini = 0
for each p in string:
  if p == "(":
    counter++
  else:
    counter--

  mini = min(counter, mini)

add -mini "(" at the start of the string
counter -= mini
add counter ")" at the end of the string

Answer 2

给定一个由左右括号组成的字符串，要求我们通过执行最少数量的删除、插入和替换操作来平衡它。

首先，让我们查看输入字符串并区分匹配对和不匹配字符。我们可以通过执行以下算法来标记属于匹配对的所有字符：

找到一个未标记的“(”，后面跟着一个未标记的“)”，两者之间有零个或多个标记字符。
如果不存在这样的一对字符，则终止算法。
否则，标记“(”和“)”。
Return 到第 1 步。

标记的货币对已经以零成本平衡，因此最佳做法是不再对它们进行任何操作。

现在让我们考虑未标记的字符。请注意，没有未标记的“(”后跟未标记的“)”，否则该对将被标记。因此，如果我们从左到右扫描未标记的字符，我们会发现零个或多个 ')' 字符后跟零个或多个 '(' 字符。

为了平衡')'字符的顺序，最好每隔一个重写为'('，从第一个开始，不包括最后一个。如果')'字符的个数为奇数, 最好删除最后一个

至于'('字符的顺序，最好每隔一个改写为')'，从第二个开始。如果有剩余的 '(' 字符，我们将其删除。以下 Python 代码实现上述步骤并显示中间结果。

def balance(s):  # s is a string of '(' and ')' characters in any order
  n = len(s)
  print('original string: %s' % s)

  # Mark all matched pairs
  marked = n * [ False ]
  left_parentheses = []
  for i, ch in enumerate(s):
    if ch == '(':
      left_parentheses.append(i)
    else:
      if len(left_parentheses) != 0:
        marked[i] = True
        marked[left_parentheses.pop()] = True

  # Display the matched pairs and unmatched characters.
  matched, remaining = [], []
  for i, ch in enumerate(s):
    if marked[i]:
      matched.append(ch)
      remaining.append(' ')
    else:
      matched.append(' ')
      remaining.append(ch)
  print('  matched pairs: %s' % ''.join(matched))
  print('      unmatched: %s' % ''.join(remaining))

  cost = 0
  deleted = n * [ False ]
  new_chars = list(s)

  # Balance the unmatched ')' characters.
  right_count, last_right = 0, -1
  for i, ch in enumerate(s):
    if not marked[i] and ch == ')':
      right_count += 1
      if right_count % 2 == 1:
        new_chars[i] = '('
        cost += 1
        last_right = i
  if right_count % 2 == 1:      # Delete the last ')' if we couldn't match it.
    deleted[last_right] = True  # The cost was incremented during replacement.

  # Balance the unmatched '(' characters.
  left_count, last_left = 0, -1
  for i, ch in enumerate(s):
    if not marked[i] and ch == '(':
      left_count += 1
      if left_count % 2 == 0:
        new_chars[i] = ')'
        cost += 1
      else:
        last_left = i
  if left_count % 2 == 1:      # Delete the last '(' if we couldn't match it.
    deleted[last_left] = True  # This character wasn't replaced, so we must
    cost += 1                  # increment the cost now.

  # Display the outcome of replacing and deleting.
  balanced = []
  for i, ch in enumerate(new_chars):
    if marked[i] or deleted[i]:
      balanced.append(' ')
    else:
      balanced.append(ch)
  print('        balance: %s' % ''.join(balanced))

  # Display the cost of balancing and the overall balanced string.
  print('           cost: %d' % cost)
  result = []
  for i, ch in enumerate(new_chars):
    if not deleted[i]:  # Skip deleted characters.
      result.append(ch)
  print('     new string: %s' % ''.join(result))


balance(')()(()())))()((())((')

对于测试用例')()(()())))()((())(('，输出如下

original string: )()(()())))()((())((
  matched pairs:  ()(()())  () (())
      unmatched: )        ))  (    ((
        balance: (        )   (    )
           cost: 4
     new string: (()(()()))()((()))

Answer 3

我用DP算法解决问题很累，通过了几个自己编的测试用例。如果您认为正确，请告诉我。

设 P(i,j) 为使字符串 S[i..j] 平衡的最小编辑次数。

当S[i]等于S[j]时，最小编辑数显然是P(i+1,j-1)

当 S[i] != S[j] 时，有几个选项可以使字符串平衡，但最后我们可以在 i 的前面添加 '(' 或在 j 的末尾添加 ')'，或者删除i 或 j 处的括号。在所有这些情况下，最小编辑次数为 min{P(i+1, j), P(i, j-1)} + 1.

因此我们有以下DP公式：

P(i,j) = 0 if i > j
       = P(i + 1, j - 1) if S[i] matches S[j] OR S[i] and S[j] are not parenthesis
       = min{P(i + 1, j), P(i, j - 1)} + 1

Answer 4

想法很简单：

查找遗留了无法配对的左括号和右括号的最终字符串。请记住，在最后一个字符串中，右括号将出现在第一位，然后是左括号。

现在我们必须分别编辑左括号和右括号。

例如：对于右括号：

(1) 如果是偶数长度：
最小的平衡编辑是将半封闭括号更改为开放括号。
所以 minEdit = closeBracketCount/2
。 (2) 如果是奇数长度：
最小的平衡编辑将执行上述步骤 1 并删除剩余的 1 个支架。
所以 minEdit = closeBracketCount/2 + 1

对于开括号：
(1) 如果是偶数长度：
最小的平衡编辑将改变半开括号以关闭括号。
所以 minEdit = openBracketCount/2.
(2) 如果是奇数长度：
最小的平衡编辑将执行上述步骤 1 并删除剩余的 1 个支架。
所以 minEdit = openBracketCount/2 + 1

这里是运行代码：http://codeshare.io/bX1Dt
告诉我你的想法。

Answer 5

我会使用堆栈来有效地平衡它们。这是 python 代码：

a=['(((((','a(b)c)','((())))',')()(()())))()((())((']


def balance(s):
  st=[]

  l=len(s)
  i=0

  while i<l:
    if s[i]=='(':
      st.append(i)
    elif s[i]==')':
      if st:
        st.pop()
      else:
        del s[i]
        i-=1
        l-=1

    i+=1

  while st:
    del s[st.pop()]

  return ''.join(s)

for i in a:
  print balance(list(i))

输出:

Empty 
a(b)c
((()))
()(()())()(())

Answer 6

 //fisher
   public int minInsertions(String s) {
        Stack<Character> stack = new Stack<>();
        int insertionsNeeded = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                if (stack.isEmpty()) {
                    stack.add(c);
                } else {
                    if (stack.peek() == ')') {
                        //in this case, we need to add one more ')' to get two consecutive right paren, then we could pop the one ')' and one '(' off the stack
                        insertionsNeeded++;
                        stack.pop();
                        stack.pop();
                        stack.add(c);
                    } else {
                        stack.add(c);
                    }
                }
            } else if (c == ')') {
                if (stack.isEmpty()) {
                    //in this case, we need to add one '(' before we add this ')' onto this stack
                    insertionsNeeded++;
                    stack.add('(');
                    stack.add(c);
                } else {
                    if (stack.peek() == ')') {
                        //in this case, we could pop the one ')' and one '(' off the stack
                        stack.pop();
                        stack.pop();
                    } else {
                        stack.add(c);
                    }
                }
            }
        }
        if (stack.isEmpty()) {
            return insertionsNeeded;
        } else {
            while (!stack.isEmpty()) {
                char pop = stack.pop();
                if (pop == '(') {
                    insertionsNeeded += 2;
                } else {
                    insertionsNeeded++;
                    stack.pop();
                }
            }
            return insertionsNeeded;
        }
    }
}

找到平衡括号的最少编辑次数？

Find the minimum number of edits to balance parentheses?

algorithm

parentheses