Sunday, September 28, 2014

AVL Tree - Height Balancing Binary Search Tree (BST) Implementation [Java]

This program implements AVL tree (written in Java). AVL trees are binary search trees which automatically balance their heights after insertion of elements or removal of existing elements.

A post on BSTs :

http://coderbots.blogspot.in/2014/09/binary-search-tree-operations-find.html

Source:

import java.util.Scanner;

public class AVL {

    Node root;

    class Node {

        Node father, left, right;
        int height = 0;
        int key;

        public Node(int key, Node left, Node right, Node father) {
            this.key = key;
            this.left = left;
            this.right = right;
            this.father = father;
        }

        public String toString() {
            return "key = " + key + " height = " + height;
        }
    }

    public void insert(Node toInsert, Node node) {
        if (root == null) {
            root = toInsert;
            return;
        }

        if (toInsert.key < node.key) {
            if (node.left != null) {
                insert(toInsert, node.left);
                return;
            } else {
                toInsert.father = node;
                node.left = toInsert;
            }
        } else if (toInsert.key >= node.key) {
            if (node.right != null) {
                insert(toInsert, node.right);
                return;
            } else {
                toInsert.father = node;
                node.right = toInsert;
            }
        }
        updateHeights(toInsert);
        balance(toInsert);
    }

    public Node findNode(Node findNode, Node node) {
        if (root == null) {
            return null;
        }

        if (findNode.key < node.key) {
            if (node.left != null) {
                return findNode(findNode, node.left);
            }
        } else if (findNode.key > node.key) {
            if (node.right != null) {
                return findNode(findNode, node.right);
            }
        } else if (findNode.key == node.key) {
            return node;
        }
        return null;
    }

    public boolean deleteNode(Node deleteNode, Node node) {
        if (root == null) {
            return false;
        } else if (root.key == deleteNode.key) {
            if (root.left == null && root.right == null) {
                root = null;
            } else if (root.left == null) {
                root = root.right;
                root.father = null;
            } else if (root.right == null) {
                root = root.left;
                root.father = null;
            } else {
                Node min = root.right;
                //min element has no left or right child.
                if (min.left == null && min.right == null) {
                    root.key = min.key;
                    root.right = null;
                    updateHeights(root);
                    balance(root);
                    return true;
                }
                while (min.left != null) {
                    //Min element has left child.
                    min = min.left;
                }
                root.key = min.key;
                if (min.right != null) {
                    min.right.father = min.father;
                }
                //Min element has no left child but has right child.
                if (min.father != root) {
                    min.father.left = min.right; 
                } else {
                    min.father.right = min.right; 
                }
                updateHeights(min.father);
                balance(min.father);
            }
            return true;
        } else {
            Node locatedNode = findNode(deleteNode, root);
            if (locatedNode != null) {
                deleteHelper(locatedNode);
            } else {
                return false;
            }
        }
        return true;
    }

    private void deleteHelper(Node locatedNode) {
        boolean left = (locatedNode.father.left == locatedNode);
        if (locatedNode.right == null && locatedNode.left == null) {
            if (left) {
                locatedNode.father.left = null;
            } else {
                locatedNode.father.right = null;
            } 
        } else if (locatedNode.left != null && locatedNode.right == null) {
            locatedNode.left.father = locatedNode.father;
            if (left) {
                locatedNode.father.left = locatedNode.left;
            } else {
                locatedNode.father.right = locatedNode.left;
            }
        } else if (locatedNode.left == null && locatedNode.right != null) {
            locatedNode.right.father = locatedNode.father;
            if (left) {
                locatedNode.father.left = locatedNode.right;
            } else {
                locatedNode.father.right = locatedNode.right;
            }
        } else if (locatedNode.left != null && locatedNode.right != null) {
            Node min = locatedNode.right;
            //min element has no left or right child.
            if (min.left == null && min.right == null) {
                locatedNode.key = min.key;
                locatedNode.right = null;
                return;
            }
            while (min.left != null) {
                //Min element has left child.
                min = min.left;
            }
            locatedNode.key = min.key;
            if (min.right != null) {
                min.right.father = min.father;
            }
            //Min element has no left child but has right child.
            if (min.father != locatedNode) {
                min.father.left = min.right;
            } else {
                min.father.right = min.right;
            }
            updateHeights(min.father);
            balance(min.father); 
            return;
        }
        updateHeights(locatedNode.father);
        balance(locatedNode.father);
    }

