Велокиїв

Може хтось з них допоможе мені з моїм питанням?

Отже, є задача:

Для введённой пользователем с клавиатуры строки программа должна определить, корректно ли расставлены скобки (круглые, фигурные, квадратные). «Перемешивание» скобок (пример: «{[}]») считается некорректным вариантом.

Є код, написаний мною, який цю задачу коректно вирішує: І є проблема:
мені не подобається те, що я відкриваю масив довжиною в цілу стрічку. Це якесь марнування ресурсів. Думаю, цю задачу можна вирішити простіше.

Питання:
як можна оптимізувати алгоритм?
якби хтось хоча би на пальцях пояснив, як оптимізувати алгоритм, ідею в код я переведу сам.

Заздалегідь вдячний!

Тут следует волноваться не из-за растраты ресурсов (размер ввода в принципе мизерный), а из-за кучи однотипных case (очень плохой стиль).
Сделай обьект, который будет держать варианты открывающих/закрывающих скобок; самый простой пример - 2 массива, openingDelimiters = [ '{','[', ...etc.. ], closingDelimiters = [ '}',']', ...etc.. ] и массив для счетчиков, и в 2х вложенных циклах делай действия проверки.
Для хранения "последних скобок" (и да, для уменьшения растраты памяти) можно использовать коллекцию типа List (а еще правильнее - Stack, он оптимизирован под добавление/удаление с конца), добавляя и удаляя из нее элементы.

Юзать динамические массивы или специальные структуры данных.
Не знаю, как там в яве, в С# есть всякие динамические списки ListArray или обобщенные коллекции List<>.

а зачем так сложно?
там есть проще алгоритм, лексический. связаный с простым подсчетом.
в нем память расходуется как o(m) где m - количество лексем(у тебя 6).

дальше (не моя) цитата которая показывает как.

при открытие скобки +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
А тут все верно...

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

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

}

причем это выше ^^ со строчкой,в вообще задача решается с хранением трех longint и двумя проверками.если гдето стало <0 то уже неверно,если гдето стало почти максимум, то значит ты не можешь ее решить по переполнению.

а зачем так сложно?

Господи, не кипятите человеку мозг. Всего то нужно немного переписать код, причем рабочий!!!
А вы ему тут какие-то адские алгоритмы даете, причем на С!
Препод такое увидит и крышей двинется

да куда уж проще. если для вас это сложно да и еще О УЖАС!!! на си, то топикстартер то границ не давал. и воообще алгоритм простой и на чем написан - неважно. перепиать минут 20 и отладить еще часик.

код с использованием длинных массивов для такой тривиальной задачи никак нельзя признать рабочим.

да куда уж проще. если для вас это сложно

Мне вообще до ... Обо мне речь не идет.

О УЖАС!!! на си, то топикстартер то границ не давал.

Вообще так, на секундочку, топикстартер выложил то что он наваял на яве! Я указал, что он может использовать с точки зрения шарпа, а как известно - это те же яйца, только в профиль.

алгоритм простой и на чем написан - неважно. перепиать минут 20 и отладить еще часик.

Вот я вообще категорически не понимаю, зачем полтора часа тратить на переписывание того, что уже работает, заново, чем потратить 15-20 минут на доработку кода???

Вобщем автору понаписывали тут всего, пущай выбирает, что более рационально в его случае.

Как-то так. Не тестировал, может какие-то варианты упустил. С нормальным форматированием здесь

Є код, написаний мною, який цю задачу коректно вирішує:

Нет, код некорректен. Ввод, начинающийся с открывающего символа, например ")()", выбрасывает исключение index out of bounds.

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

супер, ідея зі степенем двійки сподобалася, вже цікавіше.
Ще б покопатися над тим, щоб позбавитися switch-if багаточисленних і було б ащщє супер. Подумаю над цим.

/*
http://www.codeby.net
Autor: DarkKnight125
*/
switch (Str)
{
case '[':
Index++;
Arr[2]+=pow(2.0,Index);
Index++;
break;
...
}

додав це і ще одне інкрементування, бо інакше не працює у мене цей алгоритм на папірці.

в вообще задача решается с хранением трех longint и двумя проверками.если гдето стало <0 то уже неверно,если гдето стало почти максимум, то значит ты не можешь ее решить по переполнению.

Не зрозумів

ну вы читаете скобочки по одной и сохраняете результат вон тех выраженией для каждой скобочки по мере прохода.
если стало меньше нуля гдето - то это сразу фейл и можно дальше не читать.

в конце сравниваете с 0.

код не проверял,взял первый попавшийся по запросу "задача о скобках". задача кстати классическая изучается во всех курсах теории алгоритмов. к ней сводится дофига других задач оценки

Всего то нужно немного переписать код, причем рабочий!!!

Нє-а, мені хочеться оптимізувати алгоритм, а не допіліть код. Мерал толкову ідею запропонував.

