string 如何确定一串括号、大括号和方括号的有效性？

How to find validity of a string of parentheses, curly brackets and square brackets?

提问by Rajendra Uppal

I recently came in contact with this interesting problem. You are given a string containing just the characters '(', ')', '{', '}', '['and ']', for example, "[{()}]", you need to write a function which will check validity of such an input string, function may be like this:
bool isValid(char* s);
these brackets have to close in the correct order, for example "()"and "()[]{}"are all valid but "(]", "([)]"and "{{{{"are not!

我最近接触到了这个有趣的问题。您将获得只包含字符的字符串'('，')'，'{'，'}'，'['和']'，例如"[{()}]"，你需要写这将检查这些输入字符串的有效性的函数，函数可能是这样的：
bool isValid(char* s);
这些支架必须关闭以正确的顺序，例如"()"和"()[]{}"都是有效的但是"(]"，"([)]"并且"{{{{"不是！

I came out with following O(n) time and O(n) space complexity solution, which works fine:

我提出了以下 O(n) 时间和 O(n) 空间复杂度的解决方案，效果很好：

1. Maintain a stack of characters.
2. Whenever you find opening braces '(', '{'OR '['push it on the stack.
3. Whenever you find closing braces ')', '}'OR ']', check if top of stack is corresponding opening bracket, if yes, then pop the stack, else break the loop and return false.
4. Repeat steps 2 - 3 until end of the string.

1. 维护一堆字符。
2. 每当您找到大括号'('，'{'或'['将其推入堆栈。
3. 每当您找到右大括号')', '}'OR 时']'，请检查堆栈顶部是否是对应的左括号，如果是，则弹出堆栈，否则中断循环并返回 false。
4. 重复步骤 2 - 3，直到字符串结束。

This works, but can we optimize it for space, may be constant extra space, I understand that time complexity cannot be less than O(n) as we have to look at every character.

这是可行的，但是我们可以针对空间优化它吗，可能是恒定的额外空间，我知道时间复杂度不能小于 O(n)，因为我们必须查看每个字符。

So my question is can we solve this problem in O(1) space?

所以我的问题是我们可以在 O(1) 空间中解决这个问题吗？

采纳答案by user287792

Actually, there's a deterministic log-space algorithm due to Ritchie and Springsteel: http://dx.doi.org/10.1016/S0019-9958(72)90205-7(paywalled, sorrynot online). Since we need log bits to index the string, this is space-optimal.

实际上，由于 Ritchie 和 Springsteel，有一个确定性对数空间算法：http: //dx.doi.org/10.1016/S0019-9958( 72) 90205-7（付费专区，抱歉不在线）。由于我们需要对数位来索引字符串，因此这是空间最优的。

---

---

If you're willing to accept one-sided error, then there's an algorithm that uses n polylog(n) time and polylog(n) space: http://www.eccc.uni-trier.de/report/2009/119/

如果您愿意接受片面错误，那么有一种使用 n polylog(n) 时间和 polylog(n) 空间的算法：http: //www.eccc.uni-trier.de/report/2009/119 /

回答by Contango

With reference to the excellent answer from Matthieu M., here is an implementation in C# that seems to work beautifully.

参考Matthieu M.的出色回答，这里有一个 C# 实现，看起来效果很好。

/// <summary>
/// Checks to see if brackets are well formed.
/// Passes "Valid parentheses" challenge on www.codeeval.com,
/// which is a programming challenge site much like www.projecteuler.net.
/// </summary>
/// <param name="input">Input string, consisting of nothing but various types of brackets.</param>
/// <returns>True if brackets are well formed, false if not.</returns>
static bool IsWellFormedBrackets(string input)
{
    string previous = "";
    while (input.Length != previous.Length)
    {
        previous = input;
        input = input
            .Replace("()", String.Empty)
            .Replace("[]", String.Empty)
            .Replace("{}", String.Empty);                
    }
    return (input.Length == 0);
}

Essentially, all it does is remove pairs of brackets until there are none left to remove; if there is anything left the brackets are not well formed.

本质上，它所做的只是删除成对的括号，直到没有要删除的括号为止；如果有任何剩余，则括号的格式不正确。

