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

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

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

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

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

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

1. ([{} ()])
2. ([()])
3. ([])
4. ()
5. пусто -> ОК

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

Алгоритм:

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) в космосе, так что никакой реальной пользы от этого нет!

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

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

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

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

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

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

Вот так:

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

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