Bài tập lớn 01 - Biểu diễn và tính toán biểu thức

/* Vu Ngoc Tung
 * K55CC - UET
 */


import java.util.*;

// Class ExpNode - node of binary tree Expression
class ExpNode
{   protected char literal;      // Variable of Expression
   protected char operator;   // Operator of Expression
   protected int number;      // Number of Expression
   
   // Pointer field
   protected ExpNode left;
   protected ExpNode right;
   // Default constructor
   protected ExpNode()
   {   left = right = null;
   }
   // Constructor with an available value
   protected ExpNode(int _num)
   {   number = _num;
      left = right = null;
   }
   // Constructor with an available value
   protected ExpNode(char _tmpChar)
   {   if( _tmpChar == '+' || _tmpChar == '-' ||
         _tmpChar == '*' || _tmpChar == '/')      // If is's an operator
         operator = _tmpChar;
      else
         literal = _tmpChar;
      left = right = null;
   }
   // Compare operators and return priority of its
   protected int priorityOfOpr(char _opr)
   {   if(_opr == '*' || _opr == '/')   // High priority operators
         return 2;
      else                     // Lower priority operators
         return 1;
   }
   // Check a element
   protected boolean isLeaf()
   {   if(this.left == null && this.right == null)
         return true;
      return false;
   }
}// end class ExpNode

// Class Expression - A Binary Tree
class Expression extends ExpNode
{   private ExpNode root;      // Root of binary tree

   // Default constructor
   public Expression()
   {   root = null;
   }
   // Return root of tree
   public ExpNode getRoot()
   {   return this.root;
   }
   // Constructor with an available value
   public Expression(int _num)
   {   root = new ExpNode(_num);
   }
   // Constructor with an available value
   public Expression(char _tmpChar)
   {   root = new ExpNode(_tmpChar);
   }
   // Method to add an operator and a number into available expression
   public Expression append(int _num, char _operator)
   {   ExpNode node1 = new ExpNode(_operator);
      ExpNode node2 = new ExpNode(_num);
      this.insert(node1, node2);
      return this;
   }
   // Method to add an operator and a literal into available expression
   public Expression append(char _literal, char _operator)
   {   ExpNode node1 = new ExpNode(_operator);
      ExpNode node2 = new ExpNode(_literal);
      this.insert(node1, node2);
      return this;
   }
   // Method to add an operator and an expression into available expression
   public Expression append(Expression _tmpExp, char _operator)
   {   ExpNode node1 = new ExpNode(_operator);
      node1.left = root;
      node1.right = _tmpExp.root;
      root = node1;
      return this;
   }
   // Assign a value for a variable
   public boolean setValue(char _tmpCh, int _num)
   {   int count = setValueAt(this.root, _tmpCh, _num);
      if(count >= 0)
      {   System.out.println(" Variable " +_tmpCh+ " = " +_num);
         return true;
      }
      else
         return false;
   }
   // Calculate expression
   public int eval()
   {   this.evalAt(root);
      return root.number;
   }
   // Return expression
   public String print()
   {   return this.printAt(root);
   }
   
   /*--------------------------------- Private field ----------------------------------*/
   // Check a right node of node
   private boolean checkRightExpn(ExpNode node)
   {   if(node.isLeaf() == true)
         return false;
      else
      {   ExpNode nodeRR = node.right;
         if(nodeRR.isLeaf() == true)
            return true;
         else return false;
      }
   }
   // Insert a node in the available tree
   private void insert(ExpNode node1, ExpNode node2)
   {   ExpNode nodeRR = root.right;
      if(root.isLeaf() == true)
      {   node1.left = root;
         node1.right = node2;
         root = node1;
      }
      else
         if(nodeRR.isLeaf() == true)
         {   node1.left = root.right;
            node1.right = node2;
            root.right = node1;
         }
         else
         {   ExpNode tmpNode1 = root;
            while(checkRightExpn(nodeRR) != true)
            {   tmpNode1 = tmpNode1.right;
               nodeRR = nodeRR.right;
            }
            // Compare priority of 2 operators
            if( priorityOfOpr(node1.operator) <= priorityOfOpr(nodeRR.operator) )
            {   node1.left = nodeRR;
               node1.right = node2;
               tmpNode1.right = node1;
            }
            else
            {   node1.left = nodeRR.right;
               node1.right = node2;
               nodeRR.right = node1;
            }
         }
   }
   // Calculate the value of the expression and assigns the root of binary tree
   private int evalAt(ExpNode node) throws ArithmeticException
   {   if(node.isLeaf() == true)
         return node.number;
      else
      {   int x = evalAt(node.left);
         int y = evalAt(node.right);
         try
         {   switch(node.operator)
            {   case '+': node.number = x + y; break;
               case '-': node.number = x - y; break;
               case '*': node.number = x * y; break;
               case '/': node.number = x / y; break;
            }
         } catch(ArithmeticException e)
         {   System.out.println(" Infinity");
         }
      }
      return node.number;
   }
   // Find and assign a value for a variable
   private int setValueAt(ExpNode root, char _tmpCh, int _num)
   {   int count = 0;
      if(root.isLeaf() != true)
      {   setValueAt(root.left, _tmpCh, _num);
         setValueAt(root.right, _tmpCh, _num);
      }
      else
         if(root.literal == _tmpCh)
         {   root.number = _num;
            count++;
         }
      return count;
   }
   // Return a node data by string value
   private String returnNode(ExpNode node)
   {   String result = new String();
      if(node.literal == '\0')
         result += node.number;
      else
         result += node.literal;
      return result;
   }
   // Display the expression to screen
   private String printAt(ExpNode node)
   {   String result = new String();
      if(node.isLeaf() == true)
         result = returnNode(node);
      else
      {   ExpNode node1 = node.left;
         ExpNode node2 = node.right;
         if(node1.isLeaf() == true)
            result += returnNode(node1);
         else
            if( priorityOfOpr(node.operator) > priorityOfOpr(node1.operator) )
               result += "(" + printAt(node1) + ")";
            else
               result += printAt(node1);
         result += node.operator;
         if(node2.isLeaf() == true)
            result += returnNode(node2);
         else
            if( priorityOfOpr(node.operator) > priorityOfOpr(node2.operator) )
               result += "(" + printAt(node2) + ")";
            else
               result += printAt(node2);
      }
      return result;
   }
}// end class Expression