Как найти действительность строки скобок, фигурных скобок и квадратных скобок?

Question

Я недавно столкнулся с этой интересной проблемой. Вам дана строка, содержащая только символы '(', ')', '{', '}', '[' и ']', например, "[{()}]", вам нужно написать функцию, которая будет проверять правильность для такой входной строки функция может быть такой:
bool isValid(char* s);
эти скобки должны закрываться в правильном порядке, например, "()" и "()[]{}" все действительны, но "(]", "([)]" и "{{{{" нет!

Я предложил следующее решение для сложности пространства O (n) по времени и O (n), которое прекрасно работает:

1. Ведение стека символов.
2. Всякий раз, когда вы обнаружите открывающие скобки '(', '{' ИЛИ '[' опустите их в стек.
3. Всякий раз, когда вы найдете закрывающие скобки ')', '}' ИЛИ ']', проверьте, соответствует ли вершина стека открывающей скобке, если да, то вытолкните стек, иначе разорвите цикл и верните false.
4. Повторите шаги 2 - 3 до конца строки.

Это работает, но можем ли мы оптимизировать его для пробела, может быть постоянный дополнительный пробел, я понимаю, что временная сложность не может быть меньше O (n), поскольку мы должны смотреть на каждый символ.

Итак, мой вопрос: можем ли мы решить эту проблему в пространстве O (1)?

Answer 1

Использование программирования 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();

Answer 2

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

Answer 3

Вы могли бы предоставить значение и проверить, является ли оно действительным, оно напечатало бы ДА, иначе это напечатало бы НЕТ

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();

        }

Answer 4

Это моё решение проблемы. 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;
}

Answer 5

Я думаю, что вы можете реализовать алгоритм O (n). Просто вы должны инициализировать переменную счетчика для каждого типа: фигурные, квадратные и нормальные скобки. После этого вы должны выполнить итерацию строки и увеличить счетчик ответов, если скобка открыта, иначе уменьшить ее. Если счетчик отрицательный, верните false. После того, как я думаю, что вы можете реализовать алгоритм O (n). Просто вы должны инициализировать переменную счетчика для каждого типа: фигурные, квадратные и нормальные скобки. После этого вы должны выполнить итерацию строки и увеличить счетчик ответов, если скобка открыта, иначе уменьшить ее. Если счетчик отрицательный, верните false. После того, как вы посчитаете все скобки, вы должны проверить, все ли счетчики равны нулю. В этом случае строка действительна, и вы должны вернуть true.

Answer 6

Вместо помещения фигурных скобок в стек, вы можете использовать два указателя для проверки символов строки. один начинается с начала строки, а другой начинается с конца строки. что-то вроде

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

Обратите внимание, что некоторые угловые случаи не обрабатываются.

Answer 7

/**
 *
 * @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;
}

}