Алгоритм - нумерация для оглавления (оглавление) - PullRequest
Новая
       11

Алгоритм - нумерация для оглавления (оглавление)

3 голосов
/ 01 июня 2010

Я хочу реализовать функцию VBA для нумерации строк Excel на основе глубины группировки строк.

Но я думаю, что общий алгоритм генерации оглавления более интересен.

Проблема:

Дан список "отступов" строк, таких как 

One
 Two
  Three
   Four
 Five
Six

(«уровень отступа» может считаться известным и частью входных данных)

Чтобы сгенерировать следующий вывод: 

1.    One
1.1    Two
1.1.1   Three
1.1.1.1  Four
1.2    Five
2.    Six

Конечно, мой код запущен и работает ... и также скрыт под THWoS (Тяжелый вес стыда)

Ответы [ 2 ]

8 голосов
/ 01 июня 2010

Используйте стек для чисел. Проходите по каждой строке и проверяйте уровень отступа каждой строки, чтобы отступ не был уровнем 1.

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

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

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

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

const toc = `
One
 Two
  Three
   Four
 Five
  Six
  Seven
 Eight
Nine
Ten
`;

let stack = [];

toc.trim().split(/\n/g).forEach(line => {
  // Gets the identitation level with 1 being no indentation and so forth
  let level = line.match(/^\s*/)[0].length + 1;

  if (level > stack.length) {
    while (level > stack.length)
      stack.push(1);
  } else {
    while (level < stack.length)
      stack.pop();

    stack[stack.length - 1]++;
  }
  
  let title = stack.join(".") + ". " + line.trim();

  document.body.appendChild(document.createElement("div")).innerText = title;
});
2 голосов
/ 01 июня 2010

Этот алгоритм предполагает, что уровень отступа никогда не увеличивается более чем на 1 единицу. Если это так, то вы должны установить все «пропущенные» уровни на 1. 

#use a vector instead, if your language supports it
numbering = {0, 0, 0, 0, 0, 0, 0}

for line in lines:
    level = indentLevel(line) #starting from 0

    numbering[level] = numbering[level] + 1
    numbering[level + 1] = 0 #create it if it doesn't exist
    for n = 0 to level - 1
        print numbering[n], ".",
    print numbering[level], " ", line
...