Javascript.RU

Создать новую тему Ответ
 
Опции темы Искать в теме
  #1 (permalink)  
Старый 24.06.2019, 23:08
Аспирант
Отправить личное сообщение для alex-romanov Посмотреть профиль Найти все сообщения от alex-romanov
 
Регистрация: 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, но все комбинации не смог получить.


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

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


пробелы сделал для удобства, они там не нужны.

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

Как можно решить данную задачу ?
Ответить с цитированием
  #2 (permalink)  
Старый 25.06.2019, 07:56
Аватар для ksa
ksa ksa вне форума
CacheVar
Отправить личное сообщение для ksa Посмотреть профиль Найти все сообщения от ksa
 
Регистрация: 19.08.2010
Сообщений: 12,431

Сообщение от alex-romanov
Как можно решить данную задачу ?
Если я правильно понял, из исходных строк можно убирать любое количество любых скобок. Но "правильными" являются строки в которых скобки "синтаксически" правильные, даже если внутри скобок "пусто".
Так?
Ответить с цитированием
  #3 (permalink)  
Старый 25.06.2019, 07:59
Аватар для ksa
ksa ksa вне форума
CacheVar
Отправить личное сообщение для ksa Посмотреть профиль Найти все сообщения от ksa
 
Регистрация: 19.08.2010
Сообщений: 12,431

Сообщение от alex-romanov
Я пробовал 2 вложенных for, но все комбинации не смог получить.
Для получения всех комбинаций циклов нужно столько, сколько скобок.
Ответить с цитированием
  #4 (permalink)  
Старый 25.06.2019, 09:18
Аспирант
Отправить личное сообщение для alex-romanov Посмотреть профиль Найти все сообщения от alex-romanov
 
Регистрация: 02.02.2019
Сообщений: 67

Сообщение от ksa Посмотреть сообщение
Если я правильно понял, из исходных строк можно убирать любое количество любых скобок. Но "правильными" являются строки в которых скобки "синтаксически" правильные, даже если внутри скобок "пусто".
Так?
это анализатор кода

у каждого метода открывающего, есть закрывающий, методы обозначены
в виде скобок для удобства.

[ ] ] [ ] ]

[] []

[ [ ] ]

(пробелы для удобства)

когда попадается вот такая входная строка

[ x ] x ] x]


варианты вот такие (вот какое множество получается на выходе)

[ x x x]

[ x x ] x

[ x ]x x

Здесь видно, что скобки удалются со своих позиций и каждый раз оставляется одна закрывающая скобка, чтобы результат был валидным.

Входная строка может быть длиннее, но всегда правило:

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


Кроме того если
Ответить с цитированием
  #5 (permalink)  
Старый 25.06.2019, 09:24
Аспирант
Отправить личное сообщение для alex-romanov Посмотреть профиль Найти все сообщения от alex-romanov
 
Регистрация: 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;
  }
Ответить с цитированием
  #6 (permalink)  
Старый 25.06.2019, 09:27
Аспирант
Отправить личное сообщение для alex-romanov Посмотреть профиль Найти все сообщения от alex-romanov
 
Регистрация: 02.02.2019
Сообщений: 67

вот входная строка

String[] inputStrings = {
      "{}}{}}", "{{{{{{", "}cfd{{{{{}",
      "}cfd{{{}{{}", "{{{}{{}}}}}", "a{x}x}{}}",
      "{}}{}}", "{{{}}{}}", "{}d}d}}{}h}}}", "{}}{}}"
    };


вот от такого варианта

"{}}{}}"

, я только получаю

{}{}
Ответить с цитированием
  #7 (permalink)  
Старый 25.06.2019, 10:05
Аватар для ksa
ksa ksa вне форума
CacheVar
Отправить личное сообщение для ksa Посмотреть профиль Найти все сообщения от ksa
 
Регистрация: 19.08.2010
Сообщений: 12,431

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;
};


Что в итоге нужно тебе, я так и не понял...
Ответить с цитированием
  #8 (permalink)  
Старый 25.06.2019, 10:11
Аватар для ksa
ksa ksa вне форума
CacheVar
Отправить личное сообщение для ksa Посмотреть профиль Найти все сообщения от ksa
 
Регистрация: 19.08.2010
Сообщений: 12,431

Сообщение от 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;
};
Ответить с цитированием
  #9 (permalink)  
Старый 25.06.2019, 10:14
Аватар для ksa
ksa ksa вне форума
CacheVar
Отправить личное сообщение для ksa Посмотреть профиль Найти все сообщения от ksa
 
Регистрация: 19.08.2010
Сообщений: 12,431

Сообщение от alex-romanov
Я делал циклы по числу пар, но ничего не получается.
Я же тебе написал - сколько скобок, столько и циклов. А не пар...
Ответить с цитированием
  #10 (permalink)  
Старый 26.06.2019, 09:29
Аспирант
Отправить личное сообщение для alex-romanov Посмотреть профиль Найти все сообщения от alex-romanov
 
Регистрация: 02.02.2019
Сообщений: 67

вот такой вариант имеет максимальное возможное

вот от такого варианта
"{}}{}}"

, должно быть

{}{}
{{ }}

Нельзя убирать парные скобки.

Скобка { , это некий `открывающий` метод)
Скобка }, это некий `закрывающий ` метод)

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

Скобки приняты для удобства, чтобы заменить названия открывающего и закрывающего методов.

Да и кстати, я то же не понял что от меня хотели, когда давали эту задачу, вот поэтому и пытаюсь понять.

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

В общем спасибо, что пытаетесь помочь
Ответить с цитированием
Ответ



Опции темы Искать в теме
Искать в теме:

Расширенный поиск