Examples of well formed brackets:

格式良好的括号示例：

()[]
{()[]}

Example of malformed brackets:

畸形括号示例：

([)]
{()[}]

回答by user287792

If the input is read-only, I don't think we can do O(1) space. It is a well known fact that any O(1) space decidable language is regular (i.e writeable as a regular expression). The set of strings you have is not a regular language.

如果输入是只读的，我认为我们不能做 O(1) 空间。众所周知，任何 O(1) 空间可判定语言都是正则的（即可写为正则表达式）。您拥有的字符串集不是常规语言。

Of course, this is about a Turing Machine. I would expect it to be true for fixed word RAM machines too.

当然，这是关于图灵机。我希望它也适用于固定字 RAM 机器。

回答by Matthieu M.

Edit:Although simple, this algorithm is actually O(n^2) in terms of character comparisons. To demonstrate it, one can simply generate a string as '(' * n + ')' * n.

编辑：虽然简单，但这个算法在字符比较方面实际上是 O(n^2)。为了演示它，可以简单地将字符串生成为'(' * n + ')' * n.

I have a simple, though perhaps erroneous idea, that I will submit to your criticisms.

我有一个简单但可能是错误的想法，我将接受您的批评。

It's a destructive algorithm, which means that if you ever need the string it would not help (since you would need to copy it down).

这是一种破坏性算法，这意味着如果您需要该字符串，它也无济于事（因为您需要将其复制下来）。

Otherwise, the algorithm work with a simple index within the current string.

否则，该算法使用当前字符串中的简单索引。

The idea is to remove pairs one after the others:

这个想法是一个接一个地删除对：

1. ([{}()])
2. ([()])
3. ([])
4. ()
5. empty-> OK

1. ([{}()])
2. ([()])
3. ([])
4. ()
5. empty-> OK

It is based on the simple fact that if we have matching pairs, then at least one is of the form ()without any pair character in between.

它基于一个简单的事实，即如果我们有匹配的对，那么至少一个是()中间没有任何对字符的形式。

Algorithm:

算法：

1. i := 0
2. Find a matching pair from i. If none is found, then the string is not valid. If one is found, let ibe the index of the first character.
3. Remove [i:i+1]from the string
4. If iis at the end of the string, and the string is not empty, it's a failure.
5. If [i-1:i]is a matching pair, i := i-1and back to 3.
6. Else, back to 1.

1. i := 0
2. 从 中找到匹配对i。如果未找到，则该字符串无效。如果找到，则i设为第一个字符的索引。
3. [i:i+1]从字符串中删除
4. 如果i是在字符串的末尾，并且字符串不为空，则失败。
5. 如果[i-1:i]是匹配对，则i := i-1返回 3。
6. 否则，回到1。

The algorithm is O(n)in complexity because:

该算法很O(n)复杂，因为：

• each iteration of the loop removes 2 characters from the string
• the step 2., which is linear, is naturally bound (icannot grow indefinitely)

• 循环的每次迭代都会从字符串中删除 2 个字符
• 第 2 步是线性的，是自然绑定的（i不能无限增长）

And it's O(1)in space because only the index is required.

它O(1)在空间中，因为只需要索引。

Of course, if you can't afford to destroy the string, then you'll have to copy it, and that's O(n)in space so no real benefit there!

当然，如果你不能破坏字符串，那么你就必须复制它，而且那是O(n)在空间中，所以那里没有真正的好处！

Unless, of course, I am deeply mistaken somewhere... and perhaps someone could use the original idea (there is a pair somewhere) to better effect.

除非，当然，我在某个地方犯了很大的错误……也许有人可以使用最初的想法（某处有一对）来获得更好的效果。

回答by puttyshell

http://www.sureinterview.com/shwqst/112007

http://www.sureinterview.com/shwqst/112007

It is natural to solve this problem with a stack.

用堆栈来解决这个问题是很自然的。

If only '(' and ')' are used, the stack is not necessary. We just need to maintain a counter for the unmatched left '('. The expression is valid if the counter is always non-negative during the match and is zero at the end.