    public void deleteTree() {
        root = null;
    }

    public void printTree(Node node) {
        if (node == null) {
            return;
        }
        printTree(node.left);
        System.out.print(node + "\n");
        printTree(node.right);
    }

    public void consoleUI() {
        Scanner scan = new Scanner(System.in);
        while (true) {
            System.out.println("\n1.- Add items\n"
                    + "2.- Delete items\n"
                    + "3.- Check items\n"
                    + "4.- Print tree\n"
                    + "5.- Delete tree\n");
            int choice = scan.nextInt();

            int item;
            Node node;
            switch (choice) {
                case 1:
                    item = scan.nextInt();
                    while (item != -999) {
                        node = new Node(item, null, null, null);
                        insert(node, root);
                        item = scan.nextInt();
                    }
                    printTree(root);
                    break;
                case 2:
                    item = scan.nextInt();
                    while (item != -999) {
                        node = new Node(item, null, null, null);
                        System.out.print("\nDeleting item " + item);
                        if (deleteNode(node, root)) {
                            System.out.print(": deleted!");
                        } else {
                            System.out.print(": does not exist!");
                        }
                        item = scan.nextInt();
                    }
                    System.out.println();
                    printTree(root);
                    break;
                case 3:
                    item = scan.nextInt();
                    while (item != -999) {
                        node = new Node(item, null, null, null);
                        System.out.println((findNode(node, root) != null) ? "found" : "not found");
                        item = scan.nextInt();
                    }
                    break;
                case 4:
                    printTree(root);
                    break;
                case 5:
                    deleteTree();
                    System.out.println("Tree deleted!");
                    break;
            }
        }
    }
    
    /*AVL Specific Code*/
    private void updateHeights(Node node) {
        if (node == null) {
            return;
        }
        int left = -1, right = -1;
        if (node.left != null) {
            left = node.left.height;
        }
        if (node.right != null) {
            right = node.right.height;
        }
        node.height = Integer.max(left, right) + 1;
        updateHeights(node.father);
    }

    private int checkBalance(Node node){
        int subleft = -1, subright = -1;
        if(node.right!=null)subright = node.right.height;
        if(node.left!=null)subleft = node.left.height;
        int balance = subleft-subright;
        return balance;
    }
    
    private void balance(Node node) {
        int balance = checkBalance(node);
        if (balance < -1) {   
            if(checkBalance(node.right)==1) rotateRight(node.right);
            rotateLeft(node);
        } else if (balance > 1) { 
            if(checkBalance(node.left)==-1) rotateLeft(node.left);
            rotateRight(node);
        } 
        if(node.father!=null) balance(node.father); 
    } 

    void rotateLeft(Node node) {
        //Right heavy - Rotate left 
        System.out.println("Need to rotate node " + node + " left!");
        
        //In case it's a Left-Right rotation
        Node keepAlive = null;
        if(node.left!=null) {keepAlive = node.left; System.out.println("Need to keep alive "+keepAlive.key) ; }
        
        Node newNode = new Node(node.key, null, node.right.left, node);
        node.left = newNode;
        node.key = node.right.key;
        //Handling two special cases
        if (node.right.left != null) node.right.left.father = newNode;
        if (node.right.right != null) node.right.right.father = node; 
        
        node.right = node.right.right;
        if(keepAlive!=null){ node.left.left = keepAlive; keepAlive.father = node.left;}
        updateHeights(newNode);
    }

    void rotateRight(Node node) {
        //Left heavy - Rotate right
        System.out.println("Need to rotate node " + node + " right!");
        
        //In case it's a Right-Left rotation
        Node keepAlive = null;
        if(node.right!= null){ keepAlive = node.right; System.out.println("Need to keep alive "+keepAlive.key);}
        
        Node newNode = new Node(node.key, node.left.right, null, node);
        node.right = newNode;
        node.key = node.left.key;
        //Handle two special cases
        if (node.left.right != null) node.left.right.father = newNode;
        if (node.left.left != null) node.left.left.father = node;
        
        node.left = node.left.left;
        if(keepAlive!=null){ node.right.right = keepAlive; keepAlive.father = node.right;}
        updateHeights(newNode);
    } 
    
