Tuesday, 26 July 2016

Maximum and minimum of an array using minimum number of comparisons

Write a C function to return minimum and maximum in an array. You program should make minimum number of comparisons. 

Idea : Using tournament algorithm




 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
using namespace std;

struct minMaxPair{
    int maxi;
    int mini;
};

struct minMaxPair minMaxTournament(int *arr, int low, int high){
    //Number of elements is one
    if(low == high){
        struct minMaxPair maxmin;
        maxmin.maxi = arr[low];
        maxmin.mini = arr[low];
        return maxmin;
    } //Number of elements is two
    else if(low == high - 1){
        struct minMaxPair maxmin;
        if(arr[low] < arr[high]){
            maxmin.mini = arr[low];
            maxmin.maxi = arr[high];
        } else{
            maxmin.maxi = arr[low];
            maxmin.mini = arr[high];
        }
        return maxmin;
    } //Number of elements is more than two
    else{
        int mid = (low + high) / 2;
        struct minMaxPair left, right, result;
        left = minMaxTournament(arr, 0, mid);
        right = minMaxTournament(arr, mid + 1, high);
        if(left.mini <= right.mini){
            result.mini = left.mini;
        } else {
            result.mini = right.mini;
        }
        if(left.maxi >= right.maxi){
            result.maxi = left.maxi;
        } else {
            result.maxi = right.maxi;
        }
        return result;
    }
}

int main(){
    int arr[] = {1000, 11, 445, 1, 330, 3000};
    int n = sizeof(arr) / sizeof(arr[0]);
    struct minMaxPair result = minMaxTournament(arr, 0, n - 1);
    cout << "Maximum : " << result.maxi << endl;
    cout << "Minimum : " << result.mini << endl;
    return 0;
}
Share:

Monday, 25 July 2016

Two elements sum to x

Given an array of n numbers and another number x, determines whether or not there exist two elements in the array whose sum is exactly x.

Approach: Sort the array and use two pointers one at the start and the other at the end. Increment the start pointer if the sum is less than the target, decrement if the sum is greater else break out of the loop.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/* To find the pair of elements in an array if the sum is equal to the given number */
#include<iostream>
#include<algorithm>
using namespace std;

int main(){
    int arr[6] = {1, 4, 45, 6, 10, -8};
    int n = sizeof(arr) / sizeof(arr[0]);
    sort(arr, arr + n);
    int i = 0, j = n - 1, k = 16;
    int flag = 0;
    while(i < j){
            if(arr[i] + arr[j] == k){
                flag = 1;
                break;
            } else if(arr[i] + arr[j] > k){
                j--;
            } else{
                i++;
            }
    }
    if(flag){
        cout << arr[i] << " + " << arr[j] << " add upto " << k << endl;
    } else{
        cout << "No such pair exists" << endl;
    }
    return 0;
}
Share:

Pascal's Triangle

Given numRows, generate the first numRows of Pascal's triangle.
For example, given numRows = 5,
Return
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Return an array of arrays.
 * The sizes of the arrays are returned as *columnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
 int** generate(int numRows, int** columnSizes) {
    if(numRows == 0)
        return NULL;
    int **result = (int **)malloc(numRows * sizeof(int *));
    
    (*columnSizes) = (int *)malloc(numRows * sizeof(int));

    int i, j;
    for (i = 0; i < numRows; i++) {
        (*columnSizes)[i] = i + 1;
        result[i] = (int *)malloc((*columnSizes)[i] * sizeof(int));
        result[i][0] = 1;
        for (j = 1; j < i; j++) {
            result[i][j] = result[i - 1][j - 1] + result[i - 1][j];
        }
        result[i][i] = 1;
    }
    return result;
}
Share:

Pascal's Triangle II

