Coverage Report

Coverage Report - org.kuali.student.common.ui.client.widgets.table.ExpressionParser

Classes in this File

Line Coverage

Branch Coverage

Complexity

ExpressionParser

0/294

0/282

6.333

 /**
  * Copyright 2010 The Kuali Foundation Licensed under the
  * Educational Community License, Version 2.0 (the "License"); you may
  * not use this file except in compliance with the License. You may
  * obtain a copy of the License at
  *
  * http://www.osedu.org/licenses/ECL-2.0
  *
  * Unless required by applicable law or agreed to in writing,
  * software distributed under the License is distributed on an "AS IS"
  * BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
  * or implied. See the License for the specific language governing
  * permissions and limitations under the License.
  */
 
 package org.kuali.student.common.ui.client.widgets.table;
 
 import java.util.ArrayList;
 import java.util.List;
 import java.util.Stack;
 
 import org.kuali.student.common.ui.client.widgets.rules.Token;
 
 /**
  * This is the parser for boolean expression.
  * It checks the error, creates the Reverse Polish notation,
  * merge the binary tree, sort the nodes. 
  * 
  * */
 public class ExpressionParser {
     /**
      * Error messages are stored in a list
      * */
     private List<String> errorMessageList = new ArrayList<String>();
     
     public ExpressionParser() {
     }
     /**
      * After parsing, it tells if the expression has error.
      *  
      * @return If the input expression has error
      * */
     public boolean hasError(){
         return errorMessageList.size() > 0;
     }
     /**
      * It returns all error messages
      * 
      * @return List of error messages
      * */
     public List<String> getErrorMessage(){
         return errorMessageList;
     }
     /**
      * Parse the boolean expression
      * 
      * @return the tree of input tokens
      * */
     public Node<Token> parse(String expression) {
         errorMessageList = new ArrayList<String>();
         List<String> tokenValueList = getTokenValue(expression);
         List<Token> tokenList = getTokenList(tokenValueList);
         errorCheck(tokenList);
         if(hasError()){
             return null;
         }
         List<Node<Token>> nodeList = toNodeList(tokenList);
         List<Node<Token>> rpnList = getRPN(nodeList);
 
         Node<Token> root = binaryTreeFromRPN(rpnList);
         
         //Node<Token> ruleRoot = root;
         Node<Token> ruleRoot = mergeBinaryTree(root);
       
         
         //  ruleRoot = reStructure(root);
         ruleRoot = orderLeafChildren(ruleRoot, tokenList );
         ruleRoot = orderNonLeafChildren(ruleRoot, tokenList );
         return ruleRoot;
     }
     /**
      * Create the boolean expression from tree
      * 
      * @return boolean expression
      * */
     public static String getExpressionString(Node root){
         while(root.getChildCount()> 1){
             List<List<Node>> level = root.toLevel();
             for(Node<Token> n: level.get(level.size()-1)){
                 if(n.isLeaf() && n.getParent() != null){
                     Node parent = n.getParent();
                     StringBuilder sb = new StringBuilder();
                     if(parent.getChildAt(0).getUserObject() instanceof ExpressionNode
                             && parent.getChildAt(0).getUserObject() instanceof ExpressionNode
                         && (( ExpressionNode)parent.getChildAt(0).getUserObject()).token.type == Token.Or
                         && (( Token)parent.getUserObject()).type == Token.And){
                         sb.append(" ( "+parent.getChildAt(0).getUserObject().toString()+" ) ");
                     }else{
                         sb.append(" "+parent.getChildAt(0).getUserObject().toString()+" ");    
                     }
                     
                     
                     for(int i=1;i<parent.getChildCount();i++){
                         Node child = parent.getChildAt(i);
 
                         if(parent.getChildAt(i).getUserObject() instanceof ExpressionNode
                                 && parent.getChildAt(i).getUserObject() instanceof ExpressionNode
                             && (( ExpressionNode)parent.getChildAt(i).getUserObject()).token.type == Token.Or
                             && (( Token)parent.getUserObject()).type == Token.And){
                             sb.append(parent.getUserObject().toString()+ " ( "+
                                     child.getUserObject().toString()+" ) ");
 
                         }else{
                             sb.append(" "+parent.getUserObject().toString()+ "  "+
                                     child.getUserObject().toString()+" ");
                         }
                     }
                     ExpressionNode expressionNode = new ExpressionNode();
                     expressionNode.token = (Token)parent.getUserObject();
                     expressionNode.expression = sb.toString();
                     parent.setUserObject(expressionNode);
                     parent.removeAllChildren();
                     break;
                 }
             }
             
         }
         
         
         return root.getUserObject().toString();
     }
     /**
      * Order the nonleaf children
      * */
     private Node<Token> orderNonLeafChildren(Node<Token> binaryTree,List<Token> tokenList ) {
         List<Node> list = binaryTree.getNonLeafChildren();
         if(list.size() > 1){
             sequeceNonLeaves(list, tokenList);
             binaryTree.children().removeAll(list);
             for(Node n: list){
                 binaryTree.addNode(n);
             }
         }
         for(Node n: binaryTree.children()){
             if(n.isLeaf() == false){
                 orderNonLeafChildren(n,tokenList );
             }
         }
         
         List<Node> nonLeafChildList = binaryTree.getNonLeafChildren();
         List<Node> leafChildList = binaryTree.getLeafChildren();
         binaryTree.children().removeAll(nonLeafChildList);
         binaryTree.children().removeAll(leafChildList);
         for(Node n: nonLeafChildList){
             binaryTree.addNode(n);
         }
         
         for(Node n: leafChildList){
             binaryTree.addNode(n);
         }
         return binaryTree;
    }
    /**
     * Order the non leaves
     * */
    private void sequeceNonLeaves(List<Node> nonLeafChildList, List<Token> list){
        if(nonLeafChildList.size() == 2){
            if (indexInInputTokenList((Token)nonLeafChildList.get(0).getFirstLeafDescendant().getUserObject(), list)> 
            indexInInputTokenList((Token)nonLeafChildList.get(1).getFirstLeafDescendant().getUserObject(), list)) {
                Node buffer = nonLeafChildList.get(0);
                nonLeafChildList.remove(0);
                nonLeafChildList.add(buffer);
            }
        }
        for (int out = nonLeafChildList.size() - 1; out > 1; out--){
          for (int in = 0; in < out; in++){
            // inner loop (forward)
            if (indexInInputTokenList((Token)nonLeafChildList.get(in).getFirstLeafDescendant().getUserObject(), list)> 
            indexInInputTokenList((Token)nonLeafChildList.get(in + 1).getFirstLeafDescendant().getUserObject(), list)) {
              // swap them
                Node node = nonLeafChildList.get(in);
                nonLeafChildList.remove(in);
                nonLeafChildList.add(in+1, node);
            }
          }
        }
    }
     /**
      * Order the leaf children
      * */
     private Node<Token> orderLeafChildren(Node<Token> binaryTree,List<Token> tokenList ) {
          List<Node> list = binaryTree.getLeafChildren();
          if(list.size() > 1){
              sequeceLeaves(list, tokenList);
              binaryTree.children().removeAll(list);
              for(Node n: list){
                  binaryTree.addNode(n);
              }
          }
          for(Node n: binaryTree.children()){
              if(n.isLeaf() == false){
                  orderLeafChildren(n,tokenList );
              }
          }
         return binaryTree;
     }
     /**Reorder the children*/
     private void sequeceLeaves(List<Node> leafChildList, List<Token> list){
         if(leafChildList.size() == 2){
             if (indexInInputTokenList((Token)leafChildList.get(0).getUserObject(), list)> 
             indexInInputTokenList((Token)leafChildList.get(1).getUserObject(), list)) {
               // swap them
                 Token buffer = (Token)leafChildList.get(0).getUserObject();
                 leafChildList.get(0).setUserObject(leafChildList.get(1).getUserObject());
                 leafChildList.get(1).setUserObject(buffer);
             }
             
         }
         
         for (int out = leafChildList.size() - 1; out > 1; out--){
           for (int in = 0; in < out; in++){
             // inner loop (forward)
             if (indexInInputTokenList((Token)leafChildList.get(in).getUserObject(), list)> 
             indexInInputTokenList((Token)leafChildList.get(in + 1).getUserObject(), list)) {
               // swap them
                 Token buffer = (Token)leafChildList.get(in).getUserObject();
                 leafChildList.get(in).setUserObject(leafChildList.get(in + 1).getUserObject());
                 leafChildList.get(in + 1).setUserObject(buffer);
             }
           }
         }
     }
     /**Get the index of a token in the token list*/
     private int indexInInputTokenList(Token token, List<Token> list){
         int i = -1;
         for(Token n: list){
             if(n.value != null && token.value != null && n.value.equals(token.value)){
                 return i;
             }
             i++;
         }
         return i;
     }
 
 /*    public static  Node<Token> reStructure(Node<Token> binaryTree) {
         Node root = new Node();
         //Node root = binaryTree;
         root.setUserObject(binaryTree.getUserObject());
         List<Node> childList = binaryTree.children();
 
         ListIterator<Node> itr = childList.listIterator();
         for (; itr.hasNext();) {
             Node node = getDeeperNode(childList);
             if (node.isLeaf()) {
                 root.addNode(node);
             } else {
                 root.addNode(reStructure(node));
             }
             childList.remove(node);
         }
 
         return root.clone();
     }
 */
     private static Node getDeeperNode(List<Node> nodeList) {
         int childCount = 0;
         for (Node node : nodeList) {
             if (childCount < node.getAllChildren().size()) {
                 childCount = node.getAllChildren().size();
             }
         }
         for (Node node : nodeList) {
             if (childCount == node.getAllChildren().size()) {
                 return node;
             }
         }
 
         return null;
     }
     /** Merge the binary tree. */
     public static Node<Token> mergeBinaryTree(Node<Token> binaryTree) {
         while (parentEqualsGrandParent(binaryTree)) {
             List<Node<Token>> list = binaryTree.getAllChildren();
 
             for (Node node : list) {
                 if (node.getParent() != null && node.getParent().getParent() != null) {
                     Node parentNode = node.getParent();
                     Node grandParentNode = node.getParent().getParent();
                     Token parentToken = (Token) parentNode.getUserObject();
                     Token grandParentToken = (Token) grandParentNode.getUserObject();
 
                     if (parentToken.type == grandParentToken.type) {
                         for (int i = 0; i < parentNode.getChildCount(); i++) {
                             Node n = parentNode.getChildAt(i);
                             grandParentNode.addNode(n);
                         }
                         grandParentNode.remove(parentNode);
                     }
                 }
             }
         }
         return binaryTree;
     }
 
     private static boolean parentEqualsGrandParent(Node<Token> binaryTree) {
         List<Node<Token>> list = binaryTree.getAllChildren();
 
         for (Node node : list) {
             if (node.getParent() != null && node.getParent().getParent() != null) {
 
                 Token parentToken = (Token) node.getParent().getUserObject();
                 Token grandParentToken = (Token) node.getParent().getParent().getUserObject();
                 if (parentToken.type == grandParentToken.type) {
                     return true;
                 }
             }
         }
 
         return false;
     }
     /** Build the binary tree from list of tokens*/
     private Node<Token> binaryTreeFromRPN(List<Node<Token>> rpnList) {
         Stack<Node<Token>> conditionStack = new Stack<Node<Token>>();
         for (Node<Token> node : rpnList) {
             if (node.getUserObject().type == Token.Condition) {
                 conditionStack.push(node);
             } else if (node.getUserObject().type == Token.And || node.getUserObject().type == Token.Or) {
                 Node<Token> left = conditionStack.pop();
                 Node<Token> right = conditionStack.pop();
                 node.addNode(left);
                 node.addNode(right);
                 conditionStack.push(node);
             }
         }
 
         return conditionStack.pop();
     }
 
     /**
      * If higher push to stack, else pop till less than or equal, add to list push to stack if ( push to stack if ) pop to
      * list till (.
      * 
      * http://en.wikipedia.org/wiki/Reverse_Polish_notation
      * 
      */
     private List<Node<Token>> getRPN(List<Node<Token>> nodeList) {
         List<Node<Token>> rpnList = new ArrayList<Node<Token>>();
         Stack<Node<Token>> operatorStack = new Stack<Node<Token>>();
 
         for (Node<Token> node : nodeList) {
             if (node.getUserObject().type == Token.Condition) {
                 rpnList.add(node);
 
             } else if (node.getUserObject().type == Token.And) {
                 operatorStack.push(node);
             } else if (node.getUserObject().type == Token.StartParenthesis) {
                 operatorStack.push(node);
             } else if (node.getUserObject().type == Token.Or) {
 
                 if (operatorStack.isEmpty() == false && operatorStack.peek().getUserObject().type == Token.And) {
                     do {
                         rpnList.add(operatorStack.pop());
                     } while (operatorStack.isEmpty() == false && operatorStack.peek().getUserObject().type == Token.And);
                 }
 
                 operatorStack.push(node);
             } else if (node.getUserObject().type == Token.EndParenthesis) {
                 while (operatorStack.peek().getUserObject().type != Token.StartParenthesis) {
                     rpnList.add(operatorStack.pop());
                 }
                 operatorStack.pop();// pop the (
             }
         }
         if (operatorStack.isEmpty() == false) {
             do {
                 rpnList.add(operatorStack.pop());
             } while (operatorStack.isEmpty() == false);
         }
         return rpnList;
     }
 
     private int findNodeIndex(List<Node<Token>> nodeList, int type) {
         int index = -1;
         for (Node<Token> node : nodeList) {
             index++;
             if (node.getUserObject().type == type) {
                 return index;
             }
         }
         return index;
     }
 
     private boolean hasParenthesis(List<Node<Token>> nodeList) {
         boolean has = false;
         for (Node<Token> node : nodeList) {
             if (node.getUserObject().type == Token.StartParenthesis) {
                 return true;
             }
         }
         return has;
     }
 
     private List<Node<Token>> toNodeList(List<Token> tokenList) {
         List<Node<Token>> nodeList = new ArrayList<Node<Token>>();
         for (Token token : tokenList) {
             Node<Token> node = new Node<Token>();
             node.setUserObject(token);
             nodeList.add(node);
         }
         return nodeList;
     }
 
     private void errorCheck(List<Token> tokenList) {
         if (tokenList.size() == 0) {
             errorMessageList.add("empty input");
             return;
         }
         if (tokenList.size() <= 2) {
             errorMessageList.add("input not complete");
             return;
         }
         if ((tokenList.get(0).type == Token.StartParenthesis 
                 || tokenList.get(0).type == Token.Condition) == false) {
             errorMessageList.add("must start with ( or condition");
             return;
         }
         int lastIndex = tokenList.size() - 1;
         if ((tokenList.get(lastIndex).type == Token.EndParenthesis || tokenList.get(lastIndex).type == Token.Condition) == false) {
             errorMessageList.add("must end with ) or condition");
             return;
         }
         if (countToken(tokenList, Token.StartParenthesis) != countToken(tokenList, Token.EndParenthesis)) {
             errorMessageList.add("() not in pair");
             return;
         }
         // condition cannot duplicate
         for (int i = 1; i < tokenList.size(); i++) {
             Token token = tokenList.get(i);
             if (token.type == Token.And) {
                 checkAnd(tokenList, i);
             } else if (token.type == Token.Or) {
                 checkOr(tokenList, i);
             } else if (token.type == Token.StartParenthesis) {
                 checkStartParenthesis(tokenList, i);
             } else if (token.type == Token.EndParenthesis) {
                 checkEndParenthesis(tokenList, i);
             } else if (token.type == Token.Condition) {
                 checkCondition(tokenList, i);
             }
         }
     }
 
     private int countToken(List<Token> tokenList, int type) {
         int count = 0;
         for (Token t : tokenList) {
             if (t.type == type) {
                 count++;
             }
         }
         return count;
     }
 
     private void checkAnd(List<Token> tokenList, int currentIndex) {
         if ((tokenList.get(currentIndex - 1).type == Token.Condition || tokenList.get(currentIndex - 1).type == Token.EndParenthesis) == false) {
             errorMessageList.add("only ) and condition could sit before and");
         }
         if (currentIndex == tokenList.size() - 1) {
             return;
         }
         if ((tokenList.get(currentIndex + 1).type == Token.Condition || tokenList.get(currentIndex + 1).type == Token.StartParenthesis) == false) {
             errorMessageList.add("only ( and condition could sit after and");
         }
 
     }
 
     private void checkOr(List<Token> tokenList, int currentIndex) {
         if ((tokenList.get(currentIndex - 1).type == Token.Condition || tokenList.get(currentIndex - 1).type == Token.EndParenthesis) == false) {
             errorMessageList.add("only ) and condition could sit before or");
         }
         if (currentIndex == tokenList.size() - 1) {
             return;
         }
         if ((tokenList.get(currentIndex + 1).type == Token.Condition || tokenList.get(currentIndex + 1).type == Token.StartParenthesis) == false) {
             errorMessageList.add("only ( and condition could sit after or");
         }
     }
 
     private void checkStartParenthesis(List<Token> tokenList, int currentIndex) {
         if ((tokenList.get(currentIndex - 1).type == Token.And || tokenList.get(currentIndex - 1).type == Token.Or || tokenList.get(currentIndex - 1).type == Token.StartParenthesis) == false) {
             errorMessageList.add("only and, or, ( could sit before (");
         }
         if (currentIndex == tokenList.size() - 1) {
             return;
         }
         if ((tokenList.get(currentIndex + 1).type == Token.Condition || tokenList.get(currentIndex + 1).type == Token.StartParenthesis) == false) {
             errorMessageList.add("only ( and condition could sit after (");
         }
 
     }
 
     private void checkEndParenthesis(List<Token> tokenList, int currentIndex) {
         if ((tokenList.get(currentIndex - 1).type == Token.Condition || tokenList.get(currentIndex - 1).type == Token.EndParenthesis) == false) {
             errorMessageList.add("only condition and ) could sit before )");
         }
         if (currentIndex == tokenList.size() - 1) {
             return;
         }
         if ((tokenList.get(currentIndex + 1).type == Token.Or || tokenList.get(currentIndex + 1).type == Token.And || tokenList.get(currentIndex + 1).type == Token.EndParenthesis) == false) {
             errorMessageList.add("only ), and, or could sit after )");
         }
 
     }
 
     private void checkCondition(List<Token> tokenList, int currentIndex) {
         if ((tokenList.get(currentIndex - 1).type == Token.And || tokenList.get(currentIndex - 1).type == Token.Or || tokenList.get(currentIndex - 1).type == Token.StartParenthesis) == false) {
             errorMessageList.add("only and, or could sit before condition");
         }
         if (currentIndex == tokenList.size() - 1) {
             return;
         }
         if ((tokenList.get(currentIndex + 1).type == Token.Or || tokenList.get(currentIndex + 1).type == Token.And || tokenList.get(currentIndex + 1).type == Token.EndParenthesis) == false) {
             errorMessageList.add("only ), and, or could sit after condition");
         }
 
     }
 
     private List<Token> getTokenList(List<String> tokenValueList) {
         List<Token> tokenList = new ArrayList<Token>();
         for (String value : tokenValueList) {
             if (value.isEmpty()) {
                 continue;
             }
             if ("(".equals(value)) {
                 Token t = new Token();
                 t.type = Token.StartParenthesis;
                 tokenList.add(t);
             } else if (")".equals(value)) {
                 Token t = new Token();
                 t.type = Token.EndParenthesis;
                 tokenList.add(t);
 
             } else if ("and".equals(value)) {
                 Token t = new Token();
                 t.type = Token.And;
                 tokenList.add(t);
 
             } else if ("or".equals(value)) {
                 Token t = new Token();
                 t.type = Token.Or;
                 tokenList.add(t);
 
             } else {
                 Token t = new Token();
                 t.type = Token.Condition;
                 t.value = value;
                 tokenList.add(t);
 
             }
         }
         return tokenList;
     }
 
     private List<String> getTokenValue(String expression) {
         expression = expression.toLowerCase();
         List<String> tokenValueList = new ArrayList<String>();
         StringBuffer tokenValue = new StringBuffer();
         for (int i = 0; i < expression.length(); i++) {
 
             char ch = expression.charAt(i);
             if (ch == ' ') {
                 tokenValueList.add(tokenValue.toString());
                 tokenValue = new StringBuffer();
             } else if (ch == '(' || ch == ')') {
                 tokenValueList.add(tokenValue.toString());
                 tokenValue = new StringBuffer();
                 tokenValueList.add(String.valueOf(ch));
             } else {
                 tokenValue.append(ch);
             }
         }
         tokenValueList.add(tokenValue.toString());
         return tokenValueList;
     }
 }
 