    public static void main(String[] args) {
        AVL avl = new AVL();
        avl.consoleUI(); 
    }
}

You can test building and modifying some random AVLs. Here's a link: AVL Example
I've tested it on the AVLs given in the link above. Output shown is on the trees shown in the link.

Output [Note: -999 is the end marker]:

1.- Add items
2.- Delete items
3.- Check items
4.- Print tree
5.- Delete tree

1
15 20 24 10 13 7 30 36 25 -999
Need to rotate node key = 15 height = 2 left!
Need to rotate node key = 10 height = 1 left!
Need to rotate node key = 15 height = 2 right!
Need to rotate node key = 20 height = 3 right!
Need to keep alive 24
Need to rotate node key = 24 height = 2 left!
Need to rotate node key = 30 height = 2 right!
Need to keep alive 36
Need to rotate node key = 20 height = 3 left!
Need to keep alive 15
key = 7 height = 0
key = 10 height = 1
key = 13 height = 3
key = 15 height = 0
key = 20 height = 1
key = 24 height = 2
key = 25 height = 0
key = 30 height = 1
key = 36 height = 0

1.- Add items
2.- Delete items
3.- Check items
4.- Print tree
5.- Delete tree

2
24 -999

Deleting item 24: deleted!
key = 7 height = 0
key = 10 height = 1
key = 13 height = 3
key = 15 height = 0
key = 20 height = 1
key = 25 height = 2
key = 30 height = 1
key = 36 height = 0

1.- Add items
2.- Delete items
3.- Check items
4.- Print tree
5.- Delete tree

2
20 -999

Deleting item 20: deleted!
key = 7 height = 0
key = 10 height = 1
key = 13 height = 3
key = 15 height = 0
key = 25 height = 2
key = 30 height = 1
key = 36 height = 0

1.- Add items
2.- Delete items
3.- Check items
4.- Print tree
5.- Delete tree

Saturday, September 27, 2014

Binary Search Tree Operations [Find, Insert, Delete, Print][Using Father Node Field][BST][Java Implementation]

Previous post on BST did not use Father field. This program uses Father field in Node.

Source:

import java.util.Scanner;

public class BSTFather {

    Node root;

    class Node {

        Node father, left, right;
        int key;

        public Node(int key, Node left, Node right, Node father) {
            this.key = key;
            this.left = left;
            this.right = right;
            this.father = father;
        }

        public String toString() {
            return Integer.toString(key);
        }
    }

    public void insert(Node toInsert, Node node) {
        if (root == null) {
            root = toInsert;
            return;
        }

        if (toInsert.key < node.key) {
            if (node.left != null) {
                insert(toInsert, node.left);
            } else { 
                toInsert.father = node;
                node.left = toInsert;
            }
        } else if (toInsert.key >= node.key) {
            if (node.right != null) {
                insert(toInsert, node.right);
            } else { 
                toInsert.father = node;
                node.right = toInsert;
            }
        }
    }

    public Node findNode(Node findNode, Node node) {
        if (root == null) {
            return null;
        }

        if (findNode.key < node.key) {
            if (node.left != null) {
                return findNode(findNode, node.left);
            } 
        } else if (findNode.key > node.key) {
            if (node.right != null) {
                return findNode(findNode, node.right);
            } 
        } else if (findNode.key == node.key) {
            return node;
        }
        return null;
    }

    public boolean deleteNode(Node deleteNode, Node node) {
        if (root == null) return false;
        else if (root.key == deleteNode.key) {
            if(root.left == null && root.right == null) root = null;
            else if (root.left == null) { root = root.right; root.father = null; }
            else if (root.right == null) { root = root.left; root.father = null; }
            else {
                Node min = root.right;
                //min element has no left or right child.
                if(min.left==null && min.right==null){
                    root.key = min.key;
                    root.right = null; 
                    return true;
                } 
                while(min.left!=null){
                    //Min element has left child.
                    min = min.left;
                }
                root.key = min.key; 
                if(min.right!=null) min.right.father = min.father;
                //Min element has no left child but has right child.
                if(min.father!=root) min.father.left = min.right;
                else{ min.father.right = min.right;} 
            }
            return true;
        }
        else { 
            Node locatedNode = findNode(deleteNode, root); 
            if(locatedNode!=null) deleteHelper(locatedNode);
            else return false;
        }
        return true;
    }

