Scala: как разобрать строку и сгенерировать вектор вложенных векторов

Question

Цель:

Дана строка вида val strang = "ab (cde (fgh) ijk) lmn) opq) rs"

Сначала я хочу построить вектор строки, разделенной символами "(" и ")". Это достигается с помощью

val regexPattern = "((?<=\\()|(?=\\())|((?<=\\))|(?=\\)))"
val data: Vector[String] = strang .split(regexPattern ).map(_.toString).toVector

Обратите внимание, что фактическая строка будет гораздо более разнообразной, но то, как она разделена, стоит.

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

val newVector =
for(row <- data) {
    if(row == "(") // opening angle bracket
        start constructing a nested vector inside of newVector
        keep appending to the nested vector until we encounter a ")"
        character (closing parenthesis).
        IF before encountering a ")" we encounter another "(" then
        create another nestedVector inside the previous nested vector
        and keep appending to it until a closing parenthesis ")" is
        encountered

    else if(row == ")")
        if we encounter a closing parenthesis, go up one level of the nested 
        vectors
    else
        simply append this row to the new vector
        newVector :+ row
}

Я предпринял довольно много попыток сделать это с ограниченным успехом. Используя рекурсивную функцию, я управляю только одним уровнем вложенности, но, чтобы выйти за его пределы, я использую циклы while, которые кажутся излишними. Вложенные векторы могут быть особого типа. Я пробовал например case class Rowy (строка: строка, строки: вектор [вектор [строка]]) или же case class Rowy (строка: строка, строки: вектор (Rowy))

Я относительно новичок в scala и мне интересно, есть ли элегантный способ подойти к этому с помощью методов scanLeft или foldLeft. Любая помощь будет оценена.

PS: я использую не фактический цикл for для итерации по вектору «данных», а рекурсивную функцию. Цикл for просто сообщает, что происходит итерация. Любая помощь будет оценена.

Answer 1

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

// Tree structure definition
sealed trait Data
object Data {
  case class Leaf(data: String) extends Data
  case class Branch(parts: Vector[Data]) extends Data {
    // a convenience method to append data to a branch more easily
    def :+(data: Data): Branch = copy(parts = parts :+ data)
  }
}

object Main extends App {
  val regexPattern = "((?<=\\()|(?=\\())|((?<=\\))|(?=\\)))"
  val string = "ab(cde(fgh)ijk)lmn"  // now the input is balanced
  val data: Vector[String] = string.split(regexPattern).toVector

  println(data)

  var stack: List[Data.Branch] = Data.Branch(Vector.empty) :: Nil
  for (part <- data) {
    part match {
      case "(" =>
        stack = Data.Branch(Vector.empty) :: stack
      case ")" =>
        val top :: parent :: rest = stack
        stack = (parent :+ top) :: rest
      case _ =>
        stack = (stack.head :+ Data.Leaf(part)) :: stack.tail
    }
  }
  val result = stack.head

  println(result)
}

Это выводит это:

Vector(ab, (, cde, (, fgh, ), ijk, ), lmn)
Branch(Vector(Leaf(ab), Branch(Vector(Leaf(cde), Branch(Vector(Leaf(fgh))), Leaf(ijk))), Leaf(lmn)))

Если мы немного переформатируем, мы получим

Branch(Vector(
  Leaf(ab),
  Branch(Vector(
    Leaf(cde),
    Branch(Vector(
      Leaf(fgh)
    )),
    Leaf(ijk)
  )),
  Leaf(lmn)
))

, который, как вы можете видеть, отражает структуру внутри вашей строки.

Если ваш ввод может иметь несбалансированные скобки, то вам может понадобиться добавить дополнительные проверки в цикл в части case ")". Прямо сейчас, если вход не сбалансирован, будет выдан MatchError, потому что переменная stack не будет иметь необходимого количества элементов.