5

Как должен выглядеть алгоритм для раскрытия сокращений строки с фигурными скобками?

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

Например, строка

ab{cde{fg,h}xy,st{uv,zx}d}wer 

разворачивается в

abcdefgxywer,abcdehxywer,abstuvdwer,abstzxdwer

Пытаюсь придумать алгоритм для развертывания с 2+ глубиной. Но пока реализовал только для строки с 0 глубиной.

def raz(myStr):
    r = myStr.split("{")
    r1 = r[1].split("}")
    r2 = r1[0].split(",")
    cOf = 0
    str = ""
    for y in myStr:
        if y == ",":
            cOf += 1
    for i in range(cOf + 1):
        str += r[0]
        str += r2[i]
        str += r1[1]
        str += " "
    res = str.split(" ")
    for j in range(cOf + 1):
        print(res[j])

inStr = "cde{fg,h}xy"
raz(inStr)
0

4 ответа 4

3

Можно рассмотреть строку

ab{cde{fg,h}xy,st{uv,zx}d}wer

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

введите сюда описание изображения

Отсюда видно, что построение всех вариантов — это просто обход в глубину и складывание значения узлов.


Пример простой реализации построения дерева можно увидеть ниже.

В примере используются две функции:

  1. parse - которая возвращает узел со значением и ссылкой на дочерний узел
  2. parseGroup - которая возвращает список узлов имеющих один родительский узел

Для вывода самих строк используется функция dfs обходящая дерево в глубину попутно накапливая строки.

var str = 'ab{cde{fg,h}xy,st{uv,zx}d}wer';
var str2 = 'cde{fg,h}xy';

function parse(arr, node = {
  val: ''
}) {
  var curNode = node;
  while (arr.length) {
    var cur = arr.shift();
    switch (cur) {
      case '{':
        curNode.child = parseGroup(arr);
        break;
      case '}':
        arr.unshift(cur);
      case ',':
        return node;
        break;
      default:
        curNode.child = {
          val: cur
        };
        break;
    }
    curNode = curNode.child;
  }
  return node;
}

function parseGroup(arr) {
  var node = {
    nodes: []
  };
  while (arr.length) {
    var cur = arr.shift();
    switch (cur) {
      case '{':
        node.nodes.push(parseGroup(arr));
        break;
      case '}':
        return node;
      case ',':
        break;
      default:
        node.nodes.push(parse(arr, {
          val: cur
        }));
        break;
    }
  }
  return node;
}

function dfs(node) {
  if (node.nodes) {
    var c = dfs(node.child);
    return node.nodes.map(dfs).flatMap(s => s).map(s => c.map(ss => s + ss)).flatMap(s => s);
  }
  if (node.child)
    return dfs(node.child).map(s => node.val + s);

  return [node.val];
}

var tree = parse(str.split(/([{},])/));
console.log(tree);
console.log(dfs(tree));
console.log(dfs(parse(str2.split(/([{},])/))));
.as-console-wrapper {
  max-height: 100% !important;
}

7
  • Ок, как это сделать? (Построить дерево из строки) 18 мар 2019 в 13:04
  • @АндрейNOP, Это уже другой вопрос :-)
    – Grundy
    18 мар 2019 в 13:34
  • Так в этом и суть, что построить дерево из строки или обойтись без дерева равносильные задачи. Ваш ответ по сути ничего нового не привносит, никак не упрощает задачу и не намекает на решение. 18 мар 2019 в 14:50
  • @АндрейNOP, не совсем :-) вопрос был в подходе, на него дан ответ. Как реализовать немного другой вопрос :)
    – Grundy
    18 мар 2019 в 15:15
  • 1
    @АндрейNOP, мне с деревом кажется понятнее :-) возможно из-за того, что я его писал :)
    – Grundy
    20 мар 2019 в 10:53
1

Я написал 2 функции, которые вызывают друг друга рекурсивно:

// функция разбивает строку по { и } на нулевом уровне
// блок вне скобок просто дописывается к результату
// блок внутри скобок передается в split
function unpack(s) {
  // изначально начинаем с одной строки
  let list = [ "" ];
  // счетчик уровней вложенности
  let level = 0;
  // текущий блок
  let block = "";
  for (let i = 0; i < s.length; ++i) {
    // погружаемся на уровень выше
    if (s[i] == '{' && level++ == 0) {
      // сюда попадем если были на нулевом уровне
      // дописываем к каждой строке накопленный блок
      // если было list=[a, b] и block=c
      // то станет list=[ac, bc]
      list = list.map(w => w + block);
      // начинаем собирать следующий блок
      block = "";
    }
    // всплываем на уровень вверх
    else if (s[i] == '}' && --level == 0) {
      // сюда попадем если всплыли на нулевой уровень
      // разбиваем строку
      let parts = split(block);
      // вот здесь количество результатов увеличится
      // если было list=[a, b] и parts=[c, d]
      // то станет list=[ac, ad, bc, bd]
      list = list.flatMap(w => parts.map(p => w + p));
      // начинаем собирать следующий блок
      block = "";
    }
    // иначе просто добавляем текущий символ к текущему блоку
    // все { } на ненулевом уровне будут здесь же
    else block += s[i];
  }
  // дописываем к каждой строке самый последний блок
  list = list.map(w => w + block);
  return list;
}

