Функция, принимающая строку и разворачивающая сокращения с использованием {}

#алгоритм #любой_язык

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

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

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

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)

    

Ответы

Ответ 1

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

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


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



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



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

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


parse - которая возвращает узел со значением и ссылкой на дочерний узел
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;
}


Ответ 2

Я написал 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(" "));


Ответ 3

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

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


Ответ 4

Альтернативным вариантом решения может стать простой 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));