    private void deleteHelper(Node locatedNode) {
        boolean left = (locatedNode.father.left == locatedNode); 
        if(locatedNode.right == null && locatedNode.left == null){
            if(left) locatedNode.father.left = null;
            else locatedNode.father.right = null;
        }
        else if(locatedNode.left!=null && locatedNode.right == null){ 
            locatedNode.left.father = locatedNode.father;
            if(left) locatedNode.father.left = locatedNode.left;
            else locatedNode.father.right = locatedNode.left;
        }else if(locatedNode.left==null && locatedNode.right!=null){
            locatedNode.right.father = locatedNode.father;
            if(left) locatedNode.father.left = locatedNode.right;
            else locatedNode.father.right = locatedNode.right;
        }else if(locatedNode.left!=null && locatedNode.right!=null){ 
            Node min = locatedNode.right;
            //min element has no left or right child.
            if(min.left==null && min.right==null){
                locatedNode.key = min.key;
                locatedNode.right = null;
                return;
            } 
            while(min.left!=null){
                //Min element has left child.
                min = min.left;
            }
            locatedNode.key = min.key; 
            if(min.right!=null) min.right.father = min.father;
            //Min element has no left child but has right child.
            if(min.father!=locatedNode) min.father.left = min.right;
            else{ min.father.right = min.right;} 
            
        }
    }

    public void deleteTree(){
        root = null;
    }
    
    public void printTree(Node node) {
        if (node == null) {
            return;
        }
        printTree(node.left);
        System.out.print(node.key+" ");
        printTree(node.right);
    }

    public void consoleUI(){
        Scanner scan = new Scanner(System.in);  
        while (true) {
            System.out.println("\n1.- Add items\n"
                    + "2.- Delete items\n"
                    + "3.- Check items\n"
                    + "4.- Print tree\n"
                    + "5.- Delete tree\n");
            int choice = scan.nextInt();

            int item;
            Node node;
            switch (choice) {
                case 1:
                    item = scan.nextInt(); 
                    while (item != -999) {
                        node = new Node(item, null, null, null);
                        insert(node, root);
                        item = scan.nextInt(); 
                    }
                    printTree(root);
                    break;
                case 2:
                    item = scan.nextInt();
                    while (item != -999) {
                        node = new Node(item, null, null, null);
                        System.out.print("\nDeleting item "+item); 
                        if(deleteNode(node, root)){
                            System.out.print(": deleted!"); 
                        }else
                            System.out.print(": does not exist!"); 
                        item = scan.nextInt();
                    }
                    System.out.println();
                    printTree(root);
                    break;
                case 3:
                    item = scan.nextInt();
                    while (item != -999) {
                        node = new Node(item, null, null, null);
                        System.out.println((findNode(node, root)!=null)?"found":"not found");
                        item = scan.nextInt();
                    }
                    break;
                case 4:
                    printTree(root);
                    break;
                case 5:
                    deleteTree();
                    System.out.println("Tree deleted!");
                    break;
            }
        }
    }
    
    public static void main(String[] args) {
        BSTFather bst = new BSTFather();   
        bst.consoleUI();
        
    }
}

Output:

1.- Add items
2.- Delete items
3.- Check items
4.- Print tree
5.- Delete tree

1
1 2 77 5 4 99 7 4 6 -999
1 2 4 4 5 6 7 77 99 
1.- Add items
2.- Delete items
3.- Check items
4.- Print tree
5.- Delete tree

2
4 5 7 4 6 77 99 1 2 -999

Deleting item 4: deleted!
Deleting item 5: deleted!
Deleting item 7: deleted!
Deleting item 4: deleted!
Deleting item 6: deleted!
Deleting item 77: deleted!
Deleting item 99: deleted!
Deleting item 1: deleted!
Deleting item 2: deleted!

As expected!

Thursday, September 25, 2014

Computation of LEADING and TRAILING sets [Compiler Design][C++]

Computations of LEADING sets:

Algorithm:

1. Check the first non-terminal's productions one by one for terminals. If a terminal is found, print it. Then look at the next production.

2. If not found, recursively call the procedure for the single non-terminal present before the | or '\0' and include it's results (leading set's contents) in the result of this non-terminal.

Source:

#include <iostream>

using namespace std;

bool checkTerminal(char c)
{  
 if (!isupper(c) && c != '\0' && c != '|') return true;
 else return false;
}