Given an index k, return the kth row of the Pascal's triangle.
For example, given k = 3,
Return [1,3,3,1].
Note:
Could you optimize your algorithm to use only O(k) extra space?


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> result;
        int n = rowIndex / 2;
        result.push_back(1);
        for(int i = 1; i <= n; i++){
            long long next = (long(result[i - 1]) * long(rowIndex - i  + 1)) / i;
            result.push_back(next);
        }
        if(rowIndex % 2 == 1){
            int size = result.size();
            for(int i = size - 1; i >= 0; i--){
                result.push_back(result[i]);
            }
        }else{
            int size = result.size();
            for(int i = size - 2; i >= 0; i--){
                result.push_back(result[i]);
            }
        }
        return result;
    }
};
Share:

Saturday, 23 July 2016

Merge Overlapping Intervals

Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

 /**  
  * Definition for an interval.  
  * struct Interval {  
  *   int start;  
  *   int end;  
  *   Interval() : start(0), end(0) {}  
  *   Interval(int s, int e) : start(s), end(e) {}  
  * };  
  */  
 class Solution {  
 public:  
   static bool compare(Interval i1, Interval i2){  
     return (i1.start < i2.start);  
   }  
   vector<Interval> merge(vector<Interval>& intervals) {  
     vector<Interval> out;  
     int n = intervals.size();  
     if(n <= 0){  
       return out;  
     }  
     //sort as per the start time  
     sort(intervals.begin(), intervals.begin() + n, compare);  
     stack<Interval> it;  
     it.push(intervals[0]);  
     for(int i = 1; i < n; i++){  
       Interval topInterval = it.top();  
       //if start time of next is after the end of the prev, push the next  
       if(intervals[i].start > topInterval.end){  
         it.push(intervals[i]);  
       }else if(intervals[i].end > topInterval.end){  
         //if start time of next is before the end of the prev and the end of the next is after the end of the prev, then update the end of the prev  
         topInterval.end = intervals[i].end;  
         it.pop();  
         it.push(topInterval);  
       }  
     }  
     vector<Interval> out;  
     while(!it.empty()){  
       Interval curr = it.top();  
       out.push_back(curr);  
       it.pop();  
     }  
     return out;  
   }  
 };  

Share:

Spiral Order Matrix II

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
Example:
Given n = 3,
You should return the following matrix:
 [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]

 #include <iostream>  
 using namespace std;  
 int main()  
 {  
   int n = 4;  
   int **mat = new int*[n];  
   for(int i = 0 ; i < n; i++)  
       mat[i] = new int[n];  
   int dir = 0;  
   int k = 1;  
   int top = 0, bottom = n - 1, left = 0, right = n - 1;  
   while(top <= bottom && left <= right){  
     if(dir == 0){  
       for(int i = left; i <= right; i++){  
         mat[top][i] = k++;  
       }  
       top++;  
       dir = 1;  
     }  
     else if(dir == 1){  
       for(int i = top; i <= bottom; i++){  
         mat[i][right] = k++;  
       }  
       right--;  
       dir = 2;  
     }  
     else if(dir == 2){  
       for(int i = right; i >= left; i--){  
         mat[bottom][i] = k++;  
       }  
       bottom--;  
       dir = 3;  
     }else{  
       for(int i = bottom; i >= top; i--){  
         mat[i][left] = k++;  
       }  
       left++;  
       dir = 0;  
     }  
   }  
   for(int i = 0 ; i < n; i++){  
     for(int j = 0; j < n; j++){  
       cout << mat[i][j] << " ";  
     }  
     cout << endl;  
   }  
   return 0;  
 }  

Share:

