算法-如何找到括号,大括号和方括号的字符串的有效性?

我最近遇到了这个有趣的问题。 您将得到一个仅包含字符')''}'']''}''['']'的字符串,例如"[{()}]",您需要编写一个函数来检查这种输入字符串的有效性,该函数可能是这样的:
bool isValid(char* s);
这些括号必须以正确的顺序闭合,例如"()""()[]{}"均有效,但"(]""([)]""{{{{"无效!

我提出了以下O(n)时间和O(n)空间复杂度解决方案,该方法运行良好:

  1. 保持一堆字符。
  2. 每当您找到开口撑杆')''}'']'将其推入堆栈时。
  3. 每当找到闭合括号')''}''}'时,请检查堆栈顶部是否对应于打开的括号,如果是,则弹出堆栈,否则中断循环并返回false。
  4. 重复步骤2-3,直到字符串结尾。

这行得通,但是我们可以针对空间进行优化吗?可能是恒定的额外空间。我理解时间复杂度不能小于O(n),因为我们必须查看每个字符。

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

Rajendra Uppal asked 2020-06-27T02:25:52Z
17个解决方案
12 votes

参考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);
}

本质上,它所做的就是删除成对的括号,直到没有剩下要删除的为止。 如果还有什么遗漏,则括号的格式不正确。

格式正确的括号示例:

()[]
{()[]}

括号格式错误的示例:

([)]
{()[}]
Contango answered 2020-06-27T02:26:41Z
11 votes

实际上,由于Ritchie和Springsteel,有一种确定性的日志空间算法:[http://dx.doi.org/10.1016/S0019-9958(72)90205-7](付费,抱歉,不在网上)。 由于我们需要日志位来索引字符串,因此这是空间最佳的。


如果您愿意接受单方面的错误,那么有一种算法可以使用n个polylog(n)时间和polylog(n)空间:[http://www.eccc.uni-trier.de/report/2009/ 119 /]

user287792 answered 2020-06-27T02:26:06Z
6 votes

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

当然,这是关于图灵机的。 我希望对于固定字RAM机器也是如此。

answered 2020-06-27T02:27:06Z
3 votes

编辑:尽管很简单,但从字符比较的角度来看,该算法实际上是O(n ^ 2)。 为了说明这一点,可以简单地生成一个字符串为O(n)

我有一个简单的,但也许是错误的想法,我会屈服于您的批评。

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

否则,该算法将在当前字符串中使用简单索引。

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

  1. O(n)
  2. O(n)
  3. O(n)
  4. O(n)
  5. O(n) -> i := i-1

这是基于一个简单的事实,如果我们有匹配的对,则至少有一个形式为O(n),中间没有任何对字符。

算法:

  1. O(n)
  2. O(n)查找匹配对。如果找不到,则该字符串无效。 如果找到一个,则使i := i-1为第一个字符的索引。
  3. 从字符串中删除O(n)
  4. 如果O(n)位于字符串的末尾,并且字符串不为空,则失败。
  5. 如果O(n)是匹配对,则i := i-1并返回3。
  6. 否则,返回1。

该算法的复杂度为O(n),因为:

  • 循环的每次迭代都会从字符串中删除2个字符
  • 自然地绑定了线性的步骤2.(O(n)不能无限增长)

空间为O(n),因为仅需要索引。

当然,如果您无力销毁该字符串,则必须将其复制,这就是O(n)在太空中的存在,因此那里没有真正的好处!

除非,当然,除非我在某个地方误会了……也许有人可以使用最初的想法(某处有一对)来达到更好的效果。

Matthieu M. answered 2020-06-27T02:31:55Z
2 votes

我怀疑您会找到更好的解决方案,因为即使您使用内部函数对表达式进行正则表达式计数或计数,它们仍然会产生O(...)开销。 我想说您的解决方案是最好的:)

为了优化空间,您可以在堆栈上进行游程编码,但是我怀疑它会为您带来很多好处,除非像{{{{{{{{{{}}}}}}}}}}这样。

chris answered 2020-06-27T02:32:21Z
2 votes

[HTTP://呜呜呜.sure interview.com/是完全是他/112007]

用堆栈解决此问题是很自然的。

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

通常情况下,尽管仍然需要堆叠,但是可以通过使用不匹配支架的计数器来减小堆叠的深度。

puttyshell answered 2020-06-27T02:32:54Z
2 votes

这是一个有效的Java代码,在该代码中,我从字符串表达式中过滤出括号,然后通过将格式正确的括号替换为null来检查格式是否正确

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

欢迎发表评论。

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;
    }

}
Balaji Ramamurthy answered 2020-06-27T02:33:23Z
2 votes

Sbusidan答案的以下修改是O(n2)时间复杂,但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);
}
Bjartur Thorlacius answered 2020-06-27T02:33:45Z
1 votes

如果您可以覆盖输入字符串(在我设想的用例中不合理,但是到底是什么...),则可以在恒定空间中进行输入,尽管我认为时间要求会达到O(n2)。

像这样:

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

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

