Generates a logical expression from a plain structure, generating an intermediate AST binary tree

process_coded_binary_tree.groovy

class BinaryTree {

   def tmp // temporal expression
   def value
   def left
   def right
   def parent // null for root

   String toString()
   {
      toStringIndent()
   }
   
   String toStringIndent(idnt = 0)
   {
      if (left)
         value +"\n"+ " ".multiply(idnt) +" |_ "+ left.toStringIndent(idnt+1) +"\n"+ " ".multiply(idnt) +" |_ "+ right.toStringIndent(idnt+1)
      else value
   }
   
   // Know if tree is left or right child under it's parent
   boolean isLeft()
   {
      return this == this.parent.left
   }
   boolean isRight()
   {
      return this == this.parent.right
   }
   BinaryTree sibling()
   {
      if (this.isLeft()) return this.parent.right
      return this.parent.left
   }
   boolean isComplex()
   {
      return this.value == 'AND' || this.value == 'OR'
   }
}

def process_tree(btree)
{
   try_divide(btree)
   if (btree.left) process_tree(btree.left)
   if (btree.right) process_tree(btree.right)
}

def try_divide(btree)
{
   def i, left_expr = [], right_expr = []
   i = btree.tmp.findIndexOf { it[2] } // first with post_group_op
   
   if (i >= 0) // continue dividing tree, right grouping
   {
       // the current root value should be the current post_group_op
       // and the current post_group_op should be deleted to avoid reprocessing
       btree.value = btree.tmp[i][2]
       btree.tmp[i][2] = ''
    
       btree.tmp.eachWithIndex { item, idx ->
          if (idx <= i) left_expr << item
          else right_expr << item
       }
       
       //println 'post left_expr '+ left_expr
       //println 'post right_expr '+ right_expr
    
       btree.left = new BinaryTree(tmp: left_expr, parent: btree)
       btree.right = new BinaryTree(tmp: right_expr, parent: btree)
   }
   else // continue dividing tree, left grouping
   {
       // last with prev_group_op (is last to group to the left, so a AND b AND c will be (a AND b) AND c)
       // if findIndexOf is used, a AND b AND c will be a AND (b AND c), that is not the desired grouping
       i = btree.tmp.findLastIndexOf { it[0] }
        
       if (i < 0) // ends recursion, leaf node
       {
          assert btree.tmp.size() == 1
          btree.value = btree.tmp[0][1]
          return // no prev group_op found
       }
       
       // the current root value should be the current post_group_op
       // and the current post_group_op should be deleted to avoid reprocessing
       btree.value = btree.tmp[i][0]
       btree.tmp[i][0] = ''
    
       btree.tmp.eachWithIndex { item, idx ->
          if (idx < i) left_expr << item
          else right_expr << item
       }
       
       //println 'prev left_expr '+ left_expr
       //println 'prev right_expr '+ right_expr
    
       btree.left = new BinaryTree(tmp: left_expr, parent: btree)
       btree.right = new BinaryTree(tmp: right_expr, parent: btree)
   }
}

String toExpressionString(btree)
{
   def expr = ''
   
   if (btree.left)
   {
      def lexpr = toExpressionString(btree.left)
      def rexpr = toExpressionString(btree.right)
      
      expr = '('+ lexpr +' '+ btree.value +' '+ rexpr +')'
   }
   else
   {
      expr = btree.value
   }
   
   return expr
}

// returns the leaves in the same order as they appear in the plain expression (left to right)
List getLeaves(btree, returnNode = false)
{
   List leaves = []
   if (btree.isComplex())
   {
      leaves += getLeaves(btree.left, returnNode)
      leaves += getLeaves(btree.right, returnNode)
   }
   else
   {
      if (returnNode)
         leaves << btree
      else
         leaves << btree.value
   }
   return leaves
}

// same as getLeaves but returns the BinaryTree nodes, not their value.
List getLeavesBTree(btree)
{
   return getLeaves(btree, true)
}