Count And Say

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...
1 is read off as one 1 or 11.
11 is read off as two 1s or 21.
21 is read off as one 2, then one 1 or 1211.
Given an integer n, generate the nth sequence.
Note: The sequence of integers will be represented as a string.
Example:
if n = 2,
the sequence is 11.
 string appendNext(string str){  
   string out = "";  
   char curr = str[0];  
   int currCount = 1;  
   for(int i = 1; i < str.size(); i++){  
     if (str[i] == curr){  
       currCount++;  
     }  
     else {  
       char chr = currCount + '0';  
       out = out + chr;  
       out = out + curr;  
       curr = str[i];  
       currCount = 1;  
     }  
   }  
   char chr = currCount + '0';  
   out = out + chr;  
   out = out + curr;  
   return out;  
 }  
 string Solution::countAndSay(int n) {  
   if (n == 1) {  
     return "1";  
   }  
   string prev = "1";  
   string result;  
   for (int i = 1; i < n; i++){  
     result = appendNext(prev);  
     prev = result;  
   }  
   return result;  
 }  

Share:

Friday, 22 July 2016

Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

 /**  
  * Definition for a binary tree node.  
  * struct TreeNode {  
  *   int val;  
  *   TreeNode *left;  
  *   TreeNode *right;  
  *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
  * };  
  */  
 class Solution {  
 public:  
   int minDepth(TreeNode* root) {  
     if(root == NULL)  
       return 0;  
     //if it is a leaf node  
     if(root->left == NULL && root->right == NULL)  
       return 1;  
     int leftDepth, rightDepth;  
     //if left is not NULL, recursively compute the depth of left else it is a internal node and it can't give the minDepth  
     if(root ->left != NULL)  
       leftDepth = minDepth(root->left);  
     else  
       leftDepth = INT_MAX;  
     //if right is not NULL, recursively compute the depth of right tree else it is a internal node and it can't give the minDepth  
     if(root ->right != NULL)  
       rightDepth = minDepth(root->right);  
     else  
       rightDepth = INT_MAX;  
     return 1 + min(leftDepth, rightDepth);  
   }  
 };  
Share:

Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”
        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4
For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

 /**  
  * Definition for a binary tree node.  
  * struct TreeNode {  
  *   int val;  
  *   TreeNode *left;  
  *   TreeNode *right;  
  *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
  * };  
  */  
 class Solution {  
 public:  
   TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {  
     if(root == NULL){  
       return NULL;  
     }  
     if(root == p || root == q){  
       return root;  
     }  
     TreeNode *left = lowestCommonAncestor(root->left, p, q);  
     TreeNode *right = lowestCommonAncestor(root->right, p, q);  
     if(left != NULL && right != NULL){  
       return root;  
     }  
     if(left == NULL && right == NULL){  
       return NULL;  
     }else{  
       return left != NULL ? left : right;  
     }  
   }  
 };      
Share:

Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two sub trees of every node never differ by more than 1.

 /**  
  * Definition for a binary tree node.  
  * struct TreeNode {  
  *   int val;  
  *   TreeNode *left;  
  *   TreeNode *right;  
  *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
  * };  
  */  
 class Solution {  
 public:  
   int height(TreeNode *root){  
     if(root == NULL){  
       return 0;  
     }  
     int leftHeight = height(root->left);  
     if(leftHeight == -1){  
       return -1;  
     }  
     int rightHeight = height(root->right);  
     if(rightHeight == -1){  
       return -1;  
     }  
     if(abs(leftHeight - rightHeight) > 1){  
       return -1;  
     }  
     return 1 + max(leftHeight, rightHeight);  
   }  
   bool isBalanced(TreeNode* root) {  
     if(root == NULL){  
       return true;  
     }  
     if(height(root) == -1){  
       return false;  
     }  
     return true;  
   }  
 };  
Share:

Tuesday, 19 July 2016

Inplace rotate square matrix by 90 degrees(Clockwise)

