#c #algorithm #stack
#c #алгоритм #стек
Вопрос:
у меня есть строка (char * ch) со скобками, и я должен:
1) проверьте, правильно ли написана строка и хорошо ли сбалансирована, например: «(())» правильно написано и хорошо сбалансировано, в то время как «)()» не является ни хорошо написанным, ни хорошо сбалансированным
2) верните позицию первой круглой скобки, которая отклоняется от этого правила, если строка неправильно написана и не сбалансирована.
что касается первого вопроса, то все в порядке. мой код выглядит следующим образом:
int WBalanced(char *ch)
{
stack p; int i;
for (i=0; i<strlen(ch);i )
{
if(ch[i] == '(')
{
addStack(P, ch[i]);
else if(ch[i] == ')')
{
if(stackEmpty(P) == 0)
unstack(P);
else
return (0);
}
}
}
if(stackEmpty(P)==1)
return (0);
else
return (1);
}
но что касается второго вопроса, я не очень хорошо понимаю вопрос. если моя строка «(()», соответствует ли позиция позиции второй круглой скобки? и если моя строка «(()(» какова позиция отклоненной круглой скобки?
спасибо за помощь
Комментарии:
1. Для
"(()("это тот же ответ, что и вопрос, касается нахождения положения первой круглой скобки, которое отклоняется от правила.2. @ChetanRanpariya какова позиция отклоненной круглой скобки, пожалуйста, если моя строка «(()(» спасибо
3. Если у вас есть сомнения относительно смысла задания, вам следует спросить своего профессора или TA. Мы тоже не знаем, что они означают.
4. Позиция первой отклоняющейся круглой скобки равна 1 для
"(()("5. @ChetanRanpariya я думаю, что это 4, последняя скобка!
Ответ №1:
Несомненно, есть много способов подойти к этому, но из-за отсутствия дополнительных требований я бы считал уровни вложенности, просматривая слева направо. Если количество становится меньше нуля, укажите на этот символ в качестве причины.
Если строка заканчивается, а уровень не равен нулю, укажите на это место (вероятно) как на неполное выражение.
Комментарии:
1. Допустим, строка «((asd)asd». Нарушающим
(является второй символ. Как он узнает об этом, если сделает то, что вы предлагаете?2. @DavidSchwartz: Я бы сказал, что в этом случае нарушающим
(является первый символ, поскольку именно он не соответствует. Второму символу соответствует 6-й…3. @DavidSchwartz да, для «((asd) asd» это вторая скобка, но как это реализовать?
4. В конце, если счетчик отличен от нуля, верните (индекс) первую круглую скобку в строке, поскольку это первая скобка, которая является несбалансированной (после этого может быть больше несбалансированных, но первая скобка является несбалансированной.
5. @ChrisDodd какой счет, пожалуйста? «если счетчик отличен от нуля»
Ответ №2:
Используя Stack в качестве реализации для проверки баланса скобок, решение должно быть :
Во-первых, предположим, что индексация начинается с 0. Stack.top = -1 (указывает, что в стек не вставлена скобка). Мы запускаем наш алгоритм от 1-й левой круглой скобки (индекс 0) до конечной круглой скобки. fault_index = -1 (используется для вывода, какая скобка ошибочна)
-
Если встречается ‘(‘ -> вставить в стек. Stack.top = 1 и fault_index = индекс этой круглой скобки в данной строке (fault_index должен быть установлен только тогда, когда стек пуст, прежде чем вставлять эту круглую скобку)
-
Если встречается ‘)’ -> удалить ‘(‘ из стека. Stack.top -= 1.
Мы останавливаемся при возникновении любого из этих условий и должны предпринять соответствующие действия :
-
Когда строка пуста :
a. Если стек пуст -> Были сбалансированы строковые скобки.
b. Если стек не пуст -> Ошибка находится в fault_index
-
Когда вы сталкиваетесь с дополнительным ‘)’, т. е. когда стек пуст и в нем есть эта скобка, этот индекс является fault_index .
Комментарии:
1. @Constellation, Для вашего заданного ввода «(()» вот как будет выполняться код: Изначально столкнулись Stack.top = -1 и fault_index = -1 ( -> Stack.top = 0 и поскольку стек был пуст, fault_index = 0 (индекс символа в строке. ) . Push ( для стека другого ( -> Stack.top = 1 , fault_Index не обновляется, поскольку стек не пустой. Переместить в стек. Обнаружено) -> Stack.top уменьшено с 1 до 0. fault_index по-прежнему равен 0 . Поскольку строка пуста -> а стек не пуст. Ошибка при fault_index = 0 .
Ответ №3:
спасибо за ваши ответы. использование counter — неплохая идея, но она может быть функциональной в этом случае «(()» и не функциональной в этом случае «((()(«… 🙁