int findProduction(char NT, char **strings, int currentProduction, int nProductions){
  for (int i = 0; i < nProductions; ++i){ 
  if (i == currentProduction)continue;
  if (strings[i][0] == NT)return i;
 } 
}

void checkNTString(char *string, char** strings, int currentProduction, int nProductions)
{
 int i = 2; 
 for (; i < 50; ++i){ 
   if (checkTerminal(string[i])){ 
   cout << string[i] << " ";
   while (string[i] != '|' && string[i] != '\0') i++;   
  }
  else if (string[i] == '|' || string[i] == '\0'){ 
   int productionNo = findProduction(string[i - 1], strings, currentProduction, nProductions); 
   checkNTString(strings[productionNo], strings, productionNo, nProductions);
  }
  if (string[i] == '\0')break;
 }
}

int main()
{
 cout << "Enter the number of non-terminals: ";
 int nProductions = 0;
 cin >> nProductions;

 cout << "Enter the productions: \n";

 char **strings = new char*[nProductions];
 for (int i = 0; i < nProductions; ++i){
  strings[i] = new char[50]; 
  cin >> strings[i];
 } 
  
 for (int i = 0; i < nProductions; ++i){
  cout << "{ ";
  checkNTString(strings[i], strings, i, nProductions);
  cout << "}\n";
 } 

 return 0;
}
/*
Input:
E=E+T|T
T=T*E|F
F=(E)|q

Input:
E=T|E+T
T=F|T*E
F=q|(E) 

Input:
S=(L)|a
L=L,S|S
*/ 

Computation of TRAILING sets:

Algorithm:

1. Consider the first non-terminal's productions.

2. Scanning from right, if a non-terminal is found in a production, print it, skip the rest of this production's content and look for either '|' or '='. If '|' is found, this means that we are ready to consider the next production for this non-terminal. If '=' is found, it means that no production for this non-terminal is left to consider. We can look at the next non-terminal now.

3. If after scanning from right to left, we encounter '|' or '=' and non-terminal has not yet been found in between, we apply this recursive procedure to include the result of the singe non-terminal that must be present after the '|' separator and include it's result in the result for this non-terminal.

Source:

#include <iostream>

using namespace std;

bool checkTerminal(char c)
{
 if (!isupper(c) && c != '|' && c != '=') return true;
 else return false;
}

int findProduction(char NT, char **strings, int currentProduction, int nProductions){
 for (int i = 0; i < nProductions; ++i){
  if (i == currentProduction)continue;
  if (strings[i][0] == NT) return i;
 }
}

void checkNTString(char *string, char** strings, int currentProduction, int nProductions)
{
 int i = 49;
 while (string[i] != '\0')i--;
 i = i - 1;
 for (; i >= 1;--i){
  if (checkTerminal(string[i])){ 
   cout << string[i] << " ";
   while (string[i] != '|' && string[i] != '=') i--;
  }
  else if (string[i] == '|' || string[i] == '='){
   int productionNo = findProduction(string[i + 1], strings, currentProduction, nProductions);
   checkNTString(strings[productionNo], strings, productionNo, nProductions);
  }
  if (string[i] == '=')break;
 }
}

int main()
{
 cout << "Enter the number of non-terminals: ";
 int nProductions = 0;
 cin >> nProductions;

 cout << "Enter the productions: \n";

 char **strings = new char*[nProductions];
 for (int i = 0; i < nProductions; ++i){
  strings[i] = new char[50];
  cin >> strings[i];
 }

 for (int i = 0; i < nProductions; ++i){
  cout << "{ ";
  checkNTString(strings[i], strings, i, nProductions);
  cout << "}\n";
 }

 return 0;
}
/*
Input:
E=E+T|T
T=T*E|F
F=(E)|q

Input:
E=T|E+T
T=F|T*E
F=q|(E) 

Input:
S=(L)|a
L=L,S|S 
*/

Wednesday, September 24, 2014

Finding FIRST Sets (of terminals) of Productions [Compiler Design][C++]

This program finds the FIRST sets of terminals of the productions supplied to it.

Algorithm:

1. Input the productions from the user.
2. For each production, check the first char after = sign, if it is a terminal, print it if it is not in the already printed record set and record it in memory otherwise just skip it if it is listed as already printed.
3. If it is a non-terminal, find the production starting with the non-terminal and do recursion.
4. Skip all other input until comma ',' or '\0' is found.
5. The first character after ',' is checked again for being a terminal or non-terminal.
6. After the FIRST terminal set for current production has been evaluated, reset the record for already printed non-terminals.

Source:

#include <iostream>

using namespace std;

//This array stores the terminals already printed
char printed[50];
int index=0;

//This resets the printed terminals record for the next production
void resetPrinted()
{
    index=0;
    for(int i=0;i<50;++i) printed[i] = '0';
}

//Checks whether the nonterminal char found has already been printed for this production
bool alreadyPrinted(char c)
{
    for(int i=0;i<50;++i)
        if(printed[i]==c) return true;
    return false;
}

bool checkChar(char c)
{
    if(!isupper(c))
    {
        if(!alreadyPrinted(c))
        {
        cout<<c<<" ";
        printed[index++] = c;
        }
        return true;
    }else
        return false;
}

void printFirst(char **input, int production, int nProductions)
{
    char c;
    int index=0;
    while(c=input[production][index]!='=')index++;
    index++; //We have found '=', we need to skip it now.

    while((c=input[production][index])!='\0')
    {
        //Is terminal
        if(checkChar(c)){}
        //Is not terminal
        else
        {
            for(int i=0;i<nProductions;++i)
            {
                if(i==production) continue;
                if(c==input[i][0]) {printFirst(input, i, nProductions); break;}
            }
        }
        //Skip until next terminal or non-terminal is found
        while((c=input[production][++index])!=','){ if(c=='\0') return;};
        c=input[production][++index]; //We have found a comma, we need to look at the next character now
    }
}

int main()
{
    int nProductions = 0;
    char **input;

    cout<<"Enter the number of productions: ";
    cin>>nProductions;
    cin.ignore();

    input = new char*[nProductions];
    for(int i=0;i<nProductions;++i)
    {
        input[i] = new char[50];
    }

    cout<<"Enter the productions: \n";

    for(int i=0;i<nProductions;++i)
        cin>>input[i];

    for(int i=0;i<nProductions;++i)
    {
        resetPrinted();
        cout<<"{ ";
        printFirst(input, i, nProductions);
        cout<<"}\n";
    }
}

Output:

Enter the number of productions: 4
Enter the productions:
A=aB,Bc,Dd
B=Cb,b
C=Db,cD,d
D=c
{ a c d b }
{ c d b }
{ c d }
{ c }

Tuesday, September 23, 2014

Flex Tutorial - Using Flex [Lexical Analyzer Generator][Flex]

Flex (Fast lexical analyzer) is a lexical analyzer generator. It is a free software alternative to lex. It is a computer program that generates lexical analyzers ("scanners" or "lexers"). It is frequently used with the free Bison parser generator. Unlike Bison, flex is not part of the GNU project.

Download flex (windows) : http://gnuwin32.sourceforge.net/packages/flex.htm
Download tdm-gcc (windows) : http://tdm-gcc.tdragon.net/download

You need to set the path environment variable after you install these softwares properly.

Steps to write a lexical analyzer using flex:

1. Specify what your lexical analyzer should take care of using the format recognized by flex. Save this as a .l file. (lets say myLex.l)
2. Run "flex myLex.l" using cmd. This generates a .c source code file. ("lex.yy.c");
3. Compile the .c source code file using "gcc lex.yy.c". This generates "a.exe" as output file.
4. Run a.exe throgh cmd.

A flex program consists of three parts.

Part one may include C source code (definitions).
Second part specifies the working (rules) of the lexical analyzer you are making.
Third part may include other C code (subroutines).
The C code is incuded as-it-is in the generated .c file.

Parts are separated by %% sign.

... definitions ...
%%
... rules ...
%%
... subroutines ...

yytext is a global variable that is a pointer to the pattern matched in the input (null terminated string).
yyleng is another global variable that denotes the length of the matched pattern.
yylex() starts the lexical analyzer.

Some flex programs:
1. A lexical analyzer that accepts digits.

Source:

%option noyywrap
%%
[0-9] printf("Digit : %s\n", yytext); 
. ;
%%
int main(){
 yylex();
}

2. A lexical analyzer that counts the number of characters, words and newlines.

Source:

%option noyywrap
%{
int chars, words, newLines;
%}

