Transform string to object in Javascript

Question

I am having trouble transform a string using a certain mapping. The string I want to transform is the following:

Input

$B$O$TT$O$$KK$$Z$HH$$U$PP$$QQ$U$Z$B$

Which can be better seen as the following (very close to HTML):

$B
  $O
    $TT$
  O$
  $K
  K$
  $Z
    $HH$
    $U
      $PP$
      $QQ$
    U$
  Z$
B$

I am aiming to transform this into the following:

Expected Result

{
  "v": "B",
  "chld": [
    {
      "v": "O",
      "chld": [
        {
          "v": "T"
        }
      ]
    },
    {
      "v": "K"
    },
    {
      "v": "Z",
      "chld": [
        {
          "v": "H"
        },
        {
          "v": "U",
          "chld": [
            {
              "v": "P"
            },
            {
              "v": "Q"
            }
          ]
        }
      ]
    }
  ]
}

Heres where I have gotten:

function transform(contentString, currentObj, currentChld) {
  let closeOpen = {
    open: /\$[A-Z]/i,
    closed: /[A-Z]\$/i 
  }

  if (!contentString.length) {
    return currentObj
  }

  let currentSlice = contentString.slice(0, 2)
  let newString = contentString.substring(2)
  //See if tag is open, for example $A is open, A$ is closed
  if (currentSlice.match(closeOpen['open'])){
    currentObj = {v: currentSlice[1]}
    currentObj.chld = []
    return transform(newString,  currentObj , currentChld)

  }

}

It seems the recursion is not quite kicking in. Solution doesnt have to be recursive. If theres something that simpler thats okay too! My hope is to get the expected result above. Can anyone help? Simplest solution would be best!

EDIT: yes tags will only have one letter, restricted to thos in [A-Z]

Answer 1

I'm late to the party, but a simple stack based appraoch works fine.

var str = "$B$O$TT$O$$KK$$Z$HH$$U$PP$$QQ$U$Z$B$"

function convert(str) {
  var nodes = str.match(/../g)

  var node, parent, stack = [{
    chld: []
  }];

  for (key of nodes) {
    parent = stack.slice(-1)[0]
    if (key[0] == "$") {
      node = {
        v: key[1],
        chld: []
      }
      parent.chld.push(node);
      stack.push(node)
    } else if (key[1] == "$") {
      node = stack.pop()
      if (!node.chld.length) delete node.chld
    }

  }
  return stack.pop().chld[0]
}
console.log(convert(str));

Answer 2

You can write a PEG.js parser to create the tree for you like this:

class Node {
  constructor (tag, children = []) {
    this.v = tag;
    if (children.length > 0) {
      this.chld = children;
    }
  }
  toString () {
    return '$' + this.v + (this.chld || []).join('') + this.v + '$'
  }
}

let parser = PEG.buildParser(`
Expression = open:Open children:Expression * close:Close {
  var object = new Node(open, children);

  if (open !== close) {
    return expected('"' + object + '"');
  }

  return object
}

Open = "$" tag:Tag { return tag } 
Close = close:Tag "$" { return close }
Tag = [A-Za-z]
`, { cache: true });

let tree = parser.parse('$B$O$TT$O$$KK$$Z$HH$$U$PP$$QQ$U$Z$B$');

console.log(tree);

try {
  parser.parse('$B$O$TT$$U$PP$V$O$B$');
} catch (error) {
  console.log(error.message);
}

.as-console-wrapper{max-height:100%!important}

<script src="https://cdnjs.cloudflare.com/ajax/libs/pegjs/0.9.0/peg.min.js"></script>

Note that in version 0.10, the method has been changed from peg.buildParser() to peg.generate() according to the documentation.