dmckee answered 2020-06-27T02:34:14Z
1 votes

我知道我参加这个聚会有点晚了。 这也是我关于StackOverflow的第一篇文章。

但是,当我浏览答案时,我认为我可能可以提出一个更好的解决方案。

所以我的解决方案是使用一些指针。
它甚至不必使用任何RAM存储,因为可以使用寄存器。
我没有测试代码; 它是即时写的。
您需要修复我的错字并进行调试,但是我相信您会明白的。

内存使用情况:大多数情况下,仅CPU注册。
CPU使用率:取决于使用情况,但大约是读取字符串所需时间的两倍。
修改内存:否。

b:字符串开头,e:字符串结尾。
l:左侧位置,r:右侧位置。
c:字符,m:匹配字符

如果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 */
}

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

answered 2020-06-27T02:35:52Z
0 votes
/**
 *
 * @author madhusudan
 */
public class Main {

/**
 * @param args the command line arguments
 */
public static void main(String[] args) {
    new Main().validateBraces("()()()()(((((())))))()()()()()()()()");
    // TODO code application logic here
}

/**
 * @Use this method to validate braces
 */
public void validateBraces(String teststr)
{
    StringBuffer teststr1=new StringBuffer(teststr);
    int ind=-1;
    for(int i=0;i<teststr1.length();)
    {

    if(teststr1.length()<1)
    break;
    char ch=teststr1.charAt(0);
    if(isClose(ch))
    break;
    else if(isOpen(ch))
    {
        ind=teststr1.indexOf(")", i);
        if(ind==-1)
        break;
        teststr1=teststr1.deleteCharAt(ind).deleteCharAt(i);
    }
    else if(isClose(ch))
    {
        teststr1=deleteOpenBraces(teststr1,0,i);
    }
    }
    if(teststr1.length()>0)
    {
        System.out.println("Invalid");

    }else
    {
        System.out.println("Valid");
    }
}
public boolean  isOpen(char ch)
{
    if("(".equals(Character.toString(ch)))
    {
        return true;
    }else
        return false;
}
public boolean  isClose(char ch)
{
    if(")".equals(Character.toString(ch)))
    {
        return true;
    }else
        return false;
}
public StringBuffer deleteOpenBraces(StringBuffer str,int start,int end)
{
    char ar[]=str.toString().toCharArray();
    for(int i=start;i<end;i++)
    {
        if("(".equals(ar[i]))
         str=str.deleteCharAt(i).deleteCharAt(end); 
        break;
    }
    return str;
}

}
Madhusudan Singh answered 2020-06-27T02:36:08Z
0 votes

您可以使用两个指针来检查字符串的字符,而不是将花括号放入堆栈中。 一个从字符串的开头开始,另一个从字符串的结尾开始。 就像是

bool isValid(char* s) {
    start = find_first_brace(s);
    end = find_last_brace(s);
    while (start <= end) {
        if (!IsPair(start,end)) return false;
        // move the pointer forward until reach a brace
        start = find_next_brace(start);
        // move the pointer backward until reach a brace
        end = find_prev_brace(end);
    }
    return true;
}

请注意,有一些未处理的特殊情况。

Jiangbo answered 2020-06-27T02:36:32Z
0 votes

我认为您可以实现O(n)算法。 只需为每种类型初始化一个计数器变量:大括号,方括号和普通括号。 之后,您应该对字符串进行迭代,如果支架被打开,则应增加对应于内核的计数器,否则应减小字符串。 如果计数器为负,则返回false。 之后,我认为您可以实现O(n)算法。 只需为每种类型初始化一个计数器变量:大括号,方括号和普通括号。 之后,您应该对字符串进行迭代,如果支架被打开,则应增加对应于内核的计数器,否则应减小字符串。 如果计数器为负,则返回false。 计算完所有括号后,应检查所有计数器是否为零。 在这种情况下,字符串是有效的,您应该返回true。

Svetlin Ralchev answered 2020-06-27T02:36:54Z
0 votes

您可以提供该值并检查其是否为有效值,否则将打印YES,否则将打印NO

static void Main(string[] args)
        {
            string value = "(((([{[(}]}]))))";
            List<string> jj = new List<string>();
            if (!(value.Length % 2 == 0))
            {
                Console.WriteLine("NO");
            }
            else
            {
                bool isValid = true;


                List<string> items = new List<string>();

                for (int i = 0; i < value.Length; i++)
                {
                    string item = value.Substring(i, 1);
                    if (item == "(" || item == "{" || item == "[")
                    {
                        items.Add(item);
                    }
                    else
                    {
                        string openItem = items[items.Count - 1];
                        if (((item == ")" && openItem == "(")) || (item == "}" && openItem == "{") || (item == "]" && openItem == "["))
                        {
                            items.RemoveAt(items.Count - 1);

                        }
                        else
                        {
                            isValid = false;
                            break;
                        }



                    }
                }


                if (isValid)
                {
                    Console.WriteLine("Yes");
                }
                else
                {
                    Console.WriteLine("NO");
                }
            }
            Console.ReadKey();

        }