如果仅使用 '(' 和 ')'，则不需要堆栈。我们只需要为未匹配的左 '(' 维护一个计数器。如果计数器在匹配期间始​​终为非负并且在结束时为零，则表达式有效。

In general case, although the stack is still necessary, the depth of the stack can be reduced by using a counter for unmatched braces.

在一般情况下，虽然仍然需要堆栈，但可以通过对不匹配的括号使用计数器来减少堆栈的深度。

回答by chris

I doubt you'll find a better solution, since even if you use internal functions to regexp or count occurrences, they still have a O(...) cost. I'd say your solution is the best :)

我怀疑您会找到更好的解决方案，因为即使您使用内部函数进行正则表达式或计数出现次数，它们仍然有 O(...) 成本。我会说你的解决方案是最好的:)

To optimize for space you could do some run-length encoding on your stack, but I doubt it would gain you very much, except in cases like {{{{{{{{{{}}}}}}}}}}.

为了优化空间，你可以在你的堆栈上做一些运行长度编码，但我怀疑它会给你带来很多好处，除非像{{{{{{{{{{}}}}}}}}}}.

回答by Balaji Ramamurthy

This is an working java code where I filter out the brackets from the string expression and then check the well formedness by replacing wellformed braces by nulls

这是一个有效的 java 代码，我从字符串表达式中过滤掉括号，然后通过用空值替换格式正确的大括号来检查格式是否正确

Sample input = (a+{b+c}-[d-e])+[f]-[g]FilterBrackets will output = ({}[])[][]Then I check for wellformedness.

Sample input = (a+{b+c}-[d-e])+[f]-[g]FilterBrackets 将输出 =({}[])[][]然后我检查格式是否正确。

Comments welcome.

欢迎评论。

public class ParanString {

    public static void main(String[] args) {

        String s = FilterBrackets("(a+{b+c}-[d-e])[][]");

        while ((s.length()!=0) && (s.contains("[]")||s.contains("()")||s.contains("{}")))
        {
        //System.out.println(s.length());
        //System.out.println(s);
        s = s.replace("[]", "");
        s = s.replace("()", "");
        s = s.replace("{}", "");
        }

        if(s.length()==0)
        {
            System.out.println("Well Formed");
        }
        else
        {
            System.out.println("Not Well Formed");
        }
    }

    public static String FilterBrackets(String str)
    {
        int len=str.length();
        char arr[] = str.toCharArray();
        String filter = "";
        for (int i = 0; i < len; i++)
        {
            if ((arr[i]=='(') || (arr[i]==')') || (arr[i]=='[') || (arr[i]==']') || (arr[i]=='{') || (arr[i]=='}'))
            {
                filter=filter+arr[i];
            }
        }
        return filter;
    }

}

回答by Bjartur Thorlacius

The following modification of Sbusidan's answer is O(n²) time complex but O(log n) space simple.

Sbusidan答案的以下修改是 O( n ²) 时间复杂但 O(log n) 空间简单。

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

char opposite(char bracket) {
 switch(bracket) {
  case '[':
   return ']';
  case '(':
   return ')';
 }
}

bool is_balanced(int length, char *s) {
int depth, target_depth, index;
char target_bracket;
 if(length % 2 != 0) {
  return false;
 }

 for(target_depth = length/2; target_depth > 0; target_depth--) {
  depth=0;
  for(index = 0; index < length; index++) {
   switch(s[index]) {
    case '(':
    case '[':
     depth++;
     if(depth == target_depth) target_bracket = opposite(s[index]);
     break;
    case ')':
    case ']':
     if(depth == 0) return false;
     if(depth == target_depth && s[index] != target_bracket) return false;
     depth--;
     break;
   }
  }
 }
}

void main(char* argv[]) {
  char input[] = "([)[(])]";
  char *balanced = is_balanced(strlen(input), input) ? "balanced" : "imbalanced";
  printf("%s is %s.\n", input, balanced);
}

回答by Bjartur Thorlacius

I know I'm a little late to this party; it's also my very first post on StackOverflow.

我知道我参加这个派对有点晚了；这也是我在 StackOverflow 上的第一篇文章。

But when I looked through the answers, I thought I might be able to come up with a better solution.