// функция разбивает строку по запятой на нулевом уровне
// и для каждой части вызывает unpack
// все части собираются в один список
function split(s) {
  // изначально начинаем с пустого списка
  let list = [];
  // счетчик уровней вложенности
  let level = 0;
  // текущий блок
  let block = "";
  for (let i = 0; i < s.length; ++i) {
    // погружаемся на уровень глубже
    if (s[i] == '{') ++level;
    // всплываем на уровень вверх
    else if (s[i] == '}') --level;

    // нас интересуют только запятые на нулевом уровне
    if (s[i] == ',' && level == 0) {
        // распаковываем накопленный блок
        // т.е. все что вернет unpack будет добавлено в список
        list.push(...unpack(block));
        // начинаем собирать следующий блок
        block = "";
    }
    // иначе просто добавляем текущий символ к текущему блоку
    // все { } и запятые на ненулевом уровне будут здесь же
    else block += s[i];
  }
  // распаковываем самый последний блок
  list.push(...unpack(block));
  return list;
}

let s = "ab{cde{fg,h}xy,st{uv,zx}d}wer";
console.log(unpack(s).join(" "));

console.log(unpack("{1,2,3}").join(" "));
console.log(unpack("12{3,{4,5}6}{7,{8,9}0}").join(" "));
console.log(unpack("1{2,3}4{5,6}7").join(" "));

4
  • можешь чуть больше алгоритм расписать? с первого взгляда выглядит как какая-то магия :)
    – Grundy
    20 мар 2019 в 11:13
  • Кстати, можно вместо unpack вызывать split — результат будет тот же самый, за той разницей, что если у нас есть запятые вне скобок, то split разобьет по ним: 1,2 => [1, 2] (но это, наверное, некорректные входные данные) 20 мар 2019 в 11:56
  • Можно даже немного сократить код (и ускорить(?) за счет меньшего числа конкатенаций), если вместо накопления блока хранить индекс его начала. Тогда начальное значение будет b=0, вместо block можно будет брать s.substring(b, i) или s.substring(b) для последнего блока, начало нового блока b = i + 1, а ветку block += s[i] вообще можно выбросить. 20 мар 2019 в 12:12
  • Тут без замеров не обойтись :-) Мне кажется конкатенация тут не самое страшное:):):)
    – Grundy
    20 мар 2019 в 12:16
0

Не судите строго мою попытку написания алгоритма.
Минус - решает только правильные входные данные (думаю как исправить).
Ещё пытаюсь переписать без рекурсии.
Буду рад объективным советам и замечаниям.

class Graph():
    def __init__(self):
        self.graph = {};
        self.all_path_list = [];

    def add_node(self, node, child):
        if ( node not in self.graph ):
            self.graph[node] = [];
        if ( child not in self.graph ):
            self.graph[child] = [];

        self.graph[node].append(child);

    def echo(self, init_node, end_node):
        self.find_all_path(init_node, end_node, '');

        return ','.join(self.all_path_list);

    def find_all_path(self, cur_node, end_node, path):
        path += cur_node;

        if ( cur_node == end_node ):
            self.all_path_list.append(path);
            return;

        if ( not self.graph[cur_node] ):
            return;

        for node in self.graph[cur_node]:
            self.find_all_path(node, end_node, path);



graph = Graph();

#        00000000001111111111222222222
#        01234567890123456789012345678
stash = 'ab{cde{fg,h}xy,st{uv,zx}d}wer';


sep = ['{', ',', '}'];
init_node = end_node = None;
parents = {};

def deploy(i = 0, node = None, deep = 0):
    global stash, sep, init_node, end_node, parents;

    parent, node = node, '';
    back = False;

    while ( i < len(stash) ):
        ch = stash[i];

        if ( ch not in sep ):
            node += ch;
            i += 1;
            continue;

        elif ( ch == sep[0] ):
            if ( init_node is None ):
                init_node = node;

            if back:
                for item in parents[deep + 1]:
                    graph.add_node(item, node);
                del parents[deep + 1];
            elif ( parent is not None ):
                graph.add_node(parent, node);

            i, parents[deep + 1] = deploy(i + 1, node, deep + 1);

            back = True;
            node = '';

        elif ( ch == sep[1] ):
            if ( init_node is None ):
                init_node = node;

            if back:
                for item in parents[deep + 1]:
                    graph.add_node(item, node);
                del parents[deep + 1];
            else:
                graph.add_node(parent, node);

            parents[deep] = [];
            parents[deep].append(node);

            node = '';
            i += 1;
            continue;

        elif ( ch == sep[2] ):
            if back:
                for item in parents[deep + 1]:
                    graph.add_node(item, node);
            else:
                graph.add_node(parent, node);

            parents[deep].append(node);

            return i + 1, parents[deep];


    end_node = node;
    for item in parents[deep + 1]:
        graph.add_node(item, node);