/*  Inplace rotate square matrix by 90 degrees */
/*
Given an square matrix, turn it by 90 degrees in clockwise direction without using any extra space.

Example:
Input:
 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15 16
Output:
 4  8 12 16
 3  7 11 15
 2  6 10 14
 1  5  9 13
 */


 #include<iostream>  
 using namespace std;  
 int N = 4;  
 void printMatrix(int mat[4][4]){  
  for (int i = 0; i < N; i++) {  
  for (int j = 0; j < N; j++)  
   cout << mat[i][j] << " ";  
  cout << endl;  
  }  
  cout << endl;  
 }  
 void rotate(int mat[4][4], int N) {  
   for(int i = 0; i < N / 2; i++){  
     for(int j = i; j < N - 1 - i; j++){  
       //store the top in temp  
       int temp = mat[i][j];  
       //move the left to the top  
       mat[i][j] = mat[N - 1 - j][i];  
       //move bottom to left  
       mat[N - 1 - j][i] = mat[N - 1 - i][N - 1 - j];  
       //move right to bottom  
       mat[N - 1 - i][N - 1 - j] = mat[j][N - 1 - i];  
       //move top stored in temp to right  
       mat[j][N - 1 - i] = temp;  
     }  
   }  
 }  
 int main(){  
   int mat[4][4] =  
  {  
  {1, 2, 3, 4},  
  {5, 6, 7, 8},  
  {9, 10, 11, 12},  
  {13, 14, 15, 16}  
  };  
  printMatrix(mat);  
  rotateMatrix(mat, 4);  
  printMatrix(mat);  
  return 0;  
 }  
Share:

Inplace rotate square matrix by 90 degrees(Anti-Clockwise)

/*  Inplace rotate square matrix by 90 degrees */
/*
Given an square matrix, turn it by 90 degrees in anti-clockwise direction without using any extra space.

Example:
Input:
 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15 16
Output:
 4  8 12 16
 3  7 11 15
 2  6 10 14
 1  5  9 13
 */


 #include<iostream>  
 using namespace std;  
 int N = 4;  
 void printMatrix(int mat[4][4]){  
  for (int i = 0; i < N; i++) {  
  for (int j = 0; j < N; j++)  
   cout << mat[i][j] << " ";  
  cout << endl;  
  }  
  cout << endl;  
 }  
 void rotateMatrix(int mat[4][4], int N){  
   for(int i = 0; i < N / 2; i++){  
     for(int j = i; j < N - 1 - i; j++){  
       //store the top in temp  
       int temp = mat[i][j];  
       //move the right to the top  
       mat[i][j] = mat[j][N - 1 - i];  
       //move bottom to right  
       mat[j][N - 1 - i] = mat[N - 1 - i][N - 1 - j];  
       //move left to bottom  
       mat[N - 1 - i][N - 1 - j] = mat[N - 1 - j][i];  
       //move top stored in temp to left  
       mat[N - 1 - j][i] = temp;  
     }  
   }  
 }  
 int main(){  
   int mat[4][4] =  
  {  
  {1, 2, 3, 4},  
  {5, 6, 7, 8},  
  {9, 10, 11, 12},  
  {13, 14, 15, 16}  
  };  
  printMatrix(mat);  
  rotateMatrix(mat, 4);  
  printMatrix(mat);  
  return 0;  
 }  
Share:

Monday, 18 July 2016

Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
  • Integers in each row are sorted in ascending from left to right.
  • Integers in each column are sorted in ascending from top to bottom.
