Недавно я связался с этой интересной проблемой. Вам предоставляется строка, содержащая только символы '(', ')', '{', '}', '[' и ']', например, "[{()}]", вам нужно написать функцию, которая проверяет правильность такой входной строки, функция может быть такой:
bool isValid(char* s);
эти скобки должны быть закрыты в правильном порядке, например "()" и "()[]{}" являются действительными, но "(]", "([)]" и "{{{{" не являются!
Я вышел со следующим решением O (n) и O (n) пространственной сложности, которое отлично работает:
'(', '{' ИЛИ '[', надавите на стек.')', '}' ИЛИ ']', проверьте, соответствует ли верхняя часть стека соответствующей открывающей скобке, если да, затем поместите стек, иначе сломайте цикл и верните false.Это работает, но мы можем оптимизировать его для пространства, может быть постоянным дополнительным пространством, я понимаю, что временная сложность не может быть меньше O (n), поскольку мы должны смотреть на каждый символ.
Итак, мой вопрос: мы можем решить эту проблему в O (1) пространстве?
На самом деле существует детерминированный алгоритм лог-пространства из-за Ritchie и Springsteel: http://dx.doi.org/10.1016/S0019-9958(72)90205-7 ( paywalled, извините не в сети). Поскольку нам нужны лог-биты для индексации строки, это оптимально для пространства.
Если вы согласны принять одностороннюю ошибку, тогда существует алгоритм, в котором используется n полилог (n) время и полилог (n): http://www.eccc.uni-trier.de/report/2009/119/
Что касается превосходного ответа от Matthieu M., вот реализация на С#, которая кажется прекрасно работающей.
/// <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);
}
По существу, все, что он делает, это удалить пары скобок, пока их не осталось удалить; если что-то осталось, скобки не сформированы.
Примеры хорошо сформированных скобок:
()[]
{()[]}
Пример неправильных скобок:
([)]
{()[}]
Если вход доступен только для чтения, я не думаю, что мы можем сделать O (1) пространство. Хорошо известно, что любой разрешимый язык пространства O (1) является регулярным (записывается как регулярное выражение). Набор строк, который у вас есть, не является обычным языком.
Конечно, речь идет о машине Тьюринга. Я бы ожидал, что это будет верно и для аппаратов с фиксированной памятью.
Изменить: Хотя это просто, этот алгоритм является фактически O (n ^ 2) в терминах сопоставлений символов. Чтобы продемонстрировать это, можно просто сгенерировать строку как '(' * n + ')' * n.
У меня есть простая, хотя, возможно, ошибочная идея, что я буду подчиняться вашей критике.
Это разрушительный алгоритм, а это значит, что если вам понадобится строка, это не поможет (так как вам нужно будет ее скопировать).
В противном случае алгоритм работает с простым индексом в текущей строке.
Идея состоит в том, чтобы удалить пары один за другим:
([{}()])([()])([])()empty → OKОн основан на простом факте, что если у нас есть соответствующие пары, то по крайней мере один имеет вид () без какого-либо пара-символа между ними.
Алгоритм:
i := 0i. Если ни один не найден, строка недействительна. Если он найден, пусть i - индекс первого символа.[i:i+1] из строкиi находится в конце строки, а строка не пуста, это сбой.[i-1:i] - совпадающая пара, i := i-1 и обратно в 3.Алгоритм O(n) по сложности, потому что:
i не может расти бесконечно)И это O(1) в пространстве, потому что требуется только индекс.
Конечно, если вы не можете позволить себе уничтожить строку, вам придется ее скопировать, а это O(n) в пространстве, поэтому никакой реальной выгоды там нет!
Если, конечно, я не ошибаюсь где-то... и, возможно, кто-то мог бы использовать оригинальную идею (есть где-то пара), чтобы улучшить эффект.
Я сомневаюсь, что вы найдете лучшее решение, так как даже если вы используете внутренние функции для регулярного выражения или подсчета вхождений, они по-прежнему имеют стоимость O (...). Я бы сказал, что ваше решение лучше всего:)
Чтобы оптимизировать пространство, вы можете сделать некоторую кодировку в вашей стеке, но я сомневаюсь, что она вам очень понравится, за исключением случаев, когда {{{{{{{{{{}}}}}}}}}}.
http://www.sureinterview.com/shwqst/112007
Естественно решить эту проблему со стеком.
Если используются только '(' и ')', стек не нужен. Нам просто нужно поддерживать счетчик для непревзойденного слева '('. Выражение действительно, если счетчик всегда неотрицателен во время матча и равен нулю в конце.
В общем случае, хотя стек по-прежнему необходим, глубина стека может быть уменьшена с помощью счетчика для непревзойденных фигурных скобок.
Это рабочий код 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;
}
}
Следующая модификация ответа Sbusidan - это комплекс времени O (n 2), но 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);
}
Если вы можете перезаписать входную строку (не разумную в случаях использования, которую я себе представляю, но что за черт...), вы можете сделать это в постоянном пространстве, хотя я считаю, что потребность в времени идет до O (n 2).
Вот так:
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
Суть этого заключается в том, чтобы использовать раннюю часть ввода как стек.
Я знаю, что немного опаздываю на эту вечеринку; это также мой самый первый пост в StackOverflow.
Но когда я просмотрел ответы, я подумал, что смогу придумать лучшее решение.
Итак, мое решение состоит в том, чтобы использовать несколько указателей.
Он даже не должен использовать память RAM, так как для этого могут использоваться регистры.
Я не тестировал код; он написал это на лету.
Вам нужно будет исправить мои опечатки и отладить его, но я верю, что вы получите эту идею.
Использование памяти: в большинстве случаев регистрируется только центральный процессор.
Использование ЦП: это зависит, но примерно в два раза больше времени, затрачиваемого на чтение строки.
Изменяет память: Нет.
b: string b eginning, e: string e nd.
l: l позиция eft, r: r позиция.
c: c har, m: m atch char
если 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 */
}
Подумав об этом подходе некоторое время, я понял, что он не будет работать так, как сейчас.
Проблема будет в том, что если у вас есть "[()()]", это не удастся при достижении "]".
Но вместо того, чтобы удалить предлагаемое решение, я оставлю его здесь, так как на самом деле не невозможно заставить его работать, но он требует некоторой модификации.
/**
*
* @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;
}
}
Вместо того, чтобы вставлять фигурные скобки в стек, вы можете использовать два указателя для проверки символов строки. один начинается с начала строки, а другой начинается с конца строки. что-то вроде
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;
}
Обратите внимание, что некоторые угловые случаи не обрабатываются.
Я думаю, что вы можете реализовать алгоритм O (n). Просто вы должны инициализировать переменную счетчика для каждого типа: фигурные, квадратные и обычные скобки. После этого вы должны итерации строки и должны увеличить счетчик, если скобка открыта, в противном случае, чтобы уменьшить ее. Если счетчик отрицательный, верните false. AfterI думаю, что вы можете реализовать алгоритм O (n). Просто вы должны инициализировать переменную счетчика для каждого типа: фигурные, квадратные и обычные скобки. После этого вы должны итерации строки и должны увеличить счетчик, если скобка открыта, в противном случае, чтобы уменьшить ее. Если счетчик отрицательный, верните false. После того, как вы подсчитаете все скобки, вы должны проверить, равны ли все счетчики. В этом случае строка верна и вы должны вернуть true.
Это мое решение проблемы. 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;
}
Вы можете указать значение и проверить, является ли его действительным, оно будет печатать ДА, иначе оно будет печатать 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();
}
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 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 after the nest
if (test.pos.length && !recursiveCheck(test.pos)) return false;
// recursive checks what 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);
};Использование программирования С# 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();