deploy();

out_str = graph.echo(init_node, end_node);
print(out_str);  #  abcdefgxywer,abcdehxywer,abstuvdwer,abstzxdwer
5
  • Ничего не выводит на входной строке 1{2,3}4{5,6}7: ideone.com/AGJJ6z 20 мар 2019 в 4:49
  • @АндрейNOP Я написал о том, что работает только с "правильными" входными данными, т.е. такими, которые можно представить в виде графа как в ответе у Grundy, я пытаюсь исправить проблему (есть идеи, но надо отполировать их), извините, не такой умный, увы.
    – froxxendsg
    20 мар 2019 в 5:29
  • 1
    А что неправильного в 1{2,3}4{5,6}7? парность скобок в порядке 20 мар 2019 в 5:35
  • @АндрейNOP По быстрому исправил код, теперь такую строку обрабатывает. Не предусмотрел такой вариант. Но всё равно код дорабатывать буду, мне самому интересна задача.
    – froxxendsg
    20 мар 2019 в 5:49
  • добавь описание что именно в коде происходит
    – Grundy
    20 мар 2019 в 12:06
0

Альтернативным вариантом решения может стать простой replace, который будет брать внутренние скобки со словами по краям, например cde{fg,h}xy и раскрывать их "cdefgxy,cdehxy"

Далее повторять этот процесс в цикле, пока в строке не уберутся все фигурные скобки.

Для поиска нужного шаблона можно воспользоваться следующим регулярным выражением:

/(\w+)?{([^{}]+)}(\w+)?/g

При совпадении в первую группу попадет текст слева от скобки, в третью - справа, а во вторую группу попадет перечисление вариантов.

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

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

Пример:

var str = 'ab{cde{fg,h}xy,st{uv,zx}d}wer';
var str2 = 'cde{fg,h}xy';

function unpack(str){
  while(/(\w+)?{([^{}]+)}(\w+)?/.test(str)){
    str = str.replace(/(\w+)?{([^{}]+)}(\w+)?/g, ($0,$1,$2,$3)=>$2.split(',').map(s=>($1||'')+s+($3||'')));
  }
  return str;
}

console.log(unpack(str));
console.log(unpack(str2));
console.log(unpack('{1,2}{3,4}'));


Как заметили в комментариях данное решение не подходит для некоторых специальных случаев, в частности присутствия нескольких вариантов последовательно, например, для строки '{1,2}{3,4}' вернется '1,23,4' . Однако его можно расширить добавив возможность отслеживать такие ситуации и применять к ним специальную замену, например:

var str = 'ab{cde{fg,h}xy,st{uv,zx}d}wer';
var str2 = 'cde{fg,h}xy';
var str3 = '1{2,3}4{5,6}7';
var str4 = '{1,2}{3,4}{5,6}';
var str5 = 'cd e{fg,h}xy';
var str6 = '{1,2}';

function unpack(str) {
  while (str.includes('{')) {
    var flag = false;
    str = str.replace(/([^,{}]+)?{([^{}]+)}([^,{}]+)?/g, function($0, $1, $2, $3, startIndex, fullStr) {
      var replacement = $2.split(',').map(s => ($1 || '') + s + ($3 || ''));
      flag = flag || fullStr[startIndex + $0.length] == '{';
      return flag ? '{' + replacement + '}' : replacement;
    }).replace(/{([^{}]+)}{([^{}]+)}/, ($0, $1, $2, startIndex, fullStr) => {
      var a = $1.split(',');
      var b = $2.split(',');
      if (fullStr[startIndex + $0.length] == '{')
        return '{' + a.map(s => b.map(ss => s + ss)).flatMap(s => s) + '}';
      else
        return a.map(s => b.map(ss => s + ss)).flatMap(s => s);
    });
  }
  return str;
}

console.log(unpack(str));
console.log(unpack(str2));
console.log(unpack(str3));
console.log(unpack(str4));
console.log(unpack(str5));
console.log(unpack(str6));

5
  • Тоже сначала была идея раскрывать начиная с самых глубоких скобок, но я раскрывал по одному блоку за раз и на выходе получилось 8 результатов вместо 4х. В вашем варианте получилось 4 как надо, но все равно меня смущает такое решение, наверняка можно и к нему подобрать контрпример :) 20 мар 2019 в 2:31
  • Контрпримеры: cd e{fg,h}xy (с пробелом), {1,2} 20 мар 2019 в 2:45
  • Если то что выше решается заменой \w на что-то более подходящее, то вот вам еще контрпример: 1{2,3}4{5,6}7 — несколько выборных шаблонов внутри одной ветки (не разделены запятыми) 20 мар 2019 в 4:37
  • @АндрейNOP, добавил еще вариант :-) этот должен проходить большинство случаев :)
    – Grundy
    20 мар 2019 в 10:52
  • Ок, этого достаточно. :D Больше контрпример искать не буду :) 20 мар 2019 в 11:06

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.