Maxymus answered 2020-06-27T02:37:16Z
0 votes

var verify = function(text) 
{
  var symbolsArray = ['[]', '()', '<>'];
  var symbolReg = function(n) 
  {
    var reg = [];
    for (var i = 0; i < symbolsArray.length; i++) {
      reg.push('\\' + symbolsArray[i][n]);
    }
    return new RegExp('(' + reg.join('|') + ')','g');
  };
  // openReg matches '(', '[' and '<' and return true or false
  var openReg = symbolReg(0);
  // closeReg matches ')', ']' and '>' and return true or false
  var closeReg = symbolReg(1);
  // nestTest matches openSymbol+anyChar+closeSymbol
  // and returns an obj with the match str and it's start index
  var nestTest = function(symbols, text) 
  {
    var open = symbols[0]
      , close = symbols[1]
      , reg = new RegExp('(\\' + open + ')([\\s\\S])*(\\' + close + ')','g')
      , test = reg.exec(text);
    if (test) return {
      start: test.index,
      str: test[0]
    };
    else return false;
  };
  var recursiveCheck = function(text) 
  {
    var i, nestTests = [], test, symbols;
    // nestTest with each symbol
    for (i = 0; i < symbolsArray.length; i++) 
    {
      symbols = symbolsArray[i];
      test = nestTest(symbols, text);
      if (test) nestTests.push(test);
    }
    // sort tests by start index
    nestTests.sort(function(a, b) 
    {
      return a.start - b.start;
    });
    if (nestTests.length) 
    {
      // build nest data: calculate match end index
      for (i = 0; i < nestTests.length; i++) 
      {
        test = nestTests[i];
        var end = test.start + ( (test.str) ? test.str.length : 0 );
        nestTests[i].end = end;
        var last = (nestTests[i + 1]) ? nestTests[i + 1].index : text.length;
        nestTests[i].pos = text.substring(end, last);
      }
      for (i = 0; i < nestTests.length; i++) 
      {
        test = nestTests[i];
        // recursive checks  what's after the nest 
        if (test.pos.length && !recursiveCheck(test.pos)) return false;
        // recursive checks  what's in the nest 
        if (test.str.length) {
          test.str = test.str.substring(1, test.str.length - 1);
          return recursiveCheck(test.str);
        } else return true;
      }
    } else {
      // if no nests then check for orphan symbols
      var closeTest = closeReg.test(text);
      var openTest = openReg.test(text);
      return !(closeTest || openTest);
    }
  };
  return recursiveCheck(text);
};

rafaelcastrocouto answered 2020-06-27T02:37:36Z
0 votes

使用c#OOPS编程...小型而简单的解决方案

Console.WriteLine("Enter the string");
            string str = Console.ReadLine();
            int length = str.Length;
            if (length % 2 == 0)
            {
                while (length > 0 && str.Length > 0)
                {
                    for (int i = 0; i < str.Length; i++)
                    {
                        if (i + 1 < str.Length)
                        {
                            switch (str[i])
                            {
                                case '{':
                                    if (str[i + 1] == '}')
                                        str = str.Remove(i, 2);
                                    break;
                                case '(':
                                    if (str[i + 1] == ')')
                                        str = str.Remove(i, 2);
                                    break;
                                case '[':
                                    if (str[i + 1] == ']')
                                        str = str.Remove(i, 2);
                                    break;
                            }
                        }
                    }
                    length--;
                }
                if(str.Length > 0)
                    Console.WriteLine("Invalid input");
                else
                    Console.WriteLine("Valid input");
            }
            else
                Console.WriteLine("Invalid input");
            Console.ReadKey();
Jaydeep Shil answered 2020-06-27T02:37:56Z
0 votes

这是我解决问题的方法。O(n)是时间的复杂性,而没有空间的复杂性。用C语言编写的代码。

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

bool checkBraket(char *s)
{
    int curly = 0, rounded = 0, squre = 0;
    int i = 0;
    char ch = s[0];
    while (ch != '\0')
    {
        if (ch == '{') curly++;
        if (ch == '}') {
            if (curly == 0) {
                return false;
            } else {
                curly--; }
        }
        if (ch == '[') squre++;
        if (ch == ']') {
            if (squre == 0) {
                return false;
            } else {
                squre--;
            }
        }
        if (ch == '(') rounded++;
        if (ch == ')') {
            if (rounded == 0) {
                return false;
            } else {
                rounded--;
            }
        }
        i++;
        ch = s[i];
    }
    if (curly == 0 && rounded == 0 && squre == 0){
        return true;
    }
    else {
        return false;
    }
}
void main()
{
    char mystring[] = "{{{{{[(())}}]}}}";
    int answer = checkBraket(mystring);
    printf("my answer is %d\n", answer);
    return;
}
SBusidan answered 2020-06-27T02:38:17Z
translate from https://stackoverflow.com:/questions/2509358/how-to-find-validity-of-a-string-of-parentheses-curly-brackets-and-square-brack