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

Тема в разделе "C/C++/C#", создана пользователем Plazma, 17 ноя 2010.

  1. Plazma

    Plazma Гость

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

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

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

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

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

    DarkKnight Well-Known Member
    C\C++ Team

    Регистрация:
    1 авг 2010
    Сообщения:
    653
    Симпатии:
    0
    Идеи по написанию какие-нибудь есть???
    может код начали писать уже???
     
  3. Plazma

    Plazma Гость

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

    DarkKnight Well-Known Member
    C\C++ Team

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

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

    Plazma Гость

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

    DarkKnight Well-Known Member
    C\C++ Team

    Регистрация:
    1 авг 2010
    Сообщения:
    653
    Симпатии:
    0
    Нет ни ничетное кол-во.... А должно сводится под нуль:
    Вот смотри именно на твоем примере:
    З.Ы. a и b лучше сделать (вещественными) для наглядности или выходить с ошибкой сразу как индекс<0 Значит закрывающихся скобок уже на текущей позиции больше чем открывающихся
     
  7. DarkKnight

    DarkKnight Well-Known Member
    C\C++ Team

    Регистрация:
    1 авг 2010
    Сообщения:
    653
    Симпатии:
    0
    Вот примерно так...
    Код (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;

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

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

    Plazma Гость

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

    DarkKnight Well-Known Member
    C\C++ Team

    Регистрация:
    1 авг 2010
    Сообщения:
    653
    Симпатии:
    0
    Проверьте еще раз, я может когда постил код, что-нить затер, потому как цитатами сначало вставлял.....

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

    Вложения:

    • zskobki.jpg
      zskobki.jpg
      Размер файла:
      29,6 КБ
      Просмотров:
      68
  10. Plazma

    Plazma Гость

    А все спасибо , теперь понял вашу мысль,вы просто перепутали цифру. Вот правильный вариант написания:
    Код (Text):
    #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;}
     
  11. BVS

    BVS Гость

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

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

    DarkKnight Well-Known Member
    C\C++ Team

    Регистрация:
    1 авг 2010
    Сообщения:
    653
    Симпатии:
    0
    BVS
    BVS будет время выложи свою реализацию тоже... Если не сложно будет....
     
  13. BVS

    BVS Гость

    К сожалению это сложно (у меня не установлена студия).
    Могу примерный код набросать:
    Код (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
     
  14. lazybiz

    lazybiz Well-Known Member
    C\C++ Team

    Регистрация:
    3 ноя 2010
    Сообщения:
    1.344
    Симпатии:
    0
    Plazma
    Разве в этом примере результат должен быть "NO" ??

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

    BVS Гость

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

    Plazma Гость

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

    DarkKnight Well-Known Member
    C\C++ Team

    Регистрация:
    1 авг 2010
    Сообщения:
    653
    Симпатии:
    0
    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;

    }
     
  18. DarkKnight

    DarkKnight Well-Known Member
    C\C++ Team

    Регистрация:
    1 авг 2010
    Сообщения:
    653
    Симпатии:
    0
    И все же считаю что этот (первый) мой вариант, абслютно рабочий и не может выдавать ошибки...
    Алгоритм практически беззбойный...

    Код (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;

    }
     
Загрузка...
Похожие Темы - Задача Скобки (определение
  1. Янчик
    Ответов:
    0
    Просмотров:
    489
  2. TrishaRay
    Ответов:
    1
    Просмотров:
    782
  3. elzim
    Ответов:
    0
    Просмотров:
    932
  4. ShaoKahn
    Ответов:
    1
    Просмотров:
    1.125
  5. eremin-sanek
    Ответов:
    3
    Просмотров:
    1.107

Поделиться этой страницей