Решал эту задачу 3 часа, до сих пор в шоке, насколько сложное это ваше программирование для обычного заводчанина. И это якобы курс для школьников, задача далеко не самая сложная. Тем более Python, который считается очень легким языком. На каком-нибудь С++ я бы это 3 дня решал. Видимо, нужно иметь очень высокий интеллект, чтобы вкатиться в программирование и сильные математические способности, иначе там просто нечего делать.
>>259988660 (OP) В алгоритмических олимпиадных задачах язык не решает ничего В реальной разработке ты ничего сложнее реализации дерева и поиска по нему писать не будешь Тем более все эти алгоритмы легко гуглятся
>>259988660 (OP) Давай разберем по частям тобою написанное. >задача далеко не самая сложная Да. Абсолютно изи. Рил за 1 минуту решается. >Тем более Python, который считается очень легким языком. На каком-нибудь С++ я бы это 3 дня решал. Нет. На уровне простых задачек различия языков не проявляются. >нужно иметь очень высокий интеллект, чтобы вкатиться в программирование и сильные математические способности Интеллект помогает, но не является обязательным. Можно надрочиться на конкретные типы задач. Тебе сложно именно томучто ты не знаешь примеров решений похожих задач.
>>259988660 (OP) Считаешь открывающиеся скобки, считаешь закрывающие, сравниваешь, до этой хуйни ифы которые проверяют есть ли чтото кроме скобок. Чо сложного?
def is_correct_bracket(text): open_br = 0 for i in text: if i == '(': open_br += 1 elif i == ')': if open_br > 0: open_br -= 1 else: return False return True
>>259988660 (OP) Если получилось это решить значить есть перспективы и всё ок. Просто продолжай в том же духе. Ты же не собирался получить востребованную и высокооплачиваемую работу за месяц?
>>259988660 (OP) >Видимо, нужно иметь очень высокий интеллект, чтобы вкатиться в программирование и сильные математические способности, иначе там просто нечего делать Ебать! А ты думал, что там всё просто? И всё решается гуглежом? А задача интересная, кстати.
>>259988660 (OP) >Тем более Python, который считается очень легким языком. На каком-нибудь С++ я бы это 3 дня решал. Это алгоритмические задачи, вообще пох на чём писать. >>259988885 (define (ti-pidor? anon) (eq? anon 'op))
>>259990301 Тогда тебе задача со звездочкой. Придумай тест, который не пройдёт вот у этого анона >>259990051 , если он в конце добавит проверку незакрытых скобок.
>>259988660 (OP) > Тем более Python, который считается очень легким языком. На каком-нибудь С++ я бы это 3 дня решал.
Эту задачу что на питоне, что на сях, что на асме однохуйственно одинаково решать. Тут вопрос не в "сложности языка", а в банальном умении писать простые алгоритмы.
Во, всё решение, ёпта: // Для подсчета балансировки скобок counter := 0
// Бегаем по каждому символу for c in inputStr { switch (c) { case "(": counter++ // Увеличиваем счетчик скобок при открытой скобке case ")": counter-- // уменьшаем при закрытой default: continue // не скобка? Ну пошли дальше значит }
// это сработает, если закрывающих скобок больше, чем открывающих, либо они тупо раньше в строке, мол, ") хуй (" if counter < 0 { return false } }
// проверям что скобки сбалансированы. if counter == 0 { return true } else { return false }
>>259988885 Абсолютно стандартная задача для любого парсера. Иди нахуй, чмошник безграмотный.
>>259990685 я то блять думаю, хули джава приложении такие говно тормознутное. Оказывается джава синьоры классическую задачу на стек через регулярку решают. Ебааааать
>>259990737 >>259990739 эх, детишки. есть задача ,есть решение, в условии нет требований к производительности, да и сложность тут один хер линейная. а вам кста перезвонят с вашими счетчиками и иф зен элсами
>>259988660 (OP) Это элементарная задача на понимание структуры данных "стек", чего там больше пяти минут пердолиться? Может не пытаться по говнокурсам вайти, а в универ поступить?
>>259990855 guard struna_so_skobkami.count % 2 !=0 else {return false} В свифте есть гвард, в питоне можно просто if в функцию на старте запихать, нет смысла решать задачу как-то после осознания что количество скобочек нечетное
поясните непогромисту. с одним видом скобок надо просто проверять чтобы количество закрывающих никогда не превышало количество открывающих. с большим количеством видов скобок надо применять другие алгоритмы
>>259990954 > нет смысла решать задачу как-то после осознания что количество скобочек нечетное
Хуйню какую-то написал. Во-первых, нахуй не нужный корнеркейс, который можно и так общим случаем обработать, во-вторых, всё-таки в реальном мире задача подсчета скобок предполагает что между ними что-то есть.
Какого тут космического эффекта дает guard -- непонятно.
>>259988660 (OP) Идешь по массиву и считаешь открывающие и закрывающие скобки. Если в какой-то момент открывающих больше - false. Если в конце количество не совпало - false. Иначе true.
>>259991110 Это свифтовая привычка Я не знаю как в других языках, но например когда пишешь любой алгоритм сортировки, всегда начинаешь с quard arr.count == 1 else {return arr} Я думаю в других языках тоже аррей с 1 элементом считается отсортированным. Поэтому есть тенденция в гвард запихивать все корнеркейсы как ты их назвал
>>259988660 (OP) по идее можно сделать цикл с проходом по всем символам и на каждую встреченную открывающую скобку искать дальше по строке закрывающую, после чего удалять закрывающую или запоминать её индекс. и если в конце остаётся неотмеченная закрывающая скобка или открывающая без пары или вообще если строка начинается с открывающей то сразу FALSE
>>259990931 > говнокурсам вайти, а в универ поступить?
Любой говнокурс по программированию лучше, чем то, что дают в среднем универе. В универ нужно идти не для того, чтобы научиться программированию, а чтобы получить хорошую математическую базу и начать шарить в алгоритмах. Чтобы стать васяном погромиздом на 90% вакансий универ нахуй не всрался.
>>259988660 (OP) А массивами пользоваться можно? Можно по индукции найти закономерность, что правильные скобки - это четные и ( должен предшествовать ), короче для n=2: (), для n=4: ()(), (()) для n=6:()()(), ()(()), ((())) и т.д. Т.е. как видишь следующие последовательности получаются из предыдущих добавлением для каждой из них либо () по разным сторонам от скобок, т.е. для n=4 это добавление для () сбоку скобки (), либо внутри (...), как например (()) новых скобок. Короче, создаешь массивы строк правильных скобок для хотя n=32, а потом через поиск находишь соответствует ли входная скобка правильной, просматривая массив и находя подобную скобку, если не найдена, то скобка неправильная.
>>259990818 чувак, парсер регулярок в сто раз тебя умнее и он проверит даже блять оптимальнее чем твое посимвольное корявое поделие. На строке в 100 миллионов символов проверка этой регулярки отрабатывает за 93 мс, и это возможно даже лучше чем втое кривое косое поделие, по крайней мере уж никак не хуже. учите матчасть епта
>>259988660 (OP) Алгоритм простой на стек, решается в один проход. Бежим по строке слева направо, когда встречаем открывающую скобку заносим оную в стек, при закрывающей вытаскиваем значение из стека. В конце если стек пустой - последовательность верна. Работает с любым количеством скобок. Линейная сложность алгоритма O(n). Знатоки, правильно решил?
>>259989817 >>259989798 Бля обосрался А если тогда сделать чтобы иф посимвольно проверял строку, когда находит ( в переменную записывается номер символа и дальше считвает пока не найдёт ) эти две скобки удаляются, если в строке не осталось символов тру, если что то осталось фолс. Проверьте, а то чувство что опять проебался.
>>259991164 Ого, ну нихуя себе, ты сэкономил целых пару строк условного иллюстративного псевдокода на выдуманном языке, вот это да! Ты наверно такой умный!
>>259989159 >Тем более все эти алгоритмы легко гуглятся Как гуглить алгоритмы? Как понять какой алгоритм для конкретной задачи нужен? Как допустим из трёх алгоритмов определить самый подходящий под конкретный случай, допустим из трёх доступных?
>>259988660 (OP) Тоже пытался вкатиться в пограмирование некоторое время назад и тоже решал подобные задачки, у меня друган есть синьор помидор на яве 200к в наносекунду, так я её терроризировал постоянно с помощью по задачкам, так вот мы вместе сидели и тупили как правильно это сделать. С реальными рабочими задачами эта хуйня имеет мало общего.
>>259991298 Короче выглядит так 1 Создать большой список или массив строк 2 Первый (нулевой) элемент массива равен (), т.е. n=2 3 Заполнить оставшиеся элемента списка или массива прибавлением или конкатенацией скобок '()' + 'предыдущая правильная последов скобок', либо 'предыдущая правильная последов скобок'+')', либо '('+'предыдущая правильная последов скобок'+')' 4 Делаем так n раз, например 64 или 100 5 Получаем массив правильных скобок 6 Получаем входную скобку через функцию и ищем ее в массиве правильных скобок 7 Если найдена - вывести True, иначе False
>>259991313 > чувак, парсер регулярок в сто раз тебя умнее и он проверит даже блять оптимальнее беспруфный джава петушок, пожалуйста, да и вообще, сейчас бы регулярками подсчитывать количество символов, даже не представляю, какой говнокод ты высираешь ежедневно
>>259989975 Решу с 1 счетчиком. Берешь счетчик. Запускаешь цикл В цикле берешь след символ. ( - плюсуешь 1 ) - минусуешь 1 На каждой итерации проверяешь, счетчик меньше нуля - брейк. После цикла, счетчик 0 - все окей. Не 0 - последовательность говно.
Классическая задача на стек -- это обратная польская нотация. А тут стек алгоритм в O(1) по памяти превращается в O(n) в худшем случае. ХУЕТА и стек тут не нужен. Задача с 1 курса универа, буквально Laba3.pas, ебана. Пиздец вкатывальщики пошли, я хуею.
>>259990217 Охуенно высокооплачиваемая да. Иногда вкатываюсь на джуна непонятно зачем. Недавно сделал очередное тестовое. Пиздец говна поел со всеми этими мавенами, спрингами, хибернейтами, жсонами и прочей поеботой. Просто блять вагонище тупорылый технологий, смысл которых вообще не понятен почему блять именно хибернейт, почему нельзя JDBC а потом уже на стажировке тыкать хибернейт? Предлагают стажировку джуном 3 мес. зп - 10к меньше минималки, да, типа буду на 0.75 ставки или как там. Блять я когда на сврщика учился в пту по путевке от цзн - я меньше килограмма электродов сжег, и меня уже мастер звал работать куда-то за 25к для начала. И сварщиком если вкалывать как и кодером, зарплата будет не меньше, и зная язык можно оформить перекат в норм страну.
Всё без стека прекрасно решается. Вообще нахуй не нужен стек, если тебе не надо знать какие-то детали про каждый элемент на стеке. В данной задаче достаточно понимать что скобки должны в итоге засумммироваться в 0 и всё.
Посчитал количество символов одного типа и второго типа, если не равны = false. Тебя чисто синтаксис доебал?
Я ничего сложнее экселя никогда в руках не держал, но прост если проблема в самой форме записи то это дело наживное, главное вникать и закладывать в голову все больше с каждым днем. Если проблема в том чтобы написать код который сам определит, какие символы в тексте должны совпадать по количеству, то ты там дата саентистом что ли идешь?
>>259992092 >>259992060 >>259990762 Мда, в треде не поняли, что последовательность )()( - не является правильным, даже несмотря на то, что число ( и ) совпадает, вы условия читайте нормально
>>259992131 Для этого случая работает. Получается, нужно завести массив счетчиков и добавлять элемент каждый раз, когда открывается скобка другого типа. Тогда ты уже на третьем элементе получишь -1 и, соответственно, false.
>>259992021 > Просто блять вагонище тупорылый технологий, смысл которых вообще не понятен почему блять именно хибернейт, почему нельзя JDBC а потом уже на стажировке тыкать хибернейт?
Это ты просто сам тупорылый, раз не понимаешь такие простые абстракции. Ты бы ещё поныл, что чёт сложно, давай проводочек руками замыкать и сигналы так в базу слать, а то какие-то драйверы, пиздец, сложно же.
> Предлагают стажировку джуном 3 мес. зп - 10к Да это ещё и охуеть, ты же вообще не умеешь нихуя. Тебе в пору бы самому раскошелиться и хоть на какие-то курсы сходить, а то ты же реально в принципе не понимаешь что происходит.
>>259988660 (OP) А хули сложного. Ждёшь первую скобку. Если она открывающаяся, идёшь дальше, если нет, сразу false Идём дальше. Делаем 2 переменных счётчика. Одна для (, другая для ) Если в конце строки оба счётчика равны, выводим тру, иначе фолс.
>>259988660 (OP) Это задача из синтаксических анализаторов, парсеров, там целая теория по грамматикам и тд, тут не так всё просто. Мне её объясняли как решать в шараге, хотя я и сам до этого калькулятор для любых выражений писал. Не помню уже за сколько этот анализатор тогда написал, но больше чем за 3 часа явно, мб за несколько дней даже. Так что не так всё плохо, если ты дел с прогой до этого вообще не имел
>>259992153 > Мда, в треде не поняли, что последовательность )()( - не является правильным
Всё поняли, читай внимательно >>259990762 -- там внутри цикла на каждой итерации проверка что закрывающая скобка не появилась раньше времени (if counter < 0)
>>259992086 Это такой список, к которому можно добавлять элементы только в конец и убирать их тоже только из конца. то есть ты просто создаешь в пятоне список и "играешь" по этим правилам. Подумай как ты можешь стек использовать в этой задаче.
>>259988660 (OP) Это задача на знание и понимание стандартных алгоритмов и структур данных, а именно стека, ну и проверка на то, что у тебя есть обычная, человеческая логика и здравый смысл. Если ты её решил за три часа не зная, что такое стек - то ты сверхразум и очень далеко пойдешь, без шуток. > Тем более Python, который считается очень легким языком. На каком-нибудь С++ я бы это 3 дня решал. В такого рода задачах язык ни на что не влияет, максимум - придётся гуглить стандартную библиотеку, если ты её не не знаешь.
>>259992448 > Это задача из синтаксических анализаторов, парсеров, там целая теория по грамматикам и тд, тут не так всё просто
Тут всё супер-просто. Подсчет скобок вообще самая тупая и тривиальная задача из области парсинга поэтому в машиночитаемой хуйне так часто используются всякие скобушки, не надо никаких грамматик выдумывать.
>>259988660 (OP) А что там решать? Заводишь счетчик. Прибавляешь 1, если скобка "(", и отнимаешь 1, если скобка ")"/ Если в какой-то момент в счетчике отрицательное число, возвращаешь false. Иначе true.
>>259992515 > Это задача на знание и понимание стандартных алгоритмов и структур данных, а именно стека
Это задача не на стек нихуя. Поздравляю, ты нихуя не понимаешь что такое стек и какие у него свойства.
Нам в этой задаче нахуй не надо знать детали каждого элемента на стеке, достаточно осознания что скобки друг друга закрывают и одного счетчика для их подсчета.
>>259988660 (OP) в целом это тебе базовую идею стека дают, скажем какая нибудь польская запись - считай та же самая идея, не парся анон, по началу всем непросто, учи и выучишь - гарантирую
>>259992670 Дурачек ебанутый, не бомби, я во-первых, не с тобой разговаривал и вообще просто подбодрил чела. Грамматику в две строчки даже для этого стоит написать просто для того чтоб легче код было составить. А свою душноту ну тут все просто это тривиально и тд на собесе мне расскажешь, тут мне хуету написывать не надо, не интересно
>>259988660 (OP) Корректная скобка начинается с "(" и заканчивается ")", остальное не имеет значения, это же из примеров видно. Джуниоры ёбаные, счетчики какие-то придумывают, циклы...
>>259988660 (OP) Ну 3 часа это еще нихуево, я именно на эту задачу вообще весь вечер потратил когда учился. Не ссы, это нормально. мимо 250к/мес дата сайнс питонист без рофла
>>259992778 Ты прав, у меня просто сознание извращено литкодом и техническими интервью, и я подразумевал, что следующим вопросом будет "а что если скобочки будут разными?" Для задачи из ОП-пика стек не нужен.
>>259992913 Да какого стека, нахуй тут стек не нужен -- наоборот детект дебила, который не знает для чего полезен стек. Одно дело польская запись, когда тебе реально на стеке надо детали какие-то хранить, а потом при обходе обрабатывать. Другое дело тут, когда можно счетчик воткнуть.
>>259992979 Хоспаде, как же я люблю безграмотных дебилов, которые несут какую-то хуету, а потом жалуются что им "душно", когда их закономерно покрывают хуями за их хуйню.
Пиздец, грамматику он собрался "писать", чтобы скобки балансировать, что за клоун, а.
>>259988660 (OP) > нужно иметь очень высокий интеллект, чтобы вкатиться в программирование и сильные математические способности Нет, достаточно иметь средний интеллект, внимательность и усидчивость. Но программирование весьма жестоко в этих требованиях. Если твой интеллект НИЖЕ среднего, то это сразу всё, ловить тебе тут нечего. От тебя требуется понимать множество довольно простых вещей, но у тебя при этом нет права на затуп. Да, эти вещи простые, но если ты что-то не сможешь понять, то тебе никто не поможет, а без этого понимания ты не сможешь двигаться дальше. Тут нельзя сказать "хуй с ним" и надеяться, что результат просто будет чуть хуже, что потом можно будет скомпенсировать опытом. Про математические способности это вообще смешно, говорю, как чел с топ математическими способностями (если конечно ты не имеешь ввиду способность посчитать "2 + 2 х 2") >>259989053 Посмотрел бы на такую олимпиаду, лол. Это задача на отработку синтаксиса языка: циклов и условий. Автор, наверное, даже не подозревал, что для кого-то станет проблемой сама логика задачи
>>259993104 Сам ты дебил и джун. И если мне внезапно на интервью попытаются эту хуету развить в стек, я сразу же оттуда съябусь, ибо понятно что передо мной оказался студентик, который про структуры данных прочитал, а подсчитывать сложность алгоритма не научился.
>>259991754 А теперь представь, что у тебя сначала идёт пять закрывающих скобок подряд, а потом пять открывающих. По твоей программе это будет правильной последовательностью, поскольку в сумме счётчик будет ноль. Мимо решал задачу посложнее на Олимпиаде
>>259993088 Ладно, я тупой, задача была про скобочную последовательность , а не про то, что правильно были использованы скобки, невнимательно прочел. Спасибо автору за то, что убирает мне конкуренцию, понижая вкатунам самооценку и давай задачки, которых не почти никогда бывает в реальности.
>>259993388 Иди про O(n) почитай, вкатывальщик. Без понимания этой истории все твои "знания" про структуры данных -- говно полнейшее. Ты же даже не понимаешь как оценить объективно какая структура и подход для какого кейса лучше.
>>259993400 Через нейронку прогнал по фасту, ну есть пару либ для питона, хз как по другому решать, задача не из простых, очевидно. Макбук чуть не перегрелся.
тупое решение - гоняем цикл, каждый раз заменяя "()" на "". если невозможно - все, выводим фалс. О(n^n/2) сложность.
хитрое - 2 счетчика. первое - проверка четности лен(стр). нечетное - фалс. левые и правые. проход слева. считаем левые, вычитаем из них правые. если сумма меньше нуля - брейкаем, фалс.
>>259992353 Ну так вот. Знать надо просто овердохуища, чтобы попасть на эту не самую оплачиваемую работу. В любую другую профессию вкат не требует такого адового задрачивания.
>>259993231 Так ты сам кринжовую хуйню высираешь, у тебя логика макаки формошлепа который бежит сразу формошлепить. Тебе вопрос зададут как задачу решать, ты в слух грамматику озвучишь и все, вопросов вообще к тебе не будет. Не понимаю в чем тут проблема, может ты взорвался из-за незнакомых слов? Не знаешь как грамматику составить для этого тривиального случая?
>>259993237 Кому ты пиздишь, маня, эта задача не решается циклами или регулярками. Там надо через стек все это прокидывать. Процесс буквально тот же самый, что в интерпретаторах япов, эту задачу рассматривают на курсе компиляторов/интерпретаторов.
>>259993396 Чел, не ебись в глаза > На каждой итерации проверяешь, счетчик меньше нуля - брейк. На твоей последовательности счетчик на первой же закрывающей скобке уйдет в минус, цикл вылетит, счетчик не равен нулю. Фолс.
>>259988660 (OP) Решается за 1 минуту, если скобка открывающая, пихаем в стек, если закрывающая, то вынимаем из стека, если вынуть не можем, фейл, если в конце стек непустой, фейл. Все. Любой прочитавший одну книгу по написанию компиляторов это знает.
>>259988885 Долбоебик, засада выполняет свою работу. Тот, кто не может ее решить на практике никому нахуй не нужен. Ору с погромистов с нулевым интеллектом.
>>259990406 def isvalid(str): if len(s) % 2 != 0: return False else: n = len(s) while n >= len(s): s = s.replace('()','') s = s.replace('{}','') s = s.replace('[]','') n -= 2 return bool(s) is False
>>259988660 (OP) Мб я чего-то не понял, но вроде не такая сложная задача, чтобы прям 3 часа решать. Вот накидал минут за 10 на c#:
using System;
public class HelloWorld { public static void Main() { Console.WriteLine(is_correct_bracket("()(()())").ToString()); Console.WriteLine(is_correct_bracket(")(())(").ToString()); }
static bool is_correct_bracket(string text) { int closedDifference = 0;
for (int i = 0; i < text.Length; i++) { if (text.ToString() == "(") { closedDifference++; } else { closedDifference--; }
Вроде просто все, и правильное решение уже писали выше
Единственный проход по циклу, таким образом алгоритм линеен
Счетчик наращивается или уменьшается на каждом символе. Для ( он увеличивается, для ) уменьшается. Если значение счетчика в любой момент стало отрицательным, то False. В конце счетчик должен быть равен нулю, иначе False
>>259993659 >Ну так вот. Знать надо просто овердохуища, чтобы попасть на эту не самую оплачиваемую работу. В любую другую профессию вкат не требует такого адового задрачивания.
Ну дак вкатывайся в любую другую сферу, в чем смысл твоего нытья?
>>259988660 (OP) Ты довен? Через стэк за 5 минут пишеться решение. Всё открывающие суем в него, если закрывающая снимаем вершину. Если стек в конце больше 0 false
>>259995181 ну типа какой у тебя стек - какие языки знаешь, фреймворки, фронтэнд/бекенд, умеешь ли работать с базами данных. Вот это все. Кто все умеют, тех называют фуллстек.
>>259995181 Представь магазин для АК. Это и есть стек. Снаряжаешь патрон - делаешь push(). Вынимаешь или выстреливаешь патрон - делаешь pop(). Т.е. операции всегда только с верхним (последним) патроном.
>>259991298 Предлагаю мой дебильный способ решения В чём суть. Создаем массив правильных скобок индуктивным способом, начиная от n=2 прибавляю к предыдущему скобку () по бокам или (+предыдущие скобки+), далее входящую скобку сравниваем со значениями массива правильных скобок, если значение не найдено то False, иначе True. Плюс, выводит массив правильных скобок. Знаю, способ не эффективный, долгий и требует использование памяти, но хотя бы более наглядный
>>259995179 ну хер знает. к каждой откр скобке есть закр скобка и так двигаться по строке +1 символ вперед. сначала с первого символа потом со второго, с третьего. разве так нельзя исключить все закрытые пары?
поэтому вас очкариков зазнавшихся никто и не любит, сидите в своих интернетах выёбываетесь своими специализированными знаниями, а при малейшем вопросе включаете тролля
>>259994271 Сука и ебаные нытики все такие Посмотреть ебучий учебник? Попросить совета что нужно знать чтоб решить это говно? Нахуй НУЖНО НАНЫТЬ ПРОСТЫНЮ И ЗАПОСТИТЬ УЕБАНСКИХ ЛЯГУХ
>>259995598 ну вообще там стек, ты ж вставляешь в рожок патрон сверху и он двигает остальные вниз. самый просто пример стека ( что дословно переводится как сука СТОПКА) - это сложенные друг в друга тарелки. Кладешь наверх, берешь верхнюю всегда
>>259988660 (OP) А что в ней трудного? У тебя счетчик открытых скобочек изначально равен нулю. Идешь по строке. Встретил открывыющую скобку - увелчил счетчик на 1. Встретил закрывающую - уменьшил на 1. В случае если счетчик стал меньше 0 - прервал выполнение(т.к. сразу понятно, что получил невалидную строку). В конце - если счетчик не 0 - строка невалидна.
Что-то судя по треду реально проще просто импортировать тенсорфлоу Написать 2х слойную денс-сетку показать ей 50 примеров и потом просто делать предикт тех что даны для проверки дата-сатанист, не ебу как это решать классически
>>259993735 > ты в слух грамматику озвучишь и все, вопросов вообще к тебе не будет. Не понимаю в чем тут проблема
Да потому что ты дурак и пытаешься натянуть сову на глобус, вбив себе в голову, что это аж целая задача парсинга какой-то формальной грамматики, ещё и с умным видом потом пердя про формошлепство. Ты бы ещё нейронками начал решать и доказывать, что это задача якобы на то чтобы ты вслух про лингвистические модели сказал. То что ты предлагаешь -- это и есть логика формошлепа. Они вон тоже выучивают одну функцию одного фреймворка и используют её везде, к месту и не к месту.
> незнакомых слов > грамматику составить Клоун безграмотный, грамматику не "составляют", её описывают в какой-нибудь стандартной нотации, а дальше парсерами/лексерами/токенайзерами реализуют её обработку.
>>259988660 (OP) Хуй знает, одна из самых лёггких задач, котору. можно получить на собесе. Эта задача на знание стека. Мне на прошлом собесе такое дали. Ну тут на знание рекурсии:
// ЗАДАЧА:
// Определить количество замкнутых несвязанных между собою пустот (дырок) в лабиринте размера NM
// 1 <= N <= 200, 1 <= M <= 200
//
// ВХОД:
// Текстовый файл, содержащий массив NM в виде строк (т.е. N строк, каждая длиной M символов)
// Число замкнутых несвязанных между собою пустот (дырок) в переданном во входном файле лабиринте.
// // ПОЯСНЕНИЕ: // Пустота считается несвязанной с другими, если у неё нет смежных с другой пустотой клеток // по горизонтали или вертикали. Т.е. из одной пустоты нельзя перейти в другую пустоту // двигаясь по любой траектории и делая шаги по горизонтали и/или вертикали. // // Важно! Необходимо учитывать только пустоты, замкнутые стенами лабиринта со всех сторон! //
// ВЫХОД: // Вывести исходный файл и под ним - найденное число пустот. // Или вывести сообщение об ошибке, если входной файл некорректен. //
Короче, надо следить за тем, чтобы количество открывающих и закрывающих скобок на каждом уровне было одинаковым. Например, при каждой новой открывающей скобке повышаем уровень на 1 и в рамках этого уровня считаем скобки, их общий баланс должен быть равен нулю. Если где-то в массиве получился не ноль, то скобки не равны
>>259991855 С квадратным - придется таки стек использовать. Встретили открывающую - положили на стек. Встретили закрывающую, достали из стека, если она не того же типа - сразу вышли. В конце проверяем, осталось ли что-то на стеке и прошли ли мы всю строку.
Вот еще задачка на знание механизма соединений в SQL хорошая.
ДАНО: - ТаблицаЦен, в которой хранится товар, цена на товар и дата установки цены на негго. ТОВАР | ЦЕНА | ДАТА УСТАНОВКИ ЦЕНЫ (эта цена действует до следующей установки цен) - ТаблицаПродажТоваров, в которой хранится товар и дата продажи ТОВАР | ДАТА ПРОДАЖИ
НУЖНО: Написать запрос, который получит цену продажи товара (если на это время еще цена не была установлена, то считаем, что цена продажи равна 0). Должна получится таблица: ТОВАР | ДАТА ПРОДАЖИ | ЦЕНА ПРОДАЖИ
>>259996503 Просто сделай замену квадратных/фигурных на круглые Получишь все круглые(т.е. приведёшь данные к одному виду) и сделаешь тоже самое, что и в ситуации, когда все скобки однотипные
В худшем случае у тебя использование памяти со стеком будет O(n) -- потоковую обработку ты так вообще не сможешь сделать, банально потому что у тебя память кончится, на потоке из "...(((((((((((((((...", потому что ты их за каким-то невидомым хером хочешь сохранять.
С обычным интовым счетчиком и инкрементом-декрементом заместо операций со стеком ты получаешь O(1) по потреблению памяти -- можешь хоть бесконечный поток скобок в него пулять, память никогда не кончится (ну, условно до момента когда счетчик уйдет в MAX_INT, если у тебя рантайм без длинной арифметики).
Ты банально лишнее говно в виде целого стека в памяти хранишь, потому что используешь тупо для того, чтобы кол-во плиточек посчитать, но для этого прекрасно обычный счетчик подходит и всё.
Стек нужен только когда тебя в деталях ебет содержимое плиточек, но это не тот случай.
Распарсить польскую нотацию -- там да, там нужен стек, ибо тебе надо сначала установить последовательность операций (построить стек), а потом выполнить их (пройтись по содержимому стека).
>>259996259 Это не натягивание совы, это просто класс задач, по грамматике лл1, составляешь грамматику в строчку и пишешь код по ней, все, есть чуть более сложные из той же оперы, что ты тогда делать будешь? Костыли свои дебильные городить? Ну раз тебе нравится решать задачу из этого класса как костыльному школьнику - решай, мне то что? Ну просто я бы сделал вывод о тебе что ты не понимаешь \ не знаешь какие то обычный вещи. Нахуя ты тут мне что-то доказываешь так упорно пытаясь хоть как-то сумничать - я в недоумении
>>259996670 Ты таким макаром увеличиваешь время выполнения своей хуйни. В строке с 1_000_000 символов - ты сначала должен пройтись и все заменить, а потом уже выполнять алгоритм подсчета. Неэффективно это, короче. А тут четко за O(n).
SELECT ТаблицаПродажТоваров.ТОВАР, ТаблицаЦен.ЦЕНА, ТаблицаПродажТоваров.ДАТА ПРОДАЖИ FROM ТаблицаЦен, ТаблицаПродажТоваров WHERE ТаблицаПродажТоваров.ТОВАР = ТаблицаЦен.ТОВАР ORDER BY ТаблицаПродажТоваров.ТОВАР;
>>259996656 Чел, я сам 1Сник. Эта задачка для собесов учебная. Ты такой же запрос будешь писать, если, например, нужно будет не цену продажи получить, а прибыль рассчитать, используя закупочную цену в качестве себбестоимости с детализацией до документа. И часто срез последних нужно получить на каждый документ. Виртуальная таблица тебе тут не поможет. Руками будешь срез делать.
>>259996846 И зачем ты все цены вытащил ? Надо цену получить на дату продажи. В таблице цен на каждый товар может кучу цен быть. Нужно узнать, какая была цена в момент продажи.
Да и даже тут можно было без декартова произведения обойтись, а соединение хотя бы элементарное сделать, но оно один хер не будет работать. Тут без джоинов никак не решить. Притом джоин нужно делать саму с собой по датам, используя > "больше".
>>259996534 select ТаблицаПродажТоваров.ТОВАР as t, ТаблицаПродажТоваров.ДАТА ПРОДАЖИ, (select ТаблицаЦен.ЦЕНА where ТаблицаЦен.ТОВАР = t) order by ТаблицаПродажТоваров.ДАТА ПРОДАЖИ desc;
>>259996787 > Это не натягивание совы, это просто класс задач
Но это не тот класс задач, который ты пытаешься натянуть, вот и всё. Ты можешь пытаться делать какие угодно выводы, но лично я после таких вопросов сделаю вывод, что ты сам нихуя не понимаешь о чем говоришь и пытаешься "модную и крутую" штуку, про которую на хабре прочитал, безграмотно натянуть на абсолютно нерелевантную ей задачу балансировки скобок.
А делаю я такой вывод, потому что, еслиб ты вообще понимал что это и какие задачи решает, ты бы использовал её по назначению и задачи придумывал бы соответствующие с соответствующими констрейнами. Но раз у тебя грамматика -- это для решения задачи балансировки скобок, значит ты банально не понимаешь проблем, которые такая абстракция решает.
>>259996787 > Нахуя ты тут мне что-то доказываешь так упорно пытаясь хоть как-то сумничать > Грамматика для балансировки скобок > упорно пытаясь хоть как-то сумничать
>>259996891 Хуйта какая-то. Я конечно понимаю что в условии обычно не сказано, что между скобками могут быть какие-то произвольные символы, но всё-таки.
>>259997491 Да я знаю, я просто к тому что это вообще-то очень стандартная проблема, которая предполагает именно наличия промежуточного говна между скобками.
>>259997295 Ахах "модную и крутую" на хабре - это как раз про твоё понимание что такое лл1 и какие задачи ею решаются. Дружище че ты так рвешься то? Решение что по школьному, что по нормальному как это делают люди - одинаковы просты, тут даже и совы то нет которую ты мне тут приплести пытаешься. Почему это тебя так злит?
>>259997838 > Мы не ограничены А, ну раз вы не ограничены...
> Вопрос всё ещё тот же Чтобы писать программы грамотно, а не как попало, работающие только в определенных абстрактных условиях в вакууме с большими ограничениями. Нет, для вкатывальшика наверно круто научиться решать задачи хоть как-то, но вкатывальщики на то и вкатывальщики, что поголовно хуесосы безграмотные.
>>259994504 Во-первых, условие коряво сформулировано, если следовать ему буквально, то все решается простым перебором и сравнением количества. Во-вторых, ничего сложного, если ты кодингом ни одну неделю занимаешься. И в плюсах ничего слоэного нет. Если, как вы говорите последовательность ")(" хуевая, то в решении тоже ничего сложного.
создаем вектор флагов; начинаем парсить строку; если попадается '(' пушбэкаем флаг в вектор; если попадается ')' при пустом векторе, сразу нахуй такую строку, возвращаем ложь; если попадается ')' при непустом векторе, попаем вектор; если после перебора строки вектор непустой возвращшаем ложь, иначе истину;
>>259998050 А где ты в формулировке задачи увидел разрешение на допущение, что входных данных у тебя мало? Ты никогда таких задач не решал что ли? Тебе даются 1.5 простых примера, а потом автотест гоняет твою программу на ебейше огромных строках, чтобы увидеть что она отвалилась.
>>259998159 Ну тут вопрос к составителю задачи, почему она получилось такой, что в итоге ничему тебя не учит.
>>259998196 >>259998271 А ну да, я просто условие задачи не читал, ну в таком случае идём по строке циклом, если отсчёт начинается с ) - false, если, количество ) превысило количество количество (, в следующей итерации , то же false, ну я бы так делал.
>>259988660 (OP) Дегенерат, хули там решать, ( скобка делаешь к счетчику +1, ) — делаешь –1 Если меньше нуля на каком-то этапе произошло, то неправильная, если к концу строки не 0 — тоже
>>259988660 (OP) Самая первая мысль котоая пришла в голову, просто почтитать количество открвающих и закрывающих скороб и если оно не равно, значит нерпавильная стока. Это без всяких оптимизация, просто в лоб.
>>259997865 "Модную и крутую" -- это про логику формошлёпа, которому модным и "интересным" реактом захотелось решать задачу вывода статического текста.
Не нужно никаких безконтекстных грамматик, Бэкуса-Наура, синтакс-деревьев и прочей хуеты, чтобы решать задачу балансировки скобок. Это просто банально не та задача.
Если ты таких простых вещей не понимаешь, значит и какие задачи решаются.
И это кстати LR-ом решать надо, а не LL-ом, даже тут ты обосрался.
>>259998710 Почти так, считаешь кол-во открытых скобок и вычитаешь из него закрытые. На каждой итерации ещё нужно проверять, чтобы счетчик не стал меньше 0 (т.е. закрывающая скобка не появилась раньше открывающей) -- а то отвалится на примерах, которые тебе в соседних ответах накидали.
>>259998661 Ты тупой? >) — делаешь –1 >Если меньше нуля на каком-то этапе произошло, то неправильная >)( >) >меньше нуля >false Ебало так что стянул, зелень ебаная
>>259998988 Нет необходимости считать открытые и закрытые скобки отдельными счетчиками. Просто открытые добавляешь, а закрытые вычитаешь из общего счетчика. На каждой итерации считаешь, не ушел ли счетчик ниже 0.
>>259998661 >>259998903 Ну вообще он прав, т.к. у него есть условие > Если меньше нуля на каком-то этапе произошло, то неправильная На твоих примерах счётчик будет меньше нуля прям с первого символа и соот-но будет досрочный false
Так что не бомби, второкурсник, а учись адекватно общаться, даже если твой оппонент не прав хотя в данном случае неправ ТЫ, пригодится в жизни и на работе
>>259999400 Не-не, тебе не нужно два счетчика. Просто в один добавляешь открытые и вычитаешь закрытые. В итоге он должен быть равен нулю и никогда не опускаться ниже 0 в процессе обхода строки.
>>259988660 (OP) Встречал такую задачу на тесте для позиции джуна. Действительно, весьма обычная задача. Если с решением таких задач сложности - в программировании вам будет очень тяжело. Решений такого рода задач вагон. Если тебе не приходит в голову ни одно - это плохо. Нормально, если ты придумал решение, а тебе говорят, мол, ты не учел вот этой хуйни. И ты такой "а, точно, тогда поменять надо... Вот, например, так" Потом ещё что-то подмечают. Опять исправляешь. И вот так, постепенно приходишь к весьма неплохому решению. Вовсе не обязательно нагора выдавать идеальное решение. Главное, уметь думать и находить решение появляющимся проблемам. Сейчас, от балды, я бы решал как-то так def is_correct_bracket(s): ... counter = 0 ... for char in s: ... if char == '(': ... counter += 1 ... elif char == ')': ... counter -= 1 ... if counter < 0: ... return False ... return counter == 0
>>259998336 Какой менеджер ёпта ? Это учебная задача. Подобная логика встречается в реальной практике. Просто там настоебенино всего. Тут в минимальных терминах описано. Это проверка на понимания работы соединений.
Вот те скрин-пример рабочий, что на днях делал отчёт с подобной логикой, но суть тут другая совсем. Для менеджеров ёпта. Они посмотрели, сказали всё ок. Тута надо было и продажи за последние N месяца получить относительно текущего. И стоимость единицы товара узнать. И всё это на каждый месяц. А колонки с месяцами динамически тоже заполняются. Какой период пользователь задаст.
>>259988660 (OP) >>259999395 >>259999563 Бтв, я бы решил эту задачу таким образом. Данные в массив, две интегер переменные, равные половине участников массива. Брал бы из верхней половины массива скобку и искал бы ей пару в нижней половине массива, отбавляя по единице из каждого массива, если пары сошлись. И двигаясь вперёд до нахождения внутренней пары, если пара не нашлась. При этом задействуется подфункция, которая создаёт новый массив из всего промежутка до нахождения пары, если внутренний промежуток, который работает по тем же принципам что и основная программа(раздел на два и поиск пары).
>>259999950 Да не общайся, кто тебя заставляет-то. Лулзов ты уже нагенерил, своим томным кокетством и попытками сумничать штуками, которые ты не понимаешь нихуя.
>>259992607 >>259992582 К программированию вообще отношения не имею лул) Ну да Тогда единственная переменная-счётчик. В случае если она не равна 0, плюсует при '(' и минусует при ')' Если же = 0 и встречается ')' автоматом выдает фолс
>>259999831 Хуйню бы дало. Не понял условий нормально. Значит перебрал бы массив char, где нулевым элементом должен быть "(", а конечным ")", и считал при переборе в две переменных количество этих элементов, в конце бы их сравнил.
>>259988660 (OP) В питоне нет функций работающий со строчками которые определяют количество символов в строке? Могут брать символы из левой части строки? Не могут обращаться к конкретному символу в строке по номеру?
>>259988660 (OP) Люблю алгоритмические задачи. Алсо, помню писал парсер для калькулятора, который будет учитывать скобки и даже функции типа косинусов и синусов. Вот это весело было. Познакомился тогда с алгоритмом обратной польской записи.
>>260000711 >определяют количество символов в строке? Есть такая функция >Могут брать символы из левой части строки? Могут >могут обращаться к конкретному символу в строке по номеру? Могут
>>260000612 Да я же не там именно работаю. Это один из десятков клиентов. Да и вообще я увольняюсь, с НГ буду работать в московское конторе по удалёнке
>>260001316 Этот чмоха. >>260000900 Этот был бы прав, если бы нам не было бы похуй на то, что внутри. Мб там какой-нить код будет, нахуя трогать то, что трогать не нужно?
Вы оба опущенные петухи, пошли нахуй с моей профессии.
>>259988660 (OP) Считаешь в один цикл скобки правые и левые в две разные переменные, обрываешь если наткнёшься на другой символ и выдаешь false. Сравниваешь, если поровну - ture, иначе false.
Проверить первую и закрывающую скобку. Если первая ) или закрывающая ( - фалс. Затем посчитать общее количество ( скобок и сравнить с длинной строки/2. Если не равно - фалс. Это при условии что у нас строка из скобок онли. Если в строке может прийти что-то другое, то сперва пройти и проверить на символы ( или ). Решаю, пока пишу этот итт пост.
>>259988660 (OP) Так бля, а в чем проблема, тип запускаешь циул, за каждую открывающую +1, за каждую закрывающую -1 и в конце проверочка на отрицательность. Блять в 10 строк уложиться можно.
>>259991018 >>259990945 >>259990931 Пацаны, но стек же надо отдельно реализовывать, в питоне его не существует насколько я знаю. Дел на несколько строчек, конечно. Тут в треде простейшее решение, где просто при скобке "(" += 1 к счетчику, при ")" -= 1, если счетчик где-то < 0 или в конце счетчик != 0, то False. Вероятно, это дольше, чем через стек. мимо пробегал
>>260001846 Блять, микропчелик, нахуя мне иметь контакты с кабанчиками и терпеть их охуительные прихоти, типо отчётов о проделанной работе и охуительных комментариев к коду, когда я получаю +сабжи с дженерик онлайн дрочилен для детей-аутистов? Раньше я поставил бота для общения с тупыми пендосами на апворке, но меня за это пидорнули. Похуй, ебал в рот людишек.
>>259996892 >я сам 1Сник О, подскажи, пожалуйста, все 1Сники тупые мрази с завышенным чсв, или мне просто только на таких везло? Как не приходится с каким-нить 1Сником по работе пересекаться, вечно хуярят какой-то говнокод, при этом гонору яебал. Сука, простой круд могут месяц писать, нихуя не тестируют, но всегда свысока отвечают, когда их в собственные косяки носом тычешь.
>>260001670 Лучше так - идешь в одним цикле по массиву, если скобка открывается, то увеличиваешь счетчик, если закрывается - уменьшаешь. Если в какой-то момент счетчик меньше 0, то return false т.к. встретилась закрывающая скобка, для которой слева нет открывающей. Ну и если до конца дошли, то return counter == 0
>>260002293 Психологи это наебалово для тупорогого скота, т.е. гоев. Ты нихуя в этой жизни не понимаешь и не поймёшь, забей, продолжай прозябать в рабстве. Я не осуждаю, такая у кого-то жизнь, кому-то презирать говно, кому то в этом говне купаться.
>>260002347 Лучше так - идешь в одним цикле по массиву, если скобка открывается, то увеличиваешь счетчик, если закрывается - уменьшаешь. Если в какой-то момент счетчик меньше 0, то return false т.к. встретилась закрывающая скобка, для которой слева нет открывающей. Ну и если до конца дошли, то я ебу твою мамашу.
>>259988660 (OP) Хуйня без задач для олимпиадников, лучше сайт сделай или программку типа конструктр расписания для вуза или что-то подобное, больше пользы будет и не почувствуешь себя дебилом, решая дебильные задачи без практической нагрузки.
>>260001922 Тогда делаем два счетчика и идем сначала по строке. Фалс вернется тогда, когда счетчик ) превысит (, или когда счетчик какой-то скобки будет больше половины длины строки, или когда символ будет не ( или ).
>>259991109 Нет, не всё так просто: ([{])} - тут каждый вид скобок вроде последовательно открывается/закрывается, но последовательность неверная. Я бы сделал это рекурсией
>>260002486 >>260002546 >>260002582 А в практических задачах не появляется необходимость обращаться к алгоритмам и одновременно извлекать пользу и развивать быстроту мышления и память?
>>260002729 Так тут надо стратки знать, т.е. уже иметь опыт решения подобных задач, тогда будешь на изи решать. Интуитивно догадаться, что если число скобок закрывающих в ближайшем сегменте, то эта хуйня сломана, очередняре довольно трудно. Однако если один раз ему показать, то уже всё сразу поймёт.
>>260002180 С точки зрения скорости работы алгоритма. Одни ифы это не круто и в целом не очень умно. Но я не анализировал код, так что лишь предположение >>260002313 >>260002263 Когда читал про алгоритм на стеке, тоже пытался подобрать варианты, в которых скобки были бы неправильными. Но алгоритм должен работать.
Легкая же задача. Извлекаем из строки () до тех пор, пока от неё ничего не останется (true), или будет нечего извлекать, но строка будет непустой (false)
>>260004541 >С точки зрения скорости работы алгоритма С точки зрения О: Со стеком ты кладешь в стек, проводишь операцию сравнения. Со счетчиком ты проводишь операцию сравнения и инкрементируешь счетчик. Ты считаешь, что инкрементировать число это дольше, чем поместить объект в стек? Ифы у тебя один хуй будут в обоих случаях. Только со счетчиком тебе не надо тратить дополнительный объем памяти под стек, создавать стек и удалять стек после завершения.
>>259999852 Да исходную тоже лучше через стэк. Если мне на собеседование ещё начнут затирать как долбоебы выше что стэк увеличит выч сложность вообще сразу закончу разговор.
Счётчик это решение конкретно 1 задачи в одном случае, уровень решение студента на лабе. Стэк это решение всего класса задач. Неважно что там на входе такой алгоритм подходит для любой пары символов, знай себе в конфигурации их пропиши. Даже @({})\/[]##(##)[!!]@. Буквально пара секунд на внести правки в конфиг.
Это банально лакмус долбоебов которые дальше прям сейчас не думают. Решение через стэк не сложно написать, не сложно поддерживать и оно очень гибкое.
>>259988660 (OP) Сдаётся мне, что ОП давно уже работает программистом, а тред сощдан, чтобы посмеятся над вкатунами и заводчанинами, мол вот глядите какие работяги тупые, погромирование это только для элит интеллектуальных. Вообщем ОП - хуй и мулак с завышенным ЧСВ.