%%
[a-zA-Z]+ {chars+=yyleng;words++;}
[ \t]    {chars++;}
[\n]    {newLines++;}

%% 
int main(){
 yylex();
 printf("words = %d characters = %d newlines = %d", words, chars, newLines);
}

3. A lexical analyzer that counts identifiers and digits.

%option noyywrap
%{
 int i = 0, d = 0;
%}

%% 
[a-zA-Z]+([a-zA-Z]|[0-9])*  i++; 
[0-9]+     d+=yyleng;
%%

int main(){
 yylex();
 printf("identifiers = %d digits = %d\n", i, d);
}

4. A lexical analyzer that converts vowels to uppercase.

vowel [aeiou]
%%
{vowel} {printf("%c", toupper(*yytext));}
%%
int main(){
 yylex();
 return 0;
}
int yywrap(){
 return 1;
}

5. A lexical analyzer that accepts identifiers, letters, constants, keywords and operators.

%%
"="   printf("\n%s\tOperator is ASSIGNMENT", yytext);
"++"  printf("\n%s\tOperator is INCREMENT", yytext);
"--"  printf("\n%s\tOperator is DECREMENT", yytext);
"+="  printf("\n%s\tOperator is INCREMENT and ASSIGN",      yytext);
"-="  printf("\n%s\tOperator is DECREMENT and ASSIGN",      yytext);
"+"  {printf("\n%s\tOperator is PLUS",yytext);}
"*"  {printf("\n%s\tOperator is MULTIPLICATION",yytext);}
"-"  {printf("\n%s\tOperator is MINUS",yytext);}
"=="  {printf("\n%s\tOperator is  EQUAL TO",yytext);}
"/"  {printf("\n%s\tOperator is DIVISION",yytext);}
"<"  {printf("\n%s\tOperator is LESS THEN",yytext);}

">"  {printf("\n%s\tOperator is GREATER THEN",yytext);}

">="  {printf("\n%s\tOperator is GREATER THEN EQUAL TO",yytext);}

"<="  {printf("\n%s\tOperator is LESS THEN EQUAL TO",yytext);}

"!="  {printf("\n%s\tOperator is NOT EQUAL TO",yytext);}

","  {printf("\n%s\tComma",yytext);}
";"  {printf("\n%s\tSemi Colon",yytext);} 
[(|{|)|}]     {printf("\n%s\tBraces",yytext);} 
"if"  {printf("\n%s\tKEYWORD",yytext);}
"while" {printf("\n%s\tKEYWORD",yytext);}
"for"  {printf("\n%s\tKEYWORD",yytext);}
"float" {printf("\n%s\tKEYWORD",yytext);}
"char"  {printf("\n%s\tKEYWORD",yytext);}
"int"   {printf("\n%s\tKEYWORD",yytext);}
[-+]*[0-9]* {printf("\n%s\tConstant",yytext);}
[a-zA-Z]+([0-9]|[a-zA-Z])* {printf("\n%s\tIdentifier",yytext);}
[ \t\n]+ //ignore whitespace and newlines
%%
int main()
{
yylex();
}

int yywrap()
{
return 1;
}

More here: http://epaperpress.com/lexandyacc/download/LexAndYaccTutorial.pdf

Saturday, September 20, 2014

Binary Search Trees - Insert, Find, Delete, Print Tree Operations [Java]

This program implements Insert, Find, Delete Node and Print operations on a Binary Search Tree. The inorder traversal of a Binary Search Tree yields the elements in ascending order.

This program doesn't use Father field in Node class. Here is another program that has Father field in nodes : Using Father Field BST

Code:

import java.util.Scanner;

public class BinarySearchTree {

    private class Node {

        int key;
        Node left, right;

        Node(int key) {
            this.key = key;
        }
    }

    private Node root;

    /* Adds an item to the BST */
    public void add(int a) {
        if (root == null) { root = new Node(a); } 
        else              { adder(a, root, null, false); }
    }

    private void adder(int a, Node node, Node parent, boolean isLeft) {

        if (node == null) {
            if (isLeft) { parent.left = new Node(a); } 
            else        { parent.right = new Node(a); }
            return;
        }

        if (a >= node.key) { adder(a, node.right, node, false); } 
        else               { adder(a, node.left, node, true); }
    }

