24.06.2019, 23:08
|
Аспирант
|
|
Регистрация: 02.02.2019
Сообщений: 67
|
|
Какую можно применить сортировку комбинаций из 2х значений
Например есть вот такие строки
"[ x] x] [ x]x ]"
Из них можно получить вот такие комбинации
"[ x x [ x] x ]"
"[ x x] [ xx ]"
вот строка
[ ] x ] x]
получить можно такие строки
[ ] x x
[ x ] x
[ x x]
Какой подход можно применить.
То есть одной [ должна соответствовать закрывающая скобка. ]
Я пробовал 2 вложенных for, но все комбинации не смог получить.
На выходе, каждый раз коллекция добавляется в коллекцию, которая позволяет записывать в себя только уникальные элементы (но это уже можно и не решать)
на случай если не понятно, при каждом проходе, если есть несколько подряд идущих скобок,
так вот, они должны удаляться шаг за шагом из своих позиций и должна оставаться только парная, если между ними есть символы, то четко видно что они сдвигаются.
пробелы сделал для удобства, они там не нужны.
можно либо удалять лишние скобки и результат коллекции записывать в другую коллекцию(которая позоволяет добавлять уникальные элементы) , либо результат сразу записывать в некий буфер в течение итерации внутреннего цикла и в конце внешнего, результат буфера затем добавлять в общую коллекцию.
Как можно решить данную задачу ?
|
|
25.06.2019, 07:56
|
|
CacheVar
|
|
Регистрация: 19.08.2010
Сообщений: 14,228
|
|
Сообщение от alex-romanov
|
Как можно решить данную задачу ?
|
Если я правильно понял, из исходных строк можно убирать любое количество любых скобок. Но "правильными" являются строки в которых скобки "синтаксически" правильные, даже если внутри скобок "пусто".
Так?
|
|
25.06.2019, 07:59
|
|
CacheVar
|
|
Регистрация: 19.08.2010
Сообщений: 14,228
|
|
Сообщение от alex-romanov
|
Я пробовал 2 вложенных for, но все комбинации не смог получить.
|
Для получения всех комбинаций циклов нужно столько, сколько скобок.
|
|
25.06.2019, 09:18
|
Аспирант
|
|
Регистрация: 02.02.2019
Сообщений: 67
|
|
Сообщение от ksa
|
Если я правильно понял, из исходных строк можно убирать любое количество любых скобок. Но "правильными" являются строки в которых скобки "синтаксически" правильные, даже если внутри скобок "пусто".
Так?
|
это анализатор кода
у каждого метода открывающего, есть закрывающий, методы обозначены
в виде скобок для удобства.
[ ] ] [ ] ]
[] []
[ [ ] ]
(пробелы для удобства)
когда попадается вот такая входная строка
[ x ] x ] x]
варианты вот такие (вот какое множество получается на выходе)
[ x x x]
[ x x ] x
[ x ]x x
Здесь видно, что скобки удалются со своих позиций и каждый раз оставляется одна закрывающая скобка, чтобы результат был валидным.
Входная строка может быть длиннее, но всегда правило:
-Открывающей скобке должна быть пара,
-эти пары могут быть вложены одна в другую
- все остальные символы отличные от этих скобок, должны добавляться в исходный результат без изменений.
Кроме того если
|
|
25.06.2019, 09:24
|
Аспирант
|
|
Регистрация: 02.02.2019
Сообщений: 67
|
|
Сообщение от ksa
|
Для получения всех комбинаций циклов нужно столько, сколько скобок.
|
Я делал циклы по числу пар, но ничего не получается. Я лишь только подстроился к результату, а это неверно.
вот приблизительный код (здесь другой язык, но думаю понятно будет)
private static Set<String> getSetCombinations(List<String> list, int numberOfMethodsPairs) {
Set<String> stringsSet = new HashSet<>();
StringBuilder builder = new StringBuilder();
boolean isPair = false;
boolean isLock = false;
int countPair = 0;
builder = new StringBuilder();
/*работа с методами unlock. В качестве ограничителя
* смотриться количество методов unlock идущих подряд */
for (int k = 0; k < list.size(); k++) {
String element = list.get(k);
if (addRestOfCode(element, builder)) {
continue;
}
if (element.equals(LOCK) && !isLock && countPair != numberOfMethodsPairs) {
builder.append(element);
isLock = true;
isPair = false;
countPair++;
}
if (element.equals(UNLOCK) && !isPair) {
builder.append(element);
isLock = false;
isPair = true;
}
}
String stringSet = builder.toString();
if (builder.length() != 0) {
stringsSet.add(stringSet);
}
return stringsSet;
}
|
|
25.06.2019, 09:27
|
Аспирант
|
|
Регистрация: 02.02.2019
Сообщений: 67
|
|
вот входная строка
String[] inputStrings = {
"{}}{}}", "{{{{{{", "}cfd{{{{{}",
"}cfd{{{}{{}", "{{{}{{}}}}}", "a{x}x}{}}",
"{}}{}}", "{{{}}{}}", "{}d}d}}{}h}}}", "{}}{}}"
};
вот от такого варианта
"{}}{}}"
, я только получаю
{}{}
|
|
25.06.2019, 10:05
|
|
CacheVar
|
|
Регистрация: 19.08.2010
Сообщений: 14,228
|
|
alex-romanov, пишешь много, но не особо проясняешь ситуацию...
Вот сделал набросок по проблеме как я ее понял и описал выше.
var str='[ ] x ] x]';
var re=/\[|\]/;
var arr=[];
test(str);
alert(str+'\n'+arr);
str='[ x] x] [ x]x ]';
arr=[];
test(str);
alert(str+'\n'+arr);
function test(Str){
ok(Str);
var n=Str.split(re).length-1;
var str;
for (var i=0; i<n; i++) {
str=del(Str,i);
if (re.test(str)) {
test(str);
};
};
};
function del(Str,Pos) {
var str=Str.replace(/\[|\]/g,'|');
var pos=0;
var d=0;
for (var i=0; i<Pos+1; i++) {
pos=str.indexOf('|',pos+d);
if (pos==-1) {
return Str;
};
d=1;
};
str=Str.substring(0,pos);
str+=Str.substring(pos+1);
return str;
};
function ok(Str){
if (arr.indexOf(Str)!=-1) {
return false;
};
var val;
var a=0;
var b=0;
for (var i=0;i<Str.length; i++) {
val=Str.charAt(i)
if (val=='[') {
a++;
};
if (val==']') {
b++;
};
if (b>a) {
return false;
};
};
if (a!=b) {
return false;
};
arr[arr.length]=Str;
return true;
};
Что в итоге нужно тебе, я так и не понял...
|
|
25.06.2019, 10:11
|
|
CacheVar
|
|
Регистрация: 19.08.2010
Сообщений: 14,228
|
|
Сообщение от alex-romanov
|
вот от такого варианта
"{}}{}}"
, я только получаю
{}{}
|
У меня их больше.
var str='[]][]]';
var re=/\[|\]/;
var arr=[];
test(str);
alert(str+'\n'+arr);
str='0[1]2]3[4]5]6';
re=/\[|\]/;
arr=[];
test(str);
alert(str+'\n'+arr);
function test(Str){
ok(Str);
var n=Str.split(re).length-1;
var str;
for (var i=0; i<n; i++) {
str=del(Str,i);
if (re.test(str)) {
test(str);
};
};
};
function del(Str,Pos) {
var str=Str.replace(/\[|\]/g,'|');
var pos=0;
var d=0;
for (var i=0; i<Pos+1; i++) {
pos=str.indexOf('|',pos+d);
if (pos==-1) {
return Str;
};
d=1;
};
str=Str.substring(0,pos);
str+=Str.substring(pos+1);
return str;
};
function ok(Str){
if (arr.indexOf(Str)!=-1) {
return false;
};
var val;
var a=0;
var b=0;
for (var i=0;i<Str.length; i++) {
val=Str.charAt(i)
if (val=='[') {
a++;
};
if (val==']') {
b++;
};
if (b>a) {
return false;
};
};
if (a!=b) {
return false;
};
arr[arr.length]=Str;
return true;
};
|
|
25.06.2019, 10:14
|
|
CacheVar
|
|
Регистрация: 19.08.2010
Сообщений: 14,228
|
|
Сообщение от alex-romanov
|
Я делал циклы по числу пар, но ничего не получается.
|
Я же тебе написал - сколько скобок, столько и циклов. А не пар...
|
|
26.06.2019, 09:29
|
Аспирант
|
|
Регистрация: 02.02.2019
Сообщений: 67
|
|
вот такой вариант имеет максимальное возможное
вот от такого варианта
"{}}{}}"
, должно быть
{}{}
{{ }}
Нельзя убирать парные скобки.
Скобка { , это некий `открывающий` метод)
Скобка }, это некий `закрывающий ` метод)
Сама задача нацелена на создание синтаксического анализатора, который проверяет, что при открытии ресурса, ресурс должен быть закрыт.
Скобки приняты для удобства, чтобы заменить названия открывающего и закрывающего методов.
Да и кстати, я то же не понял что от меня хотели, когда давали эту задачу, вот поэтому и пытаюсь понять.
Сначала думал, что можно взять 2 for и строковый массив проходить с 2- концов друг к другу, составляя пары, но не понятно как затем организовать другие проходы, чтобы сдвигать со своих мест лишнии закрывающие скобки.
В общем спасибо, что пытаетесь помочь
|
|
|
|