// from a processed tree, get the expression back
def getExpression(btree)
{
   // creates empty expression structure with leaves on their rows, in row[1]
   def leaves = getLeavesBTree(btree)
   def expression = []
   leaves.each { leave ->
      expression << ['', leave, ''] // leave is a BinaryTree node, not it's value, we need to put the value after finishing the process
   }
   def queue = [] as Queue // .offer() adds, .poll() removes
   
   //getExpressionRecursive(btree, expression, queue, 0)
   getExpressionIterative(expression, queue)
   
   // transform the BinaryTrees in the current expression, back to their values
   def simpleExpression = []
   expression.each { row ->
      simpleExpression << [ (row[0]?row[0].value:''), (row[1]?row[1].value:''), (row[2]?row[2].value:'')]
   }
   
   return simpleExpression
}

def getExpressionIterative(expression, queue)
{
   def row, current = 0
 
   while (current < expression.size()-1)
   {
      btree = expression[current][1]
      
      if (btree.isLeft())
      {
         if (!btree.sibling().isComplex()) // sibling is simple
         {
            // row of the sibling of the current node
            row = expression.find { it[1] == btree.sibling() }
                 
            // left assoc = parent (this is BinaryTree needs to be transformed to it's value when finished)
            row[0] = btree.parent
         }
         else
         {
            // row of the current node
            row = expression[current]
               
            // right assoc = parent
            row[2] = btree.parent
         }
            
         // add parent to queue
         queue.offer(btree.parent)
      }
          
      // current = next
      current ++
   }
   
   while (!queue.isEmpty())
   {
      btree = queue.poll()
      
      // avoid procesing root or right siblings
      if (!btree.parent || btree.isRight()) continue
      
      if (btree.sibling().isComplex())
      {
         // if sibling is complex, the current node should be on left assoc of some row
         row = expression.find { it[0] == btree } // left assoc
         
         // right assoc = parent
         row[2] = btree.parent
      }
      else
      {
         // if sibling is simple, it should be on the value space in the row, row[1]
         row = expression.find { it[1] == btree.sibling() }
         
         // left asoc = parent
         row[0] = btree.parent
      }
      
      // add parent to queue
      queue.offer(btree.parent)
   }
}

def printBTreeExpression(e)
{
   e.each { row ->

      println ((row[0] ? row[0].value : '') +', '+ (row[1] ? row[1].value : '') +', '+ (row[2] ? row[2].value : ''))     
      //println "row "+ row[0] //row[0].value. +", "+ row[1].value +", "+ row[2].value
   }
}


/*
def expr = [
   ['', 'C1', ''],
   ['AND', 'C2', 'OR'],
   ['', 'C3', ''],
   ['AND', 'C4', ''],
   ['AND', 'C5', 'OR'],
   ['', 'C6', '']
]
*/
/*
def expr = [
   ['', 'C1', ''],
   ['AND', 'C2', 'OR'],
   ['', 'C3', ''],
   ['AND', 'C4', ''],
   ['AND', 'C5', ''],
   ['OR', 'C6', ''] // using the OR in the left association of the last node produces the same expression, because above says "C6 is at the rith of the rest" and this says "the rest is at the left of C6"
]
*/
/*
def expr = [
   ['', 'C1', ''],
   ['OR', 'C2', 'AND'],
   ['', 'C3', '']
]
*/
/*
def expr = [
   ['', 'C1', ''],
   ['AND', 'C2', '']
]
*/
/*
def expr = [
   ['', 'C1', '']
]
*/

def expr = [
   ['', 'C3', 'AND'],
   ['', 'C4', ''],
   ['AND', 'C5', 'OR'],
   ['', 'C6', 'AND'],
   ['', 'C7', ''],
   ['OR', 'C8', '']
]

def tree = new BinaryTree(tmp: expr)
process_tree(tree)
println tree
/*
OR
 |_ AND
  |_ C1
  |_ C2
 |_ OR
  |_ AND
   |_ AND
    |_ C3
    |_ C4
   |_ C5
  |_ C6
*/

println toExpressionString(tree)
// ((C1 AND C2) OR (((C3 AND C4) AND C5) OR C6))

// println tree.tmp // only the leaves left after the processing
// println getLeaves(tree)

// Get expression back from the tree structure, might not be 100% equal because there
// is an equivalent with the last complex node being and the right assoc of the n-1
// row or at the left assoc of the n row.
def e = getExpression(tree)
//println e

def tree2 = new BinaryTree(tmp: e)
process_tree(tree2)
println tree2

return