Question 354747 in Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – Trouble with parsing a string into a tree in JS

This code converts string into an array tree, but does so with a bug –

// I have this input
const input = "(1 (2 (4 5 6 (7) 108 (9)) 3))";

// and this function


class TreeNode {
  constructor(value) {
    this.value = value;
    this.children = [];
  }
}


function parseInput(input) {
  let root = null;
  let current = null;
  const stack = [];

  for (let i = 0; i < input.length; i++) {
    const char = input[i];

    if (char === '(') {
      if (current !== null) {
        const newNode = new TreeNode(current);
        if (stack.length > 0) {
          stack[stack.length - 1].children.push(newNode);
        } else {
          root = newNode;
        }
        stack.push(newNode);
        current = null;
      }
    } else if (char === ')') {
      stack.pop();
    } else if (char !== ' ' && char !== 'n') {
      let numStr = char;
      while (i + 1 < input.length && /d/.test(input[i + 1])) {
        numStr += input[++i];
      }
      const newNode = new TreeNode(parseInt(numStr));
      if (stack.length > 0) {
        stack[stack.length - 1].children.push(newNode);
      } else {
        root = newNode;
      }
      current = newNode.value;
    }
  }

  return root;
}


// And this function to print the parsed tree 


function printTree(node, depth = 0) {
  const indent = '  '.repeat(depth);
  console.log(`${indent}value: ${node.value}`);
  if (node.children.length > 0) {
    console.log(`${indent}children: [`);
    node.children.forEach((child) => printTree(child, depth + 1));
    console.log(`${indent}]`);
  }
}

const parsed = parseInput(input);
console.log(printTree(parsed));
value: 1
children: [
  value: 2
  value: 2
  children: [
    value: 4
    value: 5
    value: 6
    value: 6
    children: [
      value: 7
    ]
    value: 108
    value: 108
    children: [
      value: 9
    ]
  ]
  value: 3
]

Nodes, that have children, get double printed. I.E the output should be like this –

value: 1
children: [
  value: 2
  children: [
    value: 4
    value: 5
    value: 6
    children: [
      value: 7
    ]
    value: 108
    children: [
      value: 9
    ]
  ]
  value: 3
]

PLS, give me at least a hint at what wrong with my code, I have a bit more then an hour to send it!!!

Tinkering the code, commenting out the code, asking AI, searching web

Tags:

2

Answers


  1. 0

    The cause of the duplication is essentially in this line of code:

    const newNode = new TreeNode(current);

    The value of current has come from current = newNode.value;, and so it is derived from a node that was already created, hence the duplication.

    To solve this, the first if should only deal with putting that last-created node on the stack. I would then store in current the actual node, not its value, and then do stack.push(current) in the first if block.

    Unrelated, but to avoid the check whether the stack is empty or not, start with a dummy node (sentinel), which will be like the virtual parent of the root.

    Here is a correction of your code:

    class TreeNode {
  constructor(value) {
    this.value = value;
    this.children = [];
  }
}

function parseInput(input) {
  const stack = [];
  // Start with a dummy -- to make code easier
  const sentinel = new TreeNode();
  let current = sentinel;
  
  for (let i = 0; i < input.length; i++) {
    const char = input[i];
    if (char === '(') {
      // Don't create a node here: we already have it
      stack.push(current);
    } else if (char === ')') {
      stack.pop();
    } else if (char !== ' ' && char !== 'n') {
      let numStr = char;
      while (i + 1 < input.length && /d/.test(input[i + 1])) {
        numStr += input[++i];
      }
      current = new TreeNode(parseInt(numStr));
      stack.at(-1).children.push(current);
    }
  }
  return sentinel.children[0]; // Assume there is exactly one root
}

function printTree(node, depth = 0) {
  const indent = '  '.repeat(depth);
  console.log(`${indent}value: ${node.value}`);
  if (node.children.length > 0) {
    console.log(`${indent}children: [`);
    node.children.forEach((child) => printTree(child, depth + 1));
    console.log(`${indent}]`);
  }
}

const input = "(1 (2 (4 5 6 (7) 108 (9)) 3))";
const parsed = parseInput(input);
console.log(printTree(parsed));
    Login or Signup to reply.
  2. 0

    You could simply make a JSON with an array data structure by replacing round brackets with square bracktes and spaces with comma. Then build a new data structure.

    class Node {
    constructor(value) {
        this.value = value;
        this.children = [];
    }
}

const
    fn = array => {
        const result = [];
        let node;
        for (const value of array) {
            if (Array.isArray(value)) node.children.push(...fn(value));
            else result.push(node = new Node(value));
        }
        return result;
    },
    input = "(1 (2 (4 5 6 (7) 108 (9)) 3))",
    data = JSON.parse(input.replace(/(/g, '[').replace(/)/g, ']').replace(/ /g, ',')),
    result = fn(data);
    
console.log(result);
    .as-console-wrapper { max-height: 100% !important; top: 0; }
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search