1		/**
2		* Copyright 2010 The Kuali Foundation Licensed under the
3		* Educational Community License, Version 2.0 (the "License"); you may
4		* not use this file except in compliance with the License. You may
5		* obtain a copy of the License at
6		*
7		* http://www.osedu.org/licenses/ECL-2.0
8		*
9		* Unless required by applicable law or agreed to in writing,
10		* software distributed under the License is distributed on an "AS IS"
11		* BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
12		* or implied. See the License for the specific language governing
13		* permissions and limitations under the License.
14		*/
15
16		package org.kuali.student.common.ui.client.widgets.table;
17
18		import java.util.ArrayList;
19		import java.util.List;
20		import java.util.Stack;
21
22		import org.kuali.student.common.ui.client.widgets.rules.Token;
23
24		/**
25		* This is the parser for boolean expression.
26		* It checks the error, creates the Reverse Polish notation,
27		* merge the binary tree, sort the nodes.
28		*
29		* */
30		public class ExpressionParser {
31		/**
32		* Error messages are stored in a list
33		* */
34	0	private List<String> errorMessageList = new ArrayList<String>();
35
36	0	public ExpressionParser() {
37	0	}
38		/**
39		* After parsing, it tells if the expression has error.
40		*
41		* @return If the input expression has error
42		* */
43		public boolean hasError(){
44	0	return errorMessageList.size() > 0;
45		}
46		/**
47		* It returns all error messages
48		*
49		* @return List of error messages
50		* */
51		public List<String> getErrorMessage(){
52	0	return errorMessageList;
53		}
54		/**
55		* Parse the boolean expression
56		*
57		* @return the tree of input tokens
58		* */
59		public Node<Token> parse(String expression) {
60	0	errorMessageList = new ArrayList<String>();
61	0	List<String> tokenValueList = getTokenValue(expression);
62	0	List<Token> tokenList = getTokenList(tokenValueList);
63	0	errorCheck(tokenList);
64	0	if(hasError()){
65	0	return null;
66		}
67	0	List<Node<Token>> nodeList = toNodeList(tokenList);
68	0	List<Node<Token>> rpnList = getRPN(nodeList);
69
70	0	Node<Token> root = binaryTreeFromRPN(rpnList);
71
72		//Node<Token> ruleRoot = root;
73	0	Node<Token> ruleRoot = mergeBinaryTree(root);
74
75
76		// ruleRoot = reStructure(root);
77	0	ruleRoot = orderLeafChildren(ruleRoot, tokenList );
78	0	ruleRoot = orderNonLeafChildren(ruleRoot, tokenList );
79	0	return ruleRoot;
80		}
81		/**
82		* Create the boolean expression from tree
83		*
84		* @return boolean expression
85		* */
86		public static String getExpressionString(Node root){
87	0	while(root.getChildCount()> 1){
88	0	List<List<Node>> level = root.toLevel();
89	0	for(Node<Token> n: level.get(level.size()-1)){
90	0	if(n.isLeaf() && n.getParent() != null){
91	0	Node parent = n.getParent();
92	0	StringBuilder sb = new StringBuilder();
93	0	if(parent.getChildAt(0).getUserObject() instanceof ExpressionNode
94		&& parent.getChildAt(0).getUserObject() instanceof ExpressionNode
95		&& (( ExpressionNode)parent.getChildAt(0).getUserObject()).token.type == Token.Or
96		&& (( Token)parent.getUserObject()).type == Token.And){
97	0	sb.append(" ( "+parent.getChildAt(0).getUserObject().toString()+" ) ");
98		}else{
99	0	sb.append(" "+parent.getChildAt(0).getUserObject().toString()+" ");
100		}
101
102
103	0	for(int i=1;i<parent.getChildCount();i++){
104	0	Node child = parent.getChildAt(i);
105
106	0	if(parent.getChildAt(i).getUserObject() instanceof ExpressionNode
107		&& parent.getChildAt(i).getUserObject() instanceof ExpressionNode
108		&& (( ExpressionNode)parent.getChildAt(i).getUserObject()).token.type == Token.Or
109		&& (( Token)parent.getUserObject()).type == Token.And){
110	0	sb.append(parent.getUserObject().toString()+ " ( "+
111		child.getUserObject().toString()+" ) ");
112
113		}else{
114	0	sb.append(" "+parent.getUserObject().toString()+ " "+
115		child.getUserObject().toString()+" ");
116		}
117		}
118	0	ExpressionNode expressionNode = new ExpressionNode();
119	0	expressionNode.token = (Token)parent.getUserObject();
120	0	expressionNode.expression = sb.toString();
121	0	parent.setUserObject(expressionNode);
122	0	parent.removeAllChildren();
123	0	break;
124		}
125		}
126
127	0	}
128
129
130	0	return root.getUserObject().toString();
131		}
132		/**
133		* Order the nonleaf children
134		* */
135		private Node<Token> orderNonLeafChildren(Node<Token> binaryTree,List<Token> tokenList ) {
136	0	List<Node> list = binaryTree.getNonLeafChildren();
137	0	if(list.size() > 1){
138	0	sequeceNonLeaves(list, tokenList);
139	0	binaryTree.children().removeAll(list);
140	0	for(Node n: list){
141	0	binaryTree.addNode(n);
142		}
143		}
144	0	for(Node n: binaryTree.children()){
145	0	if(n.isLeaf() == false){
146	0	orderNonLeafChildren(n,tokenList );
147		}
148		}
149
150	0	List<Node> nonLeafChildList = binaryTree.getNonLeafChildren();
151	0	List<Node> leafChildList = binaryTree.getLeafChildren();
152	0	binaryTree.children().removeAll(nonLeafChildList);
153	0	binaryTree.children().removeAll(leafChildList);
154	0	for(Node n: nonLeafChildList){
155	0	binaryTree.addNode(n);
156		}
157
158	0	for(Node n: leafChildList){
159	0	binaryTree.addNode(n);
160		}
161	0	return binaryTree;
162		}
163		/**
164		* Order the non leaves
165		* */
166		private void sequeceNonLeaves(List<Node> nonLeafChildList, List<Token> list){
167	0	if(nonLeafChildList.size() == 2){
168	0	if (indexInInputTokenList((Token)nonLeafChildList.get(0).getFirstLeafDescendant().getUserObject(), list)>
169		indexInInputTokenList((Token)nonLeafChildList.get(1).getFirstLeafDescendant().getUserObject(), list)) {
170	0	Node buffer = nonLeafChildList.get(0);
171	0	nonLeafChildList.remove(0);
172	0	nonLeafChildList.add(buffer);
173		}
174		}
175	0	for (int out = nonLeafChildList.size() - 1; out > 1; out--){
176	0	for (int in = 0; in < out; in++){
177		// inner loop (forward)
178	0	if (indexInInputTokenList((Token)nonLeafChildList.get(in).getFirstLeafDescendant().getUserObject(), list)>
179		indexInInputTokenList((Token)nonLeafChildList.get(in + 1).getFirstLeafDescendant().getUserObject(), list)) {
180		// swap them
181	0	Node node = nonLeafChildList.get(in);
182	0	nonLeafChildList.remove(in);
183	0	nonLeafChildList.add(in+1, node);
184		}
185		}
186		}
187	0	}
188		/**
189		* Order the leaf children
190		* */
191		private Node<Token> orderLeafChildren(Node<Token> binaryTree,List<Token> tokenList ) {
192	0	List<Node> list = binaryTree.getLeafChildren();
193	0	if(list.size() > 1){
194	0	sequeceLeaves(list, tokenList);
195	0	binaryTree.children().removeAll(list);
196	0	for(Node n: list){
197	0	binaryTree.addNode(n);
198		}
199		}
200	0	for(Node n: binaryTree.children()){
201	0	if(n.isLeaf() == false){
202	0	orderLeafChildren(n,tokenList );
203		}
204		}
205	0	return binaryTree;
206		}
207		/*Reorder the children/
208		private void sequeceLeaves(List<Node> leafChildList, List<Token> list){
209	0	if(leafChildList.size() == 2){
210	0	if (indexInInputTokenList((Token)leafChildList.get(0).getUserObject(), list)>
211		indexInInputTokenList((Token)leafChildList.get(1).getUserObject(), list)) {
212		// swap them
213	0	Token buffer = (Token)leafChildList.get(0).getUserObject();
214	0	leafChildList.get(0).setUserObject(leafChildList.get(1).getUserObject());
215	0	leafChildList.get(1).setUserObject(buffer);
216		}
217
218		}
219
220	0	for (int out = leafChildList.size() - 1; out > 1; out--){
221	0	for (int in = 0; in < out; in++){
222		// inner loop (forward)
223	0	if (indexInInputTokenList((Token)leafChildList.get(in).getUserObject(), list)>
224		indexInInputTokenList((Token)leafChildList.get(in + 1).getUserObject(), list)) {
225		// swap them
226	0	Token buffer = (Token)leafChildList.get(in).getUserObject();
227	0	leafChildList.get(in).setUserObject(leafChildList.get(in + 1).getUserObject());
228	0	leafChildList.get(in + 1).setUserObject(buffer);
229		}
230		}
231		}
232	0	}
233		/*Get the index of a token in the token list/
234		private int indexInInputTokenList(Token token, List<Token> list){
235	0	int i = -1;
236	0	for(Token n: list){
237	0	if(n.value != null && token.value != null && n.value.equals(token.value)){
238	0	return i;
239		}
240	0	i++;
241		}
242	0	return i;
243		}
244
245		/* public static Node<Token> reStructure(Node<Token> binaryTree) {
246		Node root = new Node();
247		//Node root = binaryTree;
248		root.setUserObject(binaryTree.getUserObject());
249		List<Node> childList = binaryTree.children();
250
251		ListIterator<Node> itr = childList.listIterator();
252		for (; itr.hasNext();) {
253		Node node = getDeeperNode(childList);
254		if (node.isLeaf()) {
255		root.addNode(node);
256		} else {
257		root.addNode(reStructure(node));
258		}
259		childList.remove(node);
260		}
261
262		return root.clone();
263		}
264		*/
265		private static Node getDeeperNode(List<Node> nodeList) {
266	0	int childCount = 0;
267	0	for (Node node : nodeList) {
268	0	if (childCount < node.getAllChildren().size()) {
269	0	childCount = node.getAllChildren().size();
270		}
271		}
272	0	for (Node node : nodeList) {
273	0	if (childCount == node.getAllChildren().size()) {
274	0	return node;
275		}
276		}
277
278	0	return null;
279		}
280		/** Merge the binary tree. */
281		public static Node<Token> mergeBinaryTree(Node<Token> binaryTree) {
282	0	while (parentEqualsGrandParent(binaryTree)) {
283	0	List<Node<Token>> list = binaryTree.getAllChildren();
284
285	0	for (Node node : list) {
286	0	if (node.getParent() != null && node.getParent().getParent() != null) {
287	0	Node parentNode = node.getParent();
288	0	Node grandParentNode = node.getParent().getParent();
289	0	Token parentToken = (Token) parentNode.getUserObject();
290	0	Token grandParentToken = (Token) grandParentNode.getUserObject();
291
292	0	if (parentToken.type == grandParentToken.type) {
293	0	for (int i = 0; i < parentNode.getChildCount(); i++) {
294	0	Node n = parentNode.getChildAt(i);
295	0	grandParentNode.addNode(n);
296		}
297	0	grandParentNode.remove(parentNode);
298		}
299	0	}
300		}
301	0	}
302	0	return binaryTree;
303		}
304
305		private static boolean parentEqualsGrandParent(Node<Token> binaryTree) {
306	0	List<Node<Token>> list = binaryTree.getAllChildren();
307
308	0	for (Node node : list) {
309	0	if (node.getParent() != null && node.getParent().getParent() != null) {
310
311	0	Token parentToken = (Token) node.getParent().getUserObject();
312	0	Token grandParentToken = (Token) node.getParent().getParent().getUserObject();
313	0	if (parentToken.type == grandParentToken.type) {
314	0	return true;
315		}
316	0	}
317		}
318
319	0	return false;
320		}
321		/** Build the binary tree from list of tokens*/
322		private Node<Token> binaryTreeFromRPN(List<Node<Token>> rpnList) {
323	0	Stack<Node<Token>> conditionStack = new Stack<Node<Token>>();
324	0	for (Node<Token> node : rpnList) {
325	0	if (node.getUserObject().type == Token.Condition) {
326	0	conditionStack.push(node);
327	0	} else if (node.getUserObject().type == Token.And \|\| node.getUserObject().type == Token.Or) {
328	0	Node<Token> left = conditionStack.pop();
329	0	Node<Token> right = conditionStack.pop();
330	0	node.addNode(left);
331	0	node.addNode(right);
332	0	conditionStack.push(node);
333	0	}
334		}
335
336	0	return conditionStack.pop();
337		}
338
339		/**
340		* If higher push to stack, else pop till less than or equal, add to list push to stack if ( push to stack if ) pop to
341		* list till (.
342		*
343		* http://en.wikipedia.org/wiki/Reverse_Polish_notation
344		*
345		*/
346		private List<Node<Token>> getRPN(List<Node<Token>> nodeList) {
347	0	List<Node<Token>> rpnList = new ArrayList<Node<Token>>();
348	0	Stack<Node<Token>> operatorStack = new Stack<Node<Token>>();
349
350	0	for (Node<Token> node : nodeList) {
351	0	if (node.getUserObject().type == Token.Condition) {
352	0	rpnList.add(node);
353
354	0	} else if (node.getUserObject().type == Token.And) {
355	0	operatorStack.push(node);
356	0	} else if (node.getUserObject().type == Token.StartParenthesis) {
357	0	operatorStack.push(node);
358	0	} else if (node.getUserObject().type == Token.Or) {
359
360	0	if (operatorStack.isEmpty() == false && operatorStack.peek().getUserObject().type == Token.And) {
361		do {
362	0	rpnList.add(operatorStack.pop());
363	0	} while (operatorStack.isEmpty() == false && operatorStack.peek().getUserObject().type == Token.And);
364		}
365
366	0	operatorStack.push(node);
367	0	} else if (node.getUserObject().type == Token.EndParenthesis) {
368	0	while (operatorStack.peek().getUserObject().type != Token.StartParenthesis) {
369	0	rpnList.add(operatorStack.pop());
370		}
371	0	operatorStack.pop();// pop the (
372		}
373		}
374	0	if (operatorStack.isEmpty() == false) {
375		do {
376	0	rpnList.add(operatorStack.pop());
377	0	} while (operatorStack.isEmpty() == false);
378		}
379	0	return rpnList;
380		}
381
382		private int findNodeIndex(List<Node<Token>> nodeList, int type) {
383	0	int index = -1;
384	0	for (Node<Token> node : nodeList) {
385	0	index++;
386	0	if (node.getUserObject().type == type) {
387	0	return index;
388		}
389		}
390	0	return index;
391		}
392
393		private boolean hasParenthesis(List<Node<Token>> nodeList) {
394	0	boolean has = false;
395	0	for (Node<Token> node : nodeList) {
396	0	if (node.getUserObject().type == Token.StartParenthesis) {
397	0	return true;
398		}
399		}
400	0	return has;
401		}
402
403		private List<Node<Token>> toNodeList(List<Token> tokenList) {
404	0	List<Node<Token>> nodeList = new ArrayList<Node<Token>>();
405	0	for (Token token : tokenList) {
406	0	Node<Token> node = new Node<Token>();
407	0	node.setUserObject(token);
408	0	nodeList.add(node);
409	0	}
410	0	return nodeList;
411		}
412
413		private void errorCheck(List<Token> tokenList) {
414	0	if (tokenList.size() == 0) {
415	0	errorMessageList.add("empty input");
416	0	return;
417		}
418	0	if (tokenList.size() <= 2) {
419	0	errorMessageList.add("input not complete");
420	0	return;
421		}
422	0	if ((tokenList.get(0).type == Token.StartParenthesis
423		\|\| tokenList.get(0).type == Token.Condition) == false) {
424	0	errorMessageList.add("must start with ( or condition");
425	0	return;
426		}
427	0	int lastIndex = tokenList.size() - 1;
428	0	if ((tokenList.get(lastIndex).type == Token.EndParenthesis \|\| tokenList.get(lastIndex).type == Token.Condition) == false) {
429	0	errorMessageList.add("must end with ) or condition");
430	0	return;
431		}
432	0	if (countToken(tokenList, Token.StartParenthesis) != countToken(tokenList, Token.EndParenthesis)) {
433	0	errorMessageList.add("() not in pair");
434	0	return;
435		}
436		// condition cannot duplicate
437	0	for (int i = 1; i < tokenList.size(); i++) {
438	0	Token token = tokenList.get(i);
439	0	if (token.type == Token.And) {
440	0	checkAnd(tokenList, i);
441	0	} else if (token.type == Token.Or) {
442	0	checkOr(tokenList, i);
443	0	} else if (token.type == Token.StartParenthesis) {
444	0	checkStartParenthesis(tokenList, i);
445	0	} else if (token.type == Token.EndParenthesis) {
446	0	checkEndParenthesis(tokenList, i);
447	0	} else if (token.type == Token.Condition) {
448	0	checkCondition(tokenList, i);
449		}
450		}
451	0	}
452
453		private int countToken(List<Token> tokenList, int type) {
454	0	int count = 0;
455	0	for (Token t : tokenList) {
456	0	if (t.type == type) {
457	0	count++;
458		}
459		}
460	0	return count;
461		}
462
463		private void checkAnd(List<Token> tokenList, int currentIndex) {
464	0	if ((tokenList.get(currentIndex - 1).type == Token.Condition \|\| tokenList.get(currentIndex - 1).type == Token.EndParenthesis) == false) {
465	0	errorMessageList.add("only ) and condition could sit before and");
466		}
467	0	if (currentIndex == tokenList.size() - 1) {
468	0	return;
469		}
470	0	if ((tokenList.get(currentIndex + 1).type == Token.Condition \|\| tokenList.get(currentIndex + 1).type == Token.StartParenthesis) == false) {
471	0	errorMessageList.add("only ( and condition could sit after and");
472		}
473
474	0	}
475
476		private void checkOr(List<Token> tokenList, int currentIndex) {
477	0	if ((tokenList.get(currentIndex - 1).type == Token.Condition \|\| tokenList.get(currentIndex - 1).type == Token.EndParenthesis) == false) {
478	0	errorMessageList.add("only ) and condition could sit before or");
479		}
480	0	if (currentIndex == tokenList.size() - 1) {
481	0	return;
482		}
483	0	if ((tokenList.get(currentIndex + 1).type == Token.Condition \|\| tokenList.get(currentIndex + 1).type == Token.StartParenthesis) == false) {
484	0	errorMessageList.add("only ( and condition could sit after or");
485		}
486	0	}
487
488		private void checkStartParenthesis(List<Token> tokenList, int currentIndex) {
489	0	if ((tokenList.get(currentIndex - 1).type == Token.And \|\| tokenList.get(currentIndex - 1).type == Token.Or \|\| tokenList.get(currentIndex - 1).type == Token.StartParenthesis) == false) {
490	0	errorMessageList.add("only and, or, ( could sit before (");
491		}
492	0	if (currentIndex == tokenList.size() - 1) {
493	0	return;
494		}
495	0	if ((tokenList.get(currentIndex + 1).type == Token.Condition \|\| tokenList.get(currentIndex + 1).type == Token.StartParenthesis) == false) {
496	0	errorMessageList.add("only ( and condition could sit after (");
497		}
498
499	0	}
500
501		private void checkEndParenthesis(List<Token> tokenList, int currentIndex) {
502	0	if ((tokenList.get(currentIndex - 1).type == Token.Condition \|\| tokenList.get(currentIndex - 1).type == Token.EndParenthesis) == false) {
503	0	errorMessageList.add("only condition and ) could sit before )");
504		}
505	0	if (currentIndex == tokenList.size() - 1) {
506	0	return;
507		}
508	0	if ((tokenList.get(currentIndex + 1).type == Token.Or \|\| tokenList.get(currentIndex + 1).type == Token.And \|\| tokenList.get(currentIndex + 1).type == Token.EndParenthesis) == false) {
509	0	errorMessageList.add("only ), and, or could sit after )");
510		}
511
512	0	}
513
514		private void checkCondition(List<Token> tokenList, int currentIndex) {
515	0	if ((tokenList.get(currentIndex - 1).type == Token.And \|\| tokenList.get(currentIndex - 1).type == Token.Or \|\| tokenList.get(currentIndex - 1).type == Token.StartParenthesis) == false) {
516	0	errorMessageList.add("only and, or could sit before condition");
517		}
518	0	if (currentIndex == tokenList.size() - 1) {
519	0	return;
520		}
521	0	if ((tokenList.get(currentIndex + 1).type == Token.Or \|\| tokenList.get(currentIndex + 1).type == Token.And \|\| tokenList.get(currentIndex + 1).type == Token.EndParenthesis) == false) {
522	0	errorMessageList.add("only ), and, or could sit after condition");
523		}
524
525	0	}
526
527		private List<Token> getTokenList(List<String> tokenValueList) {
528	0	List<Token> tokenList = new ArrayList<Token>();
529	0	for (String value : tokenValueList) {
530	0	if (value.isEmpty()) {
531	0	continue;
532		}
533	0	if ("(".equals(value)) {
534	0	Token t = new Token();
535	0	t.type = Token.StartParenthesis;
536	0	tokenList.add(t);
537	0	} else if (")".equals(value)) {
538	0	Token t = new Token();
539	0	t.type = Token.EndParenthesis;
540	0	tokenList.add(t);
541
542	0	} else if ("and".equals(value)) {
543	0	Token t = new Token();
544	0	t.type = Token.And;
545	0	tokenList.add(t);
546
547	0	} else if ("or".equals(value)) {
548	0	Token t = new Token();
549	0	t.type = Token.Or;
550	0	tokenList.add(t);
551
552	0	} else {
553	0	Token t = new Token();
554	0	t.type = Token.Condition;
555	0	t.value = value;
556	0	tokenList.add(t);
557
558	0	}
559		}
560	0	return tokenList;
561		}
562
563		private List<String> getTokenValue(String expression) {
564	0	expression = expression.toLowerCase();
565	0	List<String> tokenValueList = new ArrayList<String>();
566	0	StringBuffer tokenValue = new StringBuffer();
567	0	for (int i = 0; i < expression.length(); i++) {
568
569	0	char ch = expression.charAt(i);
570	0	if (ch == ' ') {
571	0	tokenValueList.add(tokenValue.toString());
572	0	tokenValue = new StringBuffer();
573	0	} else if (ch == '(' \|\| ch == ')') {
574	0	tokenValueList.add(tokenValue.toString());
575	0	tokenValue = new StringBuffer();
576	0	tokenValueList.add(String.valueOf(ch));
577		} else {
578	0	tokenValue.append(ch);
579		}
580		}
581	0	tokenValueList.add(tokenValue.toString());
582	0	return tokenValueList;
583		}
584		}
585