Задача: Скобки (определение действительности скобок)

  • Автор темы Plazma
  • Дата начала
P

Plazma

#1
1)Нужно написать прогу, которая выясняет действительность скобок. Если есть открывающая "( " и закрывающая")" скобка, то эти скобки действительные.Прога вывести "YES" если введенные скобки действительные,если иначе "No" Пример:
Ввод
()(())
Вывод
YES

Ввод
)(
Вывод
NO

2)Нужно написать прогу, которая выясняет действительность скобок. Если есть открывающая "( " и закрывающая")" скобка, то эти скобки действительные.Отличие от первой задачи скобки в этой задаче должны содержать внутри себя и открывающую закрыващую скобку.На примере все понятно будет. Прога вывести "YES" если введенные скобки действительные,если иначе "No"Сначало вводится количество скобок, а потом скобки. Может ввести 3 типы скобок "[]", "{}" и "()"
Ввод
6
([())]
Вывод
No

Ввод
10
({}{{}})[]
Вывод
Yes

Ввод
10
[()]([]{})
Вывод
No
 

DarkKnight

Well-known member
01.08.2010
653
0
#2
Идеи по написанию какие-нибудь есть???
может код начали писать уже???
 

DarkKnight

Well-known member
01.08.2010
653
0
#4
Ну первое что приходит на ум это "считаешь вхождения":
при открытие скобки +1*(2^(0+индекс_открытия))
при закрытии скобки -1*(2^0+индекс_открытия)
где индекс открытия у тебя идет от 0...
Причем т.к. у тебя типов скобок несколько, то считаешь для каждой отдельно... (но индекс входимости всегда один, при открытие любой скобки мы его инкрементируем ++, при закрытии дикрементируем --)

Тоесть :
например [ ( ] )
Получается
"[]" 1*2^0 - 1*2^1 = 1-2 = -1
"()" 1*2^1 - 1*2^0 = 2- 1 = 1
Если показатели не равны нулю то скобки не действитель
пример 2 [()]
"[]" 1*2^0 - 1*2^0 = 0
"()" 1*2^1 - 1*2^1 = 0
А тут все верно...
Добавлено: Ну это самый оптимальный алгоритм... Можно длинее но проще...
 
P

Plazma

#5
Ну первое что приходит на ум это "считаешь вхождения":
при открытие скобки +1*(2^(0+индекс_открытия))
при закрытии скобки -1*(2^0+индекс_открытия)
где индекс открытия у тебя идет от 0...
Причем т.к. у тебя типов скобок несколько, то считаешь для каждой отдельно... (но индекс входимости всегда один, при открытие любой скобки мы его инкрементируем ++, при закрытии дикрементируем --)




