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

Question

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

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

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

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

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

Answer 1

Со ссылкой на отличный ответ от Матье М. , вот реализация на 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);
}

По сути, все, что он делает, это удаляет пары скобок, пока не останется ни одного удаляемого элемента; если что-то осталось, скобки не имеют правильной формы.

Примеры правильных скобок:

()[]
{()[]}

Пример неправильных скобок:

([)]
{()[}]

Answer 2

На самом деле, существует детерминированный алгоритм лог-пространства из-за Ричи и Спрингстила: http://dx.doi.org/10.1016/S0019-9958(72)90205-7 ( paywalled, извините не в сети) Поскольку нам нужны лог-биты для индексации строки, это оптимально для пространства.

---

Если вы готовы принять одностороннюю ошибку, есть алгоритм, который использует n полилог (n) времени и полилог (n) пространства: http://www.eccc.uni -trier.de / report / 2009/119 /

Answer 3

Если вход только для чтения, я не думаю, что мы можем сделать O (1) пробел. Хорошо известен тот факт, что любой разрешимый в O (1) язык является регулярным (т.е. записываемым как регулярное выражение). Ваш набор строк не является обычным языком.

Конечно, речь идет о машине Тьюринга. Я ожидаю, что это будет верно и для машин с фиксированным словом RAM.

Answer 4

Редактировать: Хотя этот алгоритм прост, он фактически равен O (n ^ 2) с точки зрения сравнения символов. Чтобы продемонстрировать это, можно просто сгенерировать строку как '(' * n + ')' * n.

У меня есть простая, хотя, может быть, и ошибочная идея, что я подчинюсь вашей критике.

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

В противном случае алгоритм работает с простым индексом в текущей строке.

Идея состоит в том, чтобы удалять пары одну за другой:

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

Он основан на простом факте, что если у нас есть совпадающие пары, то по крайней мере одна имеет форму () без каких-либо парных символов между ними.

Алгоритм:

1. i := 0
2. Найдите подходящую пару из i. Если ничего не найдено, строка недопустима. Если он найден, пусть i будет индексом первого символа.
3. Удалить [i:i+1] из строки
4. Если i находится в конце строки, и строка не пуста, это ошибка.
5. Если [i-1:i] совпадающая пара, i := i-1 и обратно до 3.
6. Остальное, назад к 1.

Алгоритм сложности O(n), потому что:

• каждая итерация цикла удаляет 2 символа из строки
• шаг 2., который является линейным, естественно связан (i не может расти бесконечно)

И это O(1) в пространстве, потому что требуется только индекс.

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

Если, конечно, я где-то глубоко ошибаюсь ... и, возможно, кто-то может использовать оригинальную идею (где-то есть пара) для лучшего эффекта.

Answer 5

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

Естественно решить эту проблему с помощью стека.

Если используются только '(' и ')', стек не требуется. Нам просто нужно сохранить счетчик для несопоставленного левого значения '('. Выражение действительно, если счетчик всегда неотрицателен во время матча и равен нулю в конце.

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

Answer 6

Следующая модификация ответа Сбусидана : 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);
}

Answer 7

Это рабочий java-код, в котором я отфильтровываю скобки из строкового выражения, а затем проверяю правильность формы, заменяя хорошо сформированные скобки нулями

Образец 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;
    }

}

Answer 8

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

Чтобы оптимизировать пространство, вы можете выполнить кодировку длины строки в вашем стеке, но я сомневаюсь, что это принесет вам большую пользу, за исключением случаев, таких как {{{{{{{{{{}}}}}}}}}}.

Answer 9

Если вы можете перезаписать входную строку (не разумно в тех случаях, которые я предполагаю, но какого черта ...), вы можете сделать это в постоянном пространстве, хотя я считаю, что требование времени увеличивается до O ( п ² ) .

Как это:

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

Суть этого состоит в том, чтобы использовать раннюю часть ввода в качестве стека.

Answer 10

Я знаю, что немного опоздал на эту вечеринку; это также мой самый первый пост в StackOverflow.

Но когда я просмотрел ответы, я подумал, что смогу найти лучшее решение.

Так что мое решение - использовать несколько указателей.
Ему даже не нужно использовать какое-либо ОЗУ, поскольку для этого могут использоваться регистры.
Я не проверял код; это написано на лету.
Вам нужно будет исправить мои опечатки и отладить их, но я верю, что вы поймете эту идею.

Использование памяти: в большинстве случаев регистрируется только процессор.
Загрузка ЦП: зависит, но примерно вдвое быстрее, чем чтение строки.
Модифицирует память: №

b: строка b начало, e: строка e nd.
l: l в верхнем положении, r: r в вертикальном положении.
с: с хар, м: м атч чар

если r достигнет конца строки, мы добьемся успеха.
Я идет назад от г к б.
Всякий раз, когда r встречает новый стартовый тип, установите l = r.
когда я достигну 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 */
}

Подумав некоторое время об этом подходе, я понял, что он не будет работать так, как сейчас.
Проблема будет в том, что если у вас есть «[() ()]», произойдет сбой при достижении «]».
Но вместо того, чтобы удалить предложенное решение, я оставлю его здесь, так как на самом деле это не невозможно заставить его работать, хотя оно требует некоторой модификации.