For example,
Consider the following matrix:
[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
Given target = 5, return true.
Given target = 20, return false.


 bool searchMatrix(int** matrix, int matrixRowSize, int matrixColSize, int target) {  
 //start with the top right element and move along rows and columns based on target value   
   int i = 0, j = matrixColSize - 1;  
   while(i < matrixRowSize && j >= 0){  
     if(matrix[i][j] == target){  
       return true;  
     }else if(target < matrix[i][j]){  
       j--;  
     }else{  
       i++;  
     }  
   }  
   return false;  
 }  
Share:

Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its level order traversal as:
[  [3],
  [9,20],
  [15,7] ]

 /**  
  * Definition for a binary tree node.  
  * struct TreeNode {  
  *   int val;  
  *   TreeNode *left;  
  *   TreeNode *right;  
  *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
  * };  
  */  
 #include <queue>  
 using namespace std;  
 class Solution {  
 public:  
   vector<vector<int>> levelOrder(TreeNode* root) {  
     vector<vector<int>> res;  
     if(root == NULL){  
       return res;  
     }  
     queue<TreeNode*> Q;  
     Q.push(root);  
     while(!Q.empty()){  
       vector<int> temp;  
       int size = Q.size();  
       for(int i = 0; i < size; i++){  
         TreeNode *node = Q.front(); Q.pop();  
         temp.push_back(node->val);  
         if(node->left){  
           Q.push(node->left);  
         }  
         if(node->right){  
           Q.push(node->right);  
         }  
       }  
       res.push_back(temp);  
     }  
     return res;  
   }  
 };  
Share:

Sunday, 17 July 2016

Spiral Order Matrix I Solution

Given a matrix of m * n elements (m rows, n columns), return all elements of the matrix in spiral order.
Example:
Given the following matrix:
[
    [ 1, 2, 3 ],
    [ 4, 5, 6 ],
    [ 7, 8, 9 ]
]
You should return
[1, 2, 3, 6, 9, 8, 7, 4, 5]

 /**  
  * @input A : Read only ( DON'T MODIFY ) 2D integer array ' * @input n11 : Integer array's ( A ) rows  
  * @input n12 : Integer array's ( A ) columns  
  *  
  * @Output Integer array. You need to malloc memory for result array, and fill result's length in length_of_array  
  */  
 int* spiralOrder(const int** A, int n11, int n12, int *length_of_array) {  
    *length_of_array = n11 * n12; // length of result array  
    int *result = (int *) malloc(*length_of_array * sizeof(int));  
    // DO STUFF HERE  
    int top = 0, bottom = n11 - 1, left = 0, right = n12 - 1;  
    int dir = 0, k = 0, i;  
    while(top <= bottom && left <= right){  
      if(dir == 0){  
        for(i = left; i <= right; i++){  
          result[k++] = A[top][i];  
        }  
        top++;  
        dir = 1;  
      } else if(dir == 1){  
        for(i = top; i <= bottom; i++){  
          result[k++] = A[i][right];  
        }  
        right--;  
        dir = 2;  
      } else if(dir == 2){  
        for(i = right; i >= left; i--){  
          result[k++] = A[bottom][i];  
        }  
        bottom--;  
        dir = 3;  
      } else if(dir == 3){  
        for(i = bottom; i >= top; i--){  
          result[k++] = A[i][left];  
        }  
        left++;  
        dir = 0;  
      }  
    }  
    return result;  
 }  
Share:

Min Steps in Infinite Grid

You are in an infinite 2D grid where you can move in any of the 8 directions :
 (x,y) to 
    (x+1, y), 
    (x - 1, y), 
    (x, y+1), 
    (x, y-1), 
    (x-1, y-1), 
    (x+1,y+1), 
    (x-1,y+1), 
    (x+1,y-1) 
You are given a sequence of points and the order in which you need to cover the points. Give the minimum number of steps in which you can achieve it. You start from the first point.

 /**  
  * @input X : Integer array corresponding to the X co-ordinate  
  * @input n1 : Integer array's ( X ) length  
  * @input Y : Integer array corresponding to the Y co-ordinate  
  * @input n2 : Integer array's ( Y ) length  
  *  
  * Points are represented by (X[i], Y[i])  
  *  
  * @Output Integer  
  *  
  */  
 int coverPoints(int* X, int n1, int* Y, int n2) {  
   int curX = X[0], curY = Y[0];  
   int total = 0, i, j, k;  
   for(i = 1; i < n1; i++){  
     j = abs(X[i] - curX);  
     k = abs(Y[i] - curY);  
     curX = X[i];  
     curY = Y[i];  
     if(j >= k){  
       total = total + j;  
     }else{  
       total = total + k;  
     }  
   }  
   return total;  
 }  
Share:

Beautiful Soup for Crawling

Beautiful Soup for web crawling


 import urllib2  
 from bs4 import BeautifulSoup  
 import requests  
 deptCodes = ["AE", "AG", "AR", "BT", "CH", "CM", "CE", "CS", "EE", "EC", "MG", "HS", "IM", "MM", "ME", "MT", "MI", "NA", "MP",  
       "ED", "CR", "MS", "N2", "PK", "RE", "RT", "RD", "GS", "IT", "RJ", "RG", "ID", "MD", "BS", "EF", "ES", "NT", "WM",  
       "SM"  
       ]  
 print len(deptCodes)  
 outfile = file("out.txt", "w")  
 f = []  
 for dept in deptCodes:  
   print dept  
   fetchUrl = "http://www.iitkgp.ac.in/commdir3/list.php?division=3&deptcode=" + dept  
   try:  
     page = urllib2.urlopen(fetchUrl)  
   except:  
     break  
   htmlDocs = page.read()  
   soup = BeautifulSoup(htmlDocs)  
   links = soup('a')  
   facPage = "fac-profiles"  
   for link in links:  
     if link.has_attr('href'):  
       if link['href'].find(facPage) >= 0:  
         l = str(link['href'])  
         f.append(l)  
         outfile.write("http://www.iitkgp.ac.in" + link['href'] + "\n")  
   #for elt in links:  
     #print elt  
 print len(f)  
 print len(list(set(f)))  
 outfile.close()  
Share:

Error Resolving In Linux

Resolve apache error

sudo chmod 755 html -R

 

Add ppa in ubuntu14.04

export http_proxy, https_proxy, ftp_proxy
sudo -E add-apt-repository ppa:<repository-name>

Path variable

export PATH=$PATH:<path_to_bin>
Share:

Lex Yacc Parser For HTML Processing

Lex Yacc Parser for html web pages
LEX File
%{
#include<stdio.h>
#include<math.h>
#include<string.h>
#include "cali.tab.h"
int yywrap(void);
#include<stdlib.h>
%}
%%
\<fieldset[^\>]*\>\<legend\>(Award|Fellow|Patent|Member.?.?Editorial.?Board|Copyrights|Text) {
strcpy(yylval.cval, yytext);
return UNWANTED;
}
\<fieldset[^\>]*\>\<legend\> {
strcpy(yylval.cval, yytext);
return BEGINFIELD;
}
\<\/fieldset\> {
strcpy(yylval.cval, yytext);
return ENDFIELD;
}
\<fieldset[^\>]*\>\<!--<legend\>.?[a-zA-Z\.]*[ \r]?[a-zA-Z\.]*[ \r]?[a-zA-Z\.]* {
strcpy(yylval.cval, "<fieldset>");
strtok(yytext, ">");
strtok(NULL, ">");
char *name = strtok(NULL, ">");
FILE *fp = fopen("out.txt", "a");
fprintf(fp, "Name$%s\n", name);
fclose(fp);
printf("Name$%s\n", name);
return NAME;
}
Contact[ \r]?Addresses {
strcpy(yylval.cval, yytext);
return CONTACT;
}
\+[0-9\- \r]{18} {
strcpy(yylval.cval, yytext);
return PHONE;
}
Research[ \r]?Areas {
strcpy(yylval.cval, yytext);
return RESAREA;
}
Member[ \r]?of[ \r]?Professional[ \r]?Bodies {
FILE *fp = fopen("out.txt", "a");
fprintf(fp, "%s", "\nMember of Professional Bodies$");
fclose(fp);
strcpy(yylval.cval, yytext);
return RESAREA;
}
Current[ \r]?Sponsored[ \r]?Projects {
FILE *fp = fopen("out.txt", "a");
fprintf(fp, "%s", "\nCurrent Sponsored Projects");
fclose(fp);
strcpy(yylval.cval, yytext);
return SPONSORED;
}
Project[ \r]?Title {
FILE *fp = fopen("out.txt", "a");
fprintf(fp, "%s", "$");
fclose(fp);
}
On-going[ \r]?Consultancy[ \r]?Projects {
FILE *fp = fopen("out.txt", "a");
fprintf(fp, "%s", "\nOn-going Consultancy Projects");
fclose(fp);
strcpy(yylval.cval, yytext);
return SPONSORED;
}
Project[ \r]?Name {
FILE *fp = fopen("out.txt", "a");
fprintf(fp, "%s", "$");
fclose(fp);
}
[A-Z0-9\-\/ \r]{2,10} {
strcpy(yylval.cval, yytext);
return QTRNO;
}
Publications:([ \r]?[0-9]{4}[ \r]?\-[ \r]?[0-9]{4}) {
strcpy(yylval.cval, yytext);
return PUBLICATIONS;
}
Some[ \r]?Earlier[ \r]?Publications {
strcpy(yylval.cval, yytext);
return PUBLICATIONS;
}
\([0-9]{4}\)  {
strcpy(yylval.cval, yytext);
      return YR;
}
\<[^\>]*\> {
strcpy(yylval.cval, yytext);
return TAG;
}
[a-zA-Z0-9:\.\& \r\n\t\-\/]+ {
strcpy(yylval.cval, yytext);
return VALUE;
}
. ;
%%
int yywrap(){
printf("End of parsing \n");
}
void yyerror(const char *str){
printf(" Invalid Character... \n");
}
int main(int argc, char** argv) {
FILE *fp = fopen("out.txt", "w");
fclose(fp);
        if(argc !=2){
             printf("Provide input fiile\n");
             return 0;
        }
printf("Start of parsing \n");
yyin = fopen(argv[1], "r");
while (!feof(yyin)){
yyparse();
}
usleep(10);
process();
  return 0;
}
YACC File
%{
#include<stdio.h>
#include<string.h>
int yylex(void);
void yyerror(const char *s);
%}
%union
{
char cval[1500];
}
%token <cval> BEGINFIELD
%token <cval> ENDFIELD
%token <cval> NAME
%token <cval> TAG
%token <cval> VALUE
%token <cval> CONTACT
%token <cval> QTRNO
%token <cval> UNWANTED
%token <cval> PHONE
%token <cval> RESAREA
%token <cval> MEMBER
%token <cval> SPONSORED
%token <cval> PUBLICATIONS
%token <cval> YR
%type <cval> S N C R U SP P
%%
state : S
;
S : S VALUE
| VALUE 
| S TAG 
| TAG  
| S QTRNO 
| QTRNO 
| S NAME N ENDFIELD
| S BEGINFIELD CONTACT C ENDFIELD  {
FILE *fp = fopen("out.txt", "a");
fprintf(fp, "%s", "\nResearch Areas$");
fclose(fp);
}
| S BEGINFIELD RESAREA R ENDFIELD
| S UNWANTED U ENDFIELD
| S BEGINFIELD SPONSORED SP ENDFIELD
| S BEGINFIELD PUBLICATIONS P ENDFIELD
| S CONTACT
| CONTACT
| S PHONE
| PHONE
| UNWANTED
| PUBLICATIONS
| S PUBLICATIONS
| S YR
| YR
| S RESAREA
| RESAREA
| S MEMBER
| MEMBER
| SPONSORED
| S SPONSORED
;
N : VALUE 
  | N VALUE {
  char post[100];
sprintf(post, "%s", $2);
if(strcasestr(post, "Professor") || strcasestr(post, "Director") || strcasestr(post, "Dean") || strcasestr(post, "Faculty") || strcasestr(post, "Lecturer") || strstr(post, "Network Engineer") || strcasestr(post, "Superintendent") || strcasestr(post, "Registrar") || strcasestr(post, "Librarian") ){
printf("Designation$%s\n", post+2);
  FILE *fp = fopen("out.txt", "a");
fprintf(fp, "Designation$%s\n", post+2);
  fclose(fp);
}
}
| N TAG {
FILE *fp = fopen("out.txt", "a");
fprintf(fp, "%s", " ");
fclose(fp);
}
| TAG {
FILE *fp = fopen("out.txt", "a");
fprintf(fp, "%s", " ");
fclose(fp);
}
| N QTRNO
| QTRNO
| N CONTACT
| CONTACT
| N PHONE
| PHONE
| N YR
| YR
;
C : VALUE
| C VALUE 
| C TAG {
FILE *fp = fopen("out.txt", "a");
fprintf(fp, "%s", " ");
fclose(fp);
}
| TAG {
FILE *fp = fopen("out.txt", "a");
fprintf(fp, "%s", " ");
fclose(fp);
}
| C QTRNO {
FILE *fp = fopen("out.txt", "a");
fprintf(fp, "QTRNO$%s\n", $2);
fclose(fp);
}
| QTRNO {
FILE *fp = fopen("out.txt", "a");
fprintf(fp, "QTRNO$%s\n", $1);
fclose(fp);
}
| PHONE {
FILE *fp = fopen("out.txt", "a");
fprintf(fp, "PHONE$%s\n", $1);
fclose(fp);
}
| C PHONE {
FILE *fp = fopen("out.txt", "a");
fprintf(fp, "PHONE$%s\n", $2);
fclose(fp);
}
| C YR
| YR
;
R : VALUE {
FILE *fp = fopen("out.txt", "a");
fprintf(fp,"%s$", $1);
  fclose(fp);
}
  | R VALUE {
FILE *fp = fopen("out.txt", "a");
fprintf(fp,"%s$", $2);
fclose(fp);
}
| QTRNO
| R QTRNO
| R TAG {
FILE *fp = fopen("out.txt", "a");
fprintf(fp, "%s", " ");
fclose(fp);
}
| TAG {
FILE *fp = fopen("out.txt", "a");
fprintf(fp, "%s", " ");
fclose(fp);
}
| R YR
| YR
;
U : VALUE
| U VALUE
| U TAG
| TAG
| U QTRNO
| QTRNO
| U YR
| YR
| U PHONE
| PHONE
;
SP : VALUE {
FILE *fp = fopen("out.txt", "a");
fprintf(fp,"%s", $1);
fclose(fp);
}
| SP VALUE {
FILE *fp = fopen("out.txt", "a");
fprintf(fp,"%s", $2);
fclose(fp);
}
| SP TAG {
FILE *fp = fopen("out.txt", "a");
fprintf(fp, "%s", " ");
fclose(fp);
}
| TAG {
FILE *fp = fopen("out.txt", "a");
fprintf(fp, "%s", " ");
fclose(fp);
}
| SP YR
| YR
| SP QTRNO
| QTRNO
;
P : VALUE {
FILE *fp = fopen("out.txt", "a");
fprintf(fp,"%s", $1);
fclose(fp);
}
| P VALUE {
FILE *fp = fopen("out.txt", "a");
fprintf(fp,"%s", $2);
fclose(fp);
}
| P TAG {
FILE *fp = fopen("out.txt", "a");
fprintf(fp, "%s", " ");
fclose(fp);
}
| TAG {
FILE *fp = fopen("out.txt", "a");
fprintf(fp, "%s", " ");
fclose(fp);
}
| P YR {
FILE *fp = fopen("out.txt", "a");
fprintf(fp, "%s%s%s", "$", $2, "$$");
fclose(fp);
}
| YR {
FILE *fp = fopen("out.txt", "a");
fprintf(fp, "%s%s%s", "$", $1, "$$");
fclose(fp);
}
| P QTRNO
| QTRNO
;
%%
Make file
all : yaccCompile lexCompile compile1
yaccCompile:
bison -d cali.y
lexCompile:
lex cali.l
compile1:
gcc cali.tab.c lex.yy.c -o parser.out
Share:

Contact Me

Name

Email *

Message *

Popular Posts

Blog Archive