Добавлено: Ну это самый оптимальный алгоритм... Можно длинее но проще...
Если я правильно понил твою мысль между двумя скобками не должно быть нечетное количество скобок.А как быть если ввод такой :
({{)
 

DarkKnight

Well-known member
01.08.2010
653
0
#6
Нет ни ничетное кол-во.... А должно сводится под нуль:
Вот смотри именно на твоем примере:
int Index = 0;
int a =0 - сумматор для скобок "()"
int b = 0 - суматтор для скобок "{}"

({{)

"("
a += pow(2.0,Index) // a = 0 + 1
Index++; //Index = 1
"{"
b+= pow(2.0,Index) // b = 0 + 2;
Index++; //Index = 2;
"{"
b+= pow(2.0,Index); // b = 2+ 4= 6
Index++; //Индекс = 3
")"
Index--; //Индекс = 2
a-= pow(2.0,Index); // a = 1- 4 = -3
//Итог :
a = -3; //-> Не хватает 2х скобок до ")"
b = 6 //Открытых скобок 2 которые не имееют завершения
А если бы a и b равны были нулю - то все скобки выполнены успешно
З.Ы. a и b лучше сделать (вещественными) для наглядности или выходить с ошибкой сразу как индекс<0 Значит закрывающихся скобок уже на текущей позиции больше чем открывающихся
 

DarkKnight

Well-known member
01.08.2010
653
0
#7
Вот примерно так...
C++:
/*
codeby.net
Autor: DarkKnight125
*/
#include <iostream>

using namespace std;

void main(void)
{
setlocale(LC_ALL,"Russian");
int Index = 0; //Идекс открытости
char Str[128] = {0}; //Исковая строка
double Arr[3] = {0}; //Наш массив-сумматор для скобок Arr[0] ()
//Arr[1] {}
//Arr[2] []

cout<<"Введите исходную строку: ";
cin.getline(Str,127); //Введем строку тип (a*b{ab}-c)

for (int i = 0; i<strlen(Str); i++) //Обойдем всю строку
{
if (Str[i] == '(' || Str[i] == ')') //Если попался один из символов круглых скобок
switch (Str[i]) //Проверим какой
{
case '(': //Если открытие
Arr[0]+=pow(2.0,Index); //Прибавим к нужному эл. массива 2*текущая_входимость(индекс открытости скобки)
Index++; //Увеличим индекс
break;
case ')': //Если закрытие
Index--; //Сначало уменьшим индекс т.к. если было окрытие то индекс мы уже увеличили, а нам нужен индекс одного уровня
Arr[0]-=pow(2.0,Index); //Потом отними
}
//По аналогии все остальные
else if (Str[i] == '{' || Str[i] == '}')
switch (Str[i])
{
case '{':
Arr[1]+=pow(2.0,Index);
Index++;
break;
case '}':
Index--;
Arr[1]-=pow(2.0,Index);
}
else if (Str[i] == '[' || Str[i] == ']')
switch (Str[i])
{
case '[':
Arr[2]+=pow(2.0,Index);
Index++;
break;
case ']':
Index--;
Arr[2]-=pow(2.0,Index);
}
}

bool isGood = true; //Флаг правельности синтаксиса, предположи что синтаксис из начально верен 
for (int i = 0; i<3; i++) //Обойдем массив и проверим все ли значение равны 0
{
if (Arr[i] != 0)
isGood = false; //Если хотя бы одно из значений не равно нулю то значит синтаксис не верен
}

if (isGood) //Согласно флагу выведим сообщение
cout<<"Кол-во скобок соответствует синтаксису"<<endl;
else cout<<"Ошибка : Расположение скобок ошибочно"<<endl;

}
Добавлено:
А запостите пожалуйста еще ваше решение первой задачи... Для форума... Можете позже, там например после сдачи вами задачи....
Если вам не сложно конечно...

Добавлено:
Немного добавил комментариев
 
P

Plazma

#8
Нет ни ничетное кол-во.... А должно сводится под нуль:
Вот смотри именно на твоем примере:

З.Ы. a и b лучше сделать (вещественными) для наглядности или выходить с ошибкой сразу как индекс<0 Значит закрывающихся скобок уже на текущей позиции больше чем открывающихся
спасибо за реализацию ,но ваш код выдает ошибку если ввести такой тест: {[()([]{})[]]({}{{}})}[]
 

DarkKnight

Well-known member
01.08.2010
653
0
#9
Проверьте еще раз, я может когда постил код, что-нить затер, потому как цитатами сначало вставлял.....

Результат на скрине:
 

Вложения

P

Plazma

#10
Проверьте еще раз, я может когда постил код, что-нить затер, потому как цитатами сначало вставлял.....

Результат на скрине:
А все спасибо , теперь понял вашу мысль,вы просто перепутали цифру. Вот правильный вариант написания:
Код:
#include <iostream>

using namespace std;

void main(void)
{
setlocale(LC_ALL,"Russian");
int Index = 0; //Идекс открытости
char Str[128] = {0}; //Исковая строка
double Arr[3] = {0}; //Наш массив-сумматор для скобок Arr[0] ()
//Arr[1] {}
//Arr[2] []

cout<<"Введите исходную строку: ";
cin.getline(Str,127); //Введем строку тип (a*b{ab}-c)

for (int i = 0; i<strlen(Str); i++) //Обойдем всю строку
{
if (Str[i] == '(' || Str[i] == ')') //Если попался один из символов круглых скобок
switch (Str[i]) //Проверим какой
{
case '(': //Если открытие
Arr[0]+=pow(2.0,Index); //Прибавим к нужному эл. массива 2*текущая_входимость(индекс открытости скобки)
Index++; //Увеличим индекс
break;
case ')': //Если закрытие
Index--; //Сначало уменьшим индекс т.к. если было окрытие то индекс мы уже увеличили, а нам нужен индекс одного уровня
Arr[0]-=pow(2.0,Index); //Потом отними
}
//По аналогии все остальные
else if (Str[i] == '{' || Str[i] == '}')
switch (Str[i])
{
case '{':
Arr[1]+=pow(2.0,Index);
Index++;
break;
case '}':
Index--;
Arr[1]-=pow(2.0,Index);
}
else if (Str[i] == '[' || Str[i] == ']')
switch (Str[i])
{
case '[':
Arr[2]+=pow(2.0,Index);
Index++;
break;
case ']':
Index--;
Arr[2]-=pow(2.0,Index);
}
}

bool isGood = true;
for (int i = 0; i<3; i++)
{
if (Arr[i] != 0)
isGood = false;
}

if (isGood)
cout<<"Кол-во скобок соответствует синтаксису"<<endl;
else cout<<"Ошибка : Расположение скобок ошибочно"<<endl;}
 
B
#11
Я б, сделал бы по понятней. Прописал бы 2 функций:
1. ПроверкаСимвола в которой вначале извлекал текущий (или первый) символ из строки и в зависимости от символа вызывал функцию ПроверкаНаЗакрывающиюсяСкобку(Скобка) где Скобка необходимая тип закрытой скобки (Если скобка открывающаяся иначе выдавать ошибку).
2. ПроверкаНаЗакрывающиюсяСкобку(Скобка) в которой вначале извлекал следующий символ из строки, и если он не равен Скобка, то вызывается функция ПроверкаСимвола

Ну еще можно посчитать количество вызовов функции ПроверкаСимвола, что оно было рано заданному вначале значению.
 

DarkKnight

Well-known member
01.08.2010
653
0
#12
BVS
BVS будет время выложи свою реализацию тоже... Если не сложно будет....
 
B
#13
К сожалению это сложно (у меня не установлена студия).
Могу примерный код набросать:
C++:
bool f1(void)
{
bool flag;
n++; //подсчитываем количество вызовов
switch (Str[i])
{
case '(': 
flag = f2( ')' );
case '{': 
flag = f2( '}' );
case '[': 
flag = f2( ']' );
default:
flag = false;
}
return flag;
}

bool f2(char sk)
{
bool flag;
i++; //расмотрим след. символ
if (i == strlen(Str))
return false; //строка почему то закончилась
flag = Str[i] == sk; 
if (!flag) 
flag = f1();
return flag;
}
В начале программы определишь значение переменных (они должны находиться в области видимости обеих функций) i и n как 0, Str строка со скобками. Потом вызовешь функцию f1 и если ее результат истина сверишь количество ее вызов с заданным кол-вом скобок.
функцию f1 вызывать надо пока она возвращает истину и i меньше длины Str-1
 
B
#15
Тут все намного сложнее чем ты думаешь.
Не надо усложнять: Воспользуйся отладчиком и незначительно поменяй 2 функцию (я ведь бросал примерный код)

например так:
C++:
bool f2(char sk)
{
bool flag;
i++; //расмотрим след. символ
if (i == strlen(Str))
return false; //строка почему то закончилась
flag = Str[i] == sk; 
if (!flag) 
{
flag = f1();
if flag
{
i++;
if (i == strlen(Str))
return false; //строка почему то закончилась
flag = Str[i] == sk; 
}
}
return flag;
}
Главное подать идею, а осуществить вы ее надеюсь сможете.

PS:Да, а ведь должно выдавать NO ведь количество скобок в примере 5, а не 10 (если считать еще и закрывающиеся скобки то соответственно нужно считать и вызовы 2 функции).
 
P

Plazma

#16
DarkKnight125
Ваш код выдает ошибку, если ввести такой тест:
2
)(
Выводит "Yes" , хотя я исправил эту ошибку, но не смог исправить эту ошибку,если ввести:
6
())(()
Выводит "Yes"
 

DarkKnight

Well-known member
01.08.2010
653
0
#17
2 Plazma: Вот поэтому я и говорил про проверку отрицательности индекса
C++:
/*
codeby.net
Autor: DarkKnight125
*/
#include <iostream>

using namespace std;

void main(void)
{
setlocale(LC_ALL,"Russian");
int Index = 0; //Идекс открытости
bool isGood = true; //Флаг правельности синтаксиса, предположи что синтаксис из начально верен 
char Str[128] = {0}; //Исковая строка
double Arr[3] = {0}; //Наш массив-сумматор для скобок Arr[0] ()
//Arr[1] {}
//Arr[2] []

cout<< "Введите исходную строку: ";
cin.getline(Str,127); //Введем строку тип (a*b{ab}-c)

for (int i = 0; i<strlen(Str); i++) //Обойдем всю строку
{
if (Str[i] == '(' || Str[i] == ')') //Если попался один из символов круглых скобок
switch (Str[i]) //Проверим какой
{
case '(': //Если открытие
Arr[0]+=pow(2.0,Index); //Прибавим к нужному эл. массива 2*текущая_входимость(индекс открытости скобки)
Index++; //Увеличим индекс
break;
case ')': //Если закрытие
Index--; //Сначало уменьшим индекс т.к. если было окрытие то индекс мы уже увеличили, а нам нужен индекс одного уровня
Arr[0]-=pow(2.0,Index); //Потом отними
}
//По аналогии все остальные
else if (Str[i] == '{' || Str[i] == '}')
switch (Str[i])
{
case '{':
Arr[1]+=pow(2.0,Index);
Index++;
break;
case '}':
Index--;
Arr[1]-=pow(2.0,Index);
}
else if (Str[i] == '[' || Str[i] == ']')
switch (Str[i])
{
case '[':
Arr[2]+=pow(2.0,Index);
Index++;
break;
case ']':
Index--;
Arr[2]-=pow(2.0,Index);
}

if (Index < 0) //Если ндекс принял отрицательное значение, то сразу можно сказать что ошибка синтаксиса
{
isGood = false;
break; //Выйдим из цикла сразу
}
}

for (int i = 0; i<3; i++) //Обойдем массив и проверим все ли значение равны 0
{
if (Arr[i] != 0)
isGood = false; //Если хотя бы одно из значений не равно нулю то значит синтаксис не верен
}

if (isGood) //Согласно флагу выведим сообщение
cout<< "Кол-во скобок соответствует синтаксису"<< endl;
else cout<< "Ошибка : Расположение скобок ошибочно"<< endl;

}
 

DarkKnight

Well-known member
01.08.2010
653
0
#18
И все же считаю что этот (первый) мой вариант, абслютно рабочий и не может выдавать ошибки...
Алгоритм практически беззбойный...

C++:
/*
codeby.net
Autor: DarkKnight125
*/
#include <iostream>

using namespace std;

void main(void)
{
setlocale(LC_ALL,"Russian");
int Index = 0; //Идекс открытости
bool isGood = true; //Флаг правельности синтаксиса, предположи что синтаксис из начально верен 
char Str[128] = {0}; //Исковая строка
double Arr[3] = {0}; //Наш массив-сумматор для скобок Arr[0] ()
//Arr[1] {}
//Arr[2] []

cout<< "Введите исходную строку: ";
cin.getline(Str,127); //Введем строку тип (a*b{ab}-c)

for (int i = 0; i<strlen(Str); i++) //Обойдем всю строку
{
if (Str[i] == '(' || Str[i] == ')') //Если попался один из символов круглых скобок
switch (Str[i]) //Проверим какой
{
case '(': //Если открытие
Index++; //Увеличим индекс
Arr[0]+=pow(2.0,Index); //Прибавим к нужному эл. массива 2*текущая_входимость(индекс открытости скобки)
Index++; //Увеличим индекс
break;
case ')': //Если закрытие
Index--; //Сначало уменьшим индекс т.к. если было окрытие то индекс мы уже увеличили, а нам нужен индекс одного уровня
Arr[0]-=pow(2.0,Index); //Потом отними
}
//По аналогии все остальные
else if (Str[i] == '{' || Str[i] == '}')
switch (Str[i])
{
case '{':
Index++;
Arr[1]+=pow(2.0,Index);
break;
case '}':
Index--;
Arr[1]-=pow(2.0,Index);
}
else if (Str[i] == '[' || Str[i] == ']')
switch (Str[i])
{
case '[':
Index++;
Arr[2]+=pow(2.0,Index);
break;
case ']':
Index--;
Arr[2]-=pow(2.0,Index);
}

}

for (int i = 0; i<3; i++) //Обойдем массив и проверим все ли значение равны 0
{
if (Arr[i] != 0)
isGood = false; //Если хотя бы одно из значений не равно нулю то значит синтаксис не верен
}

if (isGood) //Согласно флагу выведим сообщение
cout<< "Кол-во скобок соответствует синтаксису"<< endl;
else cout<< "Ошибка : Расположение скобок ошибочно"<< endl;

}