Причому викладача немає, я сам вчуся ( задача стирена на http://www.kostin.ws/java).

Тому і чіткого критерію оптимізації немає. Але якось не хочеться ні гвозді забивать ескаватором, ні сваі забивать молотком.

Вот я вообще категорически не понимаю, зачем полтора часа тратить на переписывание того, что уже работает, заново, чем потратить 15-20 минут на доработку кода???

Щоб знати правильний для конкретного випадку метод і при цьому знати інші можливі варіанти.

рекомендую прочитать или прослушать курс теории алгоритмов с первого курса.
у почти уверен что в любом университете как минимум дадут перексерить конспект. аскорее всего и не будут возражать против присутсвия на лекции.
ну и курс дискретки тоеж не помешает. а так задачками врядли получится. надо более менее цельное представление.

а по критериям - как правило рассматриваются три критерия.

1) скорость написания решения

2) ефективность по памяти(важна для задач большой размерности)

3) еффективность по количеству операций.

как правило все три взаимоисключающие.

вот тот что я вам запостил это оптимизация по памяти. зато операции там классически(при вычислении человеком) не простые(а на машине простые,ибо 2 в степени на текущей архитектуре тривиальный сдвиг а сложение одна регистровая машинная команда).

я в травні диплом бакалавра факультету комп'ютерних наук авіаційного отримав. до фєні ті лекції з конспектами разом з універом.

Spoiler

Show

Код: Виділити все

import java.util.LinkedList; public class ParenCheck { static int OPENING = 1, CLOSING = -1; static int PAREN = 0, BRACKET = 1, BRACE = 2, PAIRING = 3; static String[] desc = { "()", "[]", "{}", "Pairing" }; static int[] check(char[] s) { int[] stat = new int[4]; int sym, type; LinkedList<Integer> stack = new LinkedList<Integer>(); for(int i=0; i<s.length; i++) { switch(s[i]) { case '(': sym = PAREN; type = OPENING; break; case ')': sym = PAREN; type = CLOSING; break; case '[': sym = BRACKET; type = OPENING; break; case ']': sym = BRACKET; type = CLOSING; break; case '{': sym = BRACE; type = OPENING; break; case '}': sym = BRACE; type = CLOSING; break; default: continue; } stat[sym] += type; if(type == OPENING) stack.push(sym); else { Integer last = stack.peek(); if(last != null && last == sym) stack.pop(); else stat[PAIRING]++; } } stat[PAIRING] += stack.size(); return stat; } public static void main(String[] args) { if(args.length > 0) { int[] stat = check(args[0].toCharArray()); for(int i=0; i<stat.length; i++) System.out.format("%s errors: %d\n", desc[i], Math.abs(stat[i])); } } }

На папірці працює. Мені здається, найоптимальніший з усіх запропонованих варіантів.

ідею запам'ятав, піду писать-перевірять.

ну значит препод фиговый был. дискретка один из самых полезных прослушанных курсов.

Еще можно попробовать регулярными выражениями задачку решить. Кода меньше будет.
Но это, наверно, тот вариант, когда гвозди экскаватором.. : )

о. а как реуглярным выражением?
желательно на примере длиной в 10000 скобочек.
и желательно чтоб при этом было обозримое время и хватило памяти.

Для начала мне понадобится пара валидных примеров длинной 10000 скобочек..

я пробував регекспи)

чо попрощє у мене навіть виходило відфільтрувати,але вирішити задачу повністю не вийшло)

імхо, це варіант для тих, хто код в умі від А до Я пише.

Для начала мне понадобится пара валидных примеров длинной 10000 скобочек..

нефиг делать.
лови

http://pro-sip.net/temp/scobki.txt
http://pro-sip.net/temp/scobki2.txt

там не ровно 10000, скорее ближе к 20к, но это достаточно. разнообразие там низкое. а именно ровно 5,но для примера сойдет.

можно попробовать регулярными выражениями

Не получилось
Кроме того, как оказалось, регекспы не предназначены для вложенных структур.
Мeral, ты знал

Для введённой пользователем с клавиатуры строки программа должна определить, корректно ли расставлены скобки (круглые, фигурные, квадратные). «Перемешивание» скобок (пример: «{[}]») считается некорректным вариантом.

ну вы читаете скобочки по одной и сохраняете результат вон тех выраженией для каждой скобочки по мере прохода.
если стало меньше нуля гдето - то это сразу фейл и можно дальше не читать.
в конце сравниваете с 0.

meral немного не додумал свой вариант.
Как по мне, самым оптимальным будет решение с помощью стека.
Анализируем скобки по одной - если скобка открывающая (любого вида) - кладём в стек, если закрывающая - вытаскиваем скобку из стека и сравниваем, чтобы она была такого же типа, как только что считанная закрывающая.
Если на любом этапе вытянутая из стека открывающая скобка не соответствует считанной закрывающей (или стек пустой и нечего вытаскивать), или стек не пустой после считывания всей последовательности - значит последовательность некорректная.
Как-то так..

вариант со стеком плохой.

контрпример - 500000 скобочек { и потом 499999 скобочек }

очевидно что оптимальный вариант решает его за линейное время с использованием одного слова(4байта наверно для таких границ). а стековый вариант скорее всего загнется в реале. и требует линейной памяти. ну и время тоже линейное, но больше(ибо куча операций "положить на стек"

Вы Боги! Читаю - наслаждаюсь . Вот так за час взять и переделать Вселенную ! Я всегда хотел быть программистом. Но так сложилось, что работаю с людьми. По сути, реставратором. Восстанавливаю то, что создала природа, а потом оно сломалось. У меня алгоритм уже четко прописан. Степеней свободы - ноль. А вы - Творцы!