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

Plazma · 17.11.2010

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

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

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

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

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

DarkKnight · 18.11.2010

Идеи по написанию какие-нибудь есть???
может код начали писать уже???

Plazma · 18.11.2010

DarkKnight125 сказал(а):
Идеи по написанию какие-нибудь есть???
может код начали писать уже???

Первую я уже самостоятельно решил, пожалуйста подбросьте идею ко второй задаче, как можно быстро и легко решить эту задачу?

DarkKnight · 18.11.2010

Ну первое что приходит на ум это "считаешь вхождения":
при открытие скобки +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
А тут все верно...

Добавлено: Ну это самый оптимальный алгоритм... Можно длинее но проще...

Plazma · 18.11.2010

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

Добавлено: Ну это самый оптимальный алгоритм... Можно длинее но проще...

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

DarkKnight · 18.11.2010

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

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 · 18.11.2010

Вот примерно так...

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;

}

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

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

Plazma · 18.11.2010

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

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

спасибо за реализацию ,но ваш код выдает ошибку если ввести такой тест: {[()([]{})[]]({}{{}})}[]

DarkKnight · 18.11.2010

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

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

Plazma · 18.11.2010

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++)
{
if (Arr[i] != 0)
isGood = false;
}

if (isGood)
cout<<"Кол-во скобок соответствует синтаксису"<<endl;
else cout<<"Ошибка : Расположение скобок ошибочно"<<endl;}

BVS · 18.11.2010

Я б, сделал бы по понятней. Прописал бы 2 функций:
1. ПроверкаСимвола в которой вначале извлекал текущий (или первый) символ из строки и в зависимости от символа вызывал функцию ПроверкаНаЗакрывающиюсяСкобку(Скобка) где Скобка необходимая тип закрытой скобки (Если скобка открывающаяся иначе выдавать ошибку).
2. ПроверкаНаЗакрывающиюсяСкобку(Скобка) в которой вначале извлекал следующий символ из строки, и если он не равен Скобка, то вызывается функция ПроверкаСимвола

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

DarkKnight · 18.11.2010

BVS
BVS будет время выложи свою реализацию тоже... Если не сложно будет....

BVS · 18.11.2010

К сожалению это сложно (у меня не установлена студия).
Могу примерный код набросать:

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

lazybiz · 18.11.2010

Plazma

Plazma сказал(а):
Ввод
10
[()]([]{})
Вывод
No

Разве в этом примере результат должен быть "NO" ??

Добавлено: BVS
Тут все намного сложнее чем ты думаешь.

BVS · 19.11.2010

lazybiz сказал(а):
Тут все намного сложнее чем ты думаешь.

Не надо усложнять: Воспользуйся отладчиком и незначительно поменяй 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 функции).

Plazma · 19.11.2010

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

DarkKnight · 20.11.2010

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 · 20.11.2010

И все же считаю что этот (первый) мой вариант, абслютно рабочий и не может выдавать ошибки...
Алгоритм практически беззбойный...

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;

}

Все сервисы Codeby

Поиск

Поиск

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

Plazma

DarkKnight

Plazma

DarkKnight

Plazma

DarkKnight

DarkKnight

Plazma

DarkKnight

Вложения

Plazma

BVS

DarkKnight

BVS

lazybiz

BVS

Plazma

DarkKnight

DarkKnight