但是当我查看答案时，我想我可能会想出更好的解决方案。

So my solution is to use a few pointers.
It doesn't even have to use any RAM storage, as registers can be used for this.
I have not tested the code; it's written it on the fly.
You'll need to fix my typos, and debug it, but I believe you'll get the idea.

所以我的解决方案是使用一些指针。
它甚至不必使用任何 RAM 存储，因为可以为此使用寄存器。
我没有测试过代码；它是即时写的。
您需要更正我的拼写错误并进行调试，但我相信您会明白这一点。

Memory usage: Only the CPU registers in most cases.
CPU usage: It depends, but approximately twice the time it takes to read the string.
Modifies memory: No.

内存使用：大多数情况下只有 CPU 注册。
CPU 使用率：视情况而定，但大约是读取字符串所需时间的两倍。
修改内存：否。

b: string beginning, e: string end.
l: left position, r: right position.
c: char, m: match char

b：字符串b开始，e：字符串end。
L：升EFT位置中，r：- [R飞行位置。
C：ÇHAR，M：米ATCH炭

if r reaches the end of the string, we have a success.
l goes backwards from r towards b.
Whenever r meets a new start kind, set l = r.
when l reaches b, we're done with the block; jump to beginning of next block.

如果 r 到达字符串的末尾，我们就成功了。
l 从 r 向 b 倒退。
每当 r 遇到新的起始类型时，设置 l = r。
当 l 到达 b 时，我们完成了块；跳转到下一个块的开头。

const char *chk(const char *b, int len) /* option 2: remove int len */
{
  char c, m;
  const char *l, *r;

  e = &b[len];  /* option 2: remove. */
  l = b;
  r = b;
  while(r < e) /* option 2: change to while(1) */
  {
    c = *r++;
    /* option 2: if(0 == c) break; */
    if('(' == c || '{' == c || '[' == c)
    {
      l = r;
    }
    else if(')' == c || ']' == c || '}' == c)
    {
      /* find 'previous' starting brace */
      m = 0;
      while(l > b && '(' != m && '[' != m && '{' != m)
      {
        m = *--l;
      }
      /* now check if we have the correct one: */
      if(((m & 1) + 1 + m) != c)  /* cryptic: convert starting kind to ending kind and match with c */
      {
        return(r - 1);  /* point to error */
      }
      if(l <= b) /* did we reach the beginning of this block ? */
      {
        b = r; /* set new beginning to 'head' */
        l = b; /* obsolete: make left is in range. */
      }
    }
  }
  m = 0;
  while(l > b && '(' != m && '[' != m && '{' != m)
  {
    m = *--l;
  }
  return(m ? l : NULL); /* NULL-pointer for OK */
}

After thinking about this approach for a while, I realized that it will not work as it is right now.
The problem will be that if you have "[()()]", it'll fail when reaching the ']'.
But instead of deleting the proposed solution, I'll leave it here, as it's actually not impossible to make it work, it does require some modification, though.

在考虑了一段时间后，我意识到它不会像现在这样工作。
问题是，如果你有“[()()]”，它会在到达 ']' 时失败。
但是，我不会删除建议的解决方案，而是将其保留在这里，因为实际上并非不可能使其工作，但它确实需要进行一些修改。

回答by dmckee --- ex-moderator kitten

If you can overwrite the input string (not reasonable in the use cases I envision, but what the heck...) you can do it in constant space, though I believe the time requirement goes up to O(n²).

如果您可以覆盖输入字符串（在我设想的用例中不合理，但到底是什么......），您可以在恒定空间中进行，尽管我相信时间要求高达O(n ²)。

Like this:

像这样：

string s = input
char c = null
int i=0
do
  if s[i] isAOpenChar()
    c = s[i]
  else if
    c = isACloseChar()
      if closeMatchesOpen(s[i],c)
         erase s[i]
         while s[--i] != c ;
         erase s[i]
         c == null
         i = 0;      // Not optimal! It would be better to back up until you find an opening character
      else 
         return fail
  end if
while (s[++i] != EOS)
if c==null
  return pass
else
  return fail

The essence of this is to use the early part of the input as the stack.

这样做的本质是将输入的早期部分用作堆栈。