    /* Checks whether an item is in the tree */
    public boolean isNode(int a) {
        if(root == null) return false;
        return nodeFinder(a, root);
    }

    private boolean nodeFinder(int a, Node node) {
        if (node.key == a) { return true; }

        if (a >= node.key) { return nodeFinder(a, node.right); } 
        else               { return nodeFinder(a, node.left); }
    }

    /* Deletes a node from the tree */
    public boolean delete(int a) {
        if (root == null) { return false; }
        
        //Target element is the root and either left or right subtree is empty
        if(root.key == a){
            if (root.left == null && root.right == null) 
                { root = null; return true;}
            else if(root.right == null)    //Root with only left subtree 
                { root = root.left; return true;}
            else if(root.left == null)                    //Root with right subtree only
                { root = root.right; return true;} 
        }
        return deleter(a, root, null); 
    }

    private boolean deleter(int a, Node node, Node parent) {  
        
        //Node is not present. Return false. 
        if(node == null){ return false; }
        
        //Node to be deleted is either a leaf or has only one child 
if (node.left != null && node.left.key == a) { if (node.left.left == null) { node.left = node.left.right; return true; } else if (node.left.right == null) { node.left = node.left.left; return true; } } else if (node.right != null && node.right.key == a) { if (node.right.left == null) { node.right = node.right.right; return true; } else if (node.right.right == null) { node.right = node.right.left; return true; } } //Node to be deleted has two children if (node.key == a) { Node smallestNodesParent = smallestNodesParent(node.right); if (smallestNodesParent.left != null) { node.key = smallestNodesParent.left.key; smallestNodesParent.left = smallestNodesParent.left.right; } else { node.key = smallestNodesParent.key; node.right = smallestNodesParent.right; } return true; } //Go left or right? if (a > node.key) { return deleter(a, node.right, node); } else if(a < node.key) { return deleter(a, node.left, node); } //Never gets Returned - One of the three conditions - equal, less or greater //return before reaching here. return false; } /*        returns the smallest nodes parent node, or if the node first passed to        this function has no left child, it just returns the node passed to it     */ private Node smallestNodesParent(Node node) { if (node.left != null) { if (node.left.left == null) { return node; } } else { return node; } return smallestNodesParent(node.left); } /*        Prints the tree contents - Inorder traversal -        Inorder traversal of a BST yields the items in        ascending order     */ public void printTree() { print(root); } private void print(Node node) { if (node == null) { if (root == null) { System.out.println("Tree is empty!"); } return; } print(node.left); System.out.print(node.key + " "); print(node.right); } public static void main(String[] args) { BinarySearchTree bst = new BinarySearchTree(); Scanner scan = new Scanner(System.in); //Display a Console Interface while (true) { System.out.println("\n1.- Add items\n" + "2.- Delete items\n" + "3.- Check items\n" + "4.- Print tree\n"); int choice = scan.nextInt(); int item; switch (choice) { case 1: item = scan.nextInt(); while (item != -999) { bst.add(item); item = scan.nextInt(); } bst.printTree(); break; case 2: item = scan.nextInt(); while (item != -999) { System.out.print("\nDeleting item "+item); if(bst.delete(item)){ System.out.print(": deleted!"); }else System.out.print(": does not exist!"); item = scan.nextInt(); } System.out.println(); bst.printTree(); break; case 3: item = scan.nextInt(); while (item != -999) { System.out.println(bst.isNode(item)); item = scan.nextInt(); } break; case 4: bst.printTree(); break; } } } }

Output: 

1.- Add items
2.- Delete items
3.- Check items
4.- Print tree

1
9 3 14 2 8 12 14 13 112 19 -999
2 3 8 9 12 13 14 14 19 112
1.- Add items
2.- Delete items
3.- Check items
4.- Print tree

2
3 14 14 13 112 -999

Deleting item 3: deleted!
Deleting item 14: deleted!
Deleting item 14: deleted!
Deleting item 13: deleted!
Deleting item 112: deleted!
2 8 9 12 19
1.- Add items
2.- Delete items
3.- Check items
4.- Print tree

2
8 9 12 19 2 -999

Deleting item 8: deleted!
Deleting item 9: deleted!
Deleting item 12: deleted!
Deleting item 19: deleted!
Deleting item 2: deleted!
Tree is empty!

1.- Add items
2.- Delete items
3.- Check items
4.- Print tree