Simple Polynomial data structure and Calculator for single variable

Explanation:

The first code takes an integer for the value of the variable and the next one takes a double for the value of variable and produces value of the function.

I have commented the second code to make it easy. Pun intended on lines 144 to 147.

Calculates an equation with given value of the variable. If the equation is,

f(x) = -50x^{-3} +3x -40x^2 +10x^{-5} -7x^{10}

then for,

x = -3, \ f(x) = -413710.189300 \\  x = -2, \ f(x) = -7328.062500 \\  x = -1, \ f(x) = -10.000000 \\  x = 0, \ \ \ f(x) = \ \ \ Undefined \\  x = 1, \ \ \ f(x) = -84.000000 \\  x = 2, \ \ \ f(x) = -7327.937500 \\  x = 3, \ \ \ f(x) = -413695.810700 \\

(Pease Test this code before using, I haven’t done much testing). Check against this site. To use this from console comment freopen lines. Otherwise make two txt files named input and output in the same directory as the cpp file and follow the given equation input format.

Input:
-50x^-3 +3x^+1 -40x^+2 +10x^-5 -7x^+10
0
y
-3
y
-2
y
-1
y
0
y
1
y
2
y
3
n
Output:
-50x^-3 +3x^+1 -40x^+2 +10x^-5 -7x^+10 
Calculate value of Equation for given value (y/n)?
Enter value for the variable.
>>	 -413710.189300
Calculate value of Equation for given value (y/n)?
Enter value for the variable.
>>	 -7328.062500
Calculate value of Equation for given value (y/n)?
Enter value for the variable.
>>	 -10.000000
Calculate value of Equation for given value (y/n)?
Enter value for the variable.
Sorry Try something different
Calculate value of Equation for given value (y/n)?
Enter value for the variable.
>>	 -84.000000
Calculate value of Equation for given value (y/n)?
Enter value for the variable.
>>	 -7327.937500
Calculate value of Equation for given value (y/n)?
Enter value for the variable.
>>	 -413695.810700
Calculate value of Equation for given value (y/n)?
Exiting...

Code:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   Simple Polynomial data structure and
 *            Calculator for single variable.
 */

#include<stdio.h>
#include<string.h>
#include<math.h>


#define N 512


char input[N];


struct PolynomialEquation{

    char sign;
    char signExponent;
    int exponent;
    char variable;
    int constant;

    struct PolynomialEquation *next;
};
typedef struct PolynomialEquation node;



node* insertNode(node* current, char sign, int constant, char variable, char signExponent, int exponent){

    node* temp = new node();

    temp->sign = sign;
    temp->signExponent = signExponent;
    temp->exponent = exponent;
    temp->variable = variable;
    temp->constant = constant;

    temp->next = NULL;
    current->next = temp;
    current = temp;

    return current;
}


void printEquation(node* dummy){
    node* tmp = dummy->next;
    while( tmp != NULL ){
        printf("%c%d%c^%c%d ", tmp->sign, tmp->constant, tmp->variable, tmp->signExponent, tmp->exponent);
        tmp = tmp->next;
    }
    printf("\n");
}


void calculateEquation(node* dummy, int var){

    double sum = 0;
    bool calculable;


    node* tmp = dummy->next;
    while( tmp != NULL ){

        double constantValue = 0, variableValue = 0;
        calculable = true;


        constantValue = tmp->constant;
        if(tmp->sign == '-')
            constantValue *= -1;


        variableValue = pow(var, tmp->exponent);
        if(tmp->signExponent == '-'){
            if(variableValue)
                variableValue = (double) 1 / variableValue;
            else
                calculable = false;
        }


        sum = sum + variableValue * constantValue;
        tmp = tmp->next;


        if(!calculable){
            printf("Sorry Try something different\n");
            break;
        }

    }

    if(calculable)
        printf(">>\t %f\n", sum);

}


int main(){

    // Comment these lines to do I/O operation in console.
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);



    char sign;
    char signExponent;
    int exponent;
    char variable;
    int constant;



    node* dummy = new node();
    dummy->variable = '$';
    node* current = dummy;


    while( scanf("%c%d%c%*c%c%d", &sign, &constant, &variable, &signExponent, &exponent ) == 5){
        getchar();
        current = insertNode(current, sign, constant, variable, signExponent, exponent);
    }

    printEquation(dummy);


    while(1){
        printf("Calculate value of Equation for given value (y/n)?\n");

        char choice = getchar();

        if( choice == 'y' ){
            printf("Enter value for the variable.\n");

            int variableValue;
            scanf("%d", &variableValue);
            getchar();

            calculateEquation(dummy, variableValue);
        }else{
            printf("Exiting...\n");
            break;
        }
    }

    return 0;
}

 

Working with float numbers:

If the equation is,

f(x) = - 4x^{2} - 4x - 9

Input:
+4x^+2 -4x^+1 -9x^+0
0
y
5
y
2.5
y
1.25
y
1.875
n
Output:
+4x^+2 -4x^+1 -9x^+0 
Calculate value of Equation for given value (y/n)?
Enter value for the variable:
>>	 71.000000
Calculate value of Equation for given value (y/n)?
Enter value for the variable:
>>	 6.000000
Calculate value of Equation for given value (y/n)?
Enter value for the variable:
>>	 -7.750000
Calculate value of Equation for given value (y/n)?
Enter value for the variable:
>>	 -2.437500
Calculate value of Equation for given value (y/n)?
Exiting...

Code for float:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   Simple Polynomial data structure and
 *            Calculator with single variable.
 */

#include<stdio.h>
#include<string.h>
#include<math.h>


#define N 512


char input[N];


struct PolynomialEquation{

    char sign;
    char signExponent;
    int exponent;
    char variable;
    int constant;

    struct PolynomialEquation *next;
};
typedef struct PolynomialEquation node;



node* insertNode(node* current, char sign, int constant, char variable, char signExponent, int exponent){

    node* temp = new node();


    temp->sign = sign;
    temp->signExponent = signExponent;
    temp->exponent = exponent;
    temp->variable = variable;
    temp->constant = constant;


    temp->next = NULL;
    current->next = temp;
    current = temp;


    return current;
}


void printEquation(node* dummy){

    // dummy is just an empty node to keep track of front of equation.
    // It is not part of equation. Equation starts after dummy node.
    node* tmp = dummy->next;

    // Print the equation term by term.
    while( tmp != NULL ){
        printf("%c%d%c^%c%d ", tmp->sign, tmp->constant, tmp->variable, tmp->signExponent, tmp->exponent);
        tmp = tmp->next;
    }
    printf("\n");

}


void calculateEquation(node* dummy, double var){

    double sum = 0;
    bool calculable;


    // dummy->next because dummy node is not a part of the equation.
    node* tmp = dummy->next;

    while( tmp != NULL ){

        double constantValue = 0, variableValue = 0;
        calculable = true;

        // make constant negative if the sign is negative.
        constantValue = tmp->constant;
        if(tmp->sign == '-')
            constantValue *= -1;


        // calculate the value of the variable with given exponent.
        variableValue = pow(var, tmp->exponent);
        if(tmp->signExponent == '-'){
            if(variableValue)
                variableValue = (double) 1 / variableValue;
            else
                calculable = false;
        }


        // multiply the calculated value of variable with the constant.
        sum = sum + variableValue * constantValue;

        // calculate the next term of the equation.
        tmp = tmp->next;


        // If not calculable. Ex: divide by zero. then print this.
        if(!calculable){
            printf("Sorry Try something different\n");
            break;
        }

    }

    // print the result.
    if(calculable)
        printf(">>\t %f\n", sum);

}


int main(){

    // Comment these lines to do I/O operation in console.
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);



    char sign;
    char signExponent;
    int exponent;
    char variable;
    int constant;


    // Dummy node to make insertion code simpler.
    node* dummy = new node();
    dummy->variable = '$';
    node* current = dummy;


    // Take input of equation term by term.
    // If
    //     taking input from console stop input using null terminator ( ctrl + z ).
    // Else
    //     when taking input from file enter a 0 in a line by itself to stop input.
    while( scanf("%c%d%c%*c%c%d", &sign, &constant, &variable, &signExponent, &exponent ) == 5){
        getchar();
        current = insertNode(current, sign, constant, variable, signExponent, exponent);
    }

    // print the
    printEquation(dummy);


    // Enter different values for the variable to get the value of function.
    while(1){
        printf("Calculate value of Equation for given value (y/n)?\n");

        char choice = getchar();

        if( choice == 'y' ){
            printf("Enter value for the variable:\n");

            double variableValue;
            scanf("%lf", &variableValue);
            getchar();

            calculateEquation(dummy, variableValue);
        }else{
            printf("Exiting...\n");
            break;
        }
    }

    return 0;
}
Advertisements

Ternary Heap Sort Code in C++ using Heap Data structure

Introduction:

This code is implementation of ternary heap sort. The code requires no input. Data inputs (integers) are generated randomly then sorted using heap sort.

Only change the define SIZE value to for sorting large or small amount of numbers.

Code for Binary Heap Sort here.

Ternary Heap Sort Code Cpp:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: Ternary Heap Sort
 */

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>

#define SIZE 10
int A[SIZE], heapsize = SIZE;

void maxHeapify(int i){
    int largest;

    /**
     * Find right child index
     */
    int l = 3 * i + 1;

    /**
     * Compare left child against the current node
     */
    if(l < heapsize && A[l] > A[i])
        largest = l;
    else
        largest = i;

    /**
     * find mid child index
     */
    int m = 3 * i + 2;

    /**
     * Compare mid child against the calculated largest value node
     */
    if(m < heapsize && A[m] > A[largest])
        largest = m;

    /**
     * Find right child index
     */
    int r = 3 * i + 3;

    /**
     * Compare right child against the calculated largest value node
     */
    if(r < heapsize && A[r] > A[largest])
        largest = r;

    /*
     * If child nodes have larger value then current node
     */
    if(largest != i){
        /**
         * Swap the two values
         */
        std::swap(A[i], A[largest]);

        /**
         * Max heapify again rest of the heap
         */
        maxHeapify(largest);
    }
}

void buildMaxHeap(){
    int j;
    /**
     * operate on third of array
     */
    for(j = heapsize / 3 - 1; j >= 0; --j)
        maxHeapify(j);
}

void heapsort(){
    buildMaxHeap();

    int i;
    for(i = heapsize - 1; i > 0; --i){
        std::swap(A[0], A[i]);

        /**
         * Decrease the heap size as right of heap is already sorted
         */
        --heapsize;

        /**
         * Again max heapify the rest of the heap
         */
        maxHeapify(0);
    }
}

int main(){
    int i;

    clock_t begin, end;
    double time_elapsed;

    srand(time(NULL));
    for(i=0; i<SIZE; ++i){
        A[i] = rand() % SIZE;
        printf("%d ", A[i]);
    }
    printf("\n");

    printf("Sorting Now....\n");
    begin = clock();
    heapsort();
    end = clock();

    time_elapsed = (double)(end - begin) / CLOCKS_PER_SEC;

    for(i=0; i<SIZE; ++i)
        printf("%d ", A[i]);

    printf("\n\nTime elapsed: %lf\n", time_elapsed);

    return 0;
}

Pre order, In order, Post order, Level order Tree Traversal Reference Sheet

The reference sheet below shows the print traversal order for preorder, inorder, postorder and levelorder tree traversal.

Code for printing preorder, inorder, postorder and levelorder traversal is available here. Instructions for inputting a graph can be found in this tutorial.

Both recursive and iterative algorithms for tree traversal are available here.

Tree Input:
tree traversal input
tree traversal input

Tree Traversal Reference Sheet:

pre-in-post-level-order-tree-traversal
pre-in-post-level-order-tree-traversal

Inputting directed, undirected, weighted and unweighted graph in C, C++ Adjacency Matrix

The codes below uses 2D array adjacency matrix. For both sparse and dense graph the space requirement is always O(v2) in adjacency matrix. The codes below can be used take input and store graphs for graph algorithm related problems.

Related to this have a look at,

DIRECTED, UNDIRECTED, WEIGHTED, UNWEIGHTED GRAPH REPRESENTATION IN ADJACENCY LIST, MATRIX REFERENCE SHEET


Input for Directed Weighted Graph:

directed weighted input
directed weighted input

Code Directed Weighted Graph:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Type:    Directed Weighted Graph Input
 */

#include<stdio.h>

#define N 100

/*
 * Graph is the graph representation in adjacency matrix
 */
int Graph[N][N];

/*
 * u is the current or source vertex
 * v is the next or destination vertex
 * w is the edge weight or path cost
 */

int vertices, edges;
int u, v, w;
int i, j;

void InputGraph(){
    printf("Enter vertices and Edges:\n");
    scanf("%d%d", &vertices, &edges);

    // Reset graph
    for(i = 0; i < vertices; ++i)
        for(j = 0; j < vertices; ++j)
            Graph[i][j] = 0;

    // Input Graph
    printf("Enter (u v w):\n");
    for(i = 0; i < edges; ++i){
        scanf("%d%d%d", &u, &v, &w);
        Graph[u][v] = w;
    }
}

void PrintGraph(){
    // Print the current Graph
    printf("\n");
    printf("Graph:\n");
    for(i = 0; i < vertices; ++i){
        for(j = 0; j < vertices; ++j)
            printf("%d ", Graph[i][j]);
        printf("\n");
    }
    printf("\n");
}

int main(){

    printf("Directed Weighted Graph:\n");
    printf("============================\n\n");

    InputGraph();
    PrintGraph();

    return 0;
}

Input for Directed Unweighted Graph:

directed unweighted input
directed unweighted input

Code Directed Unweighted Graph:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Type:    Directed Unweighted Graph Input
 */

#include<stdio.h>

#define N 100

/*
 * Graph is the graph representation in adjacency matrix
 */
int Graph[N][N];

/*
 * u is the current or source vertex
 * v is the next or destination vertex
 */

int vertices, edges;
int u, v;
int i, j;

void InputGraph(){
    printf("Enter vertices and Edges:\n");
    scanf("%d%d", &vertices, &edges);

    // Reset graph
    for(i = 0; i < vertices; ++i)
        for(j = 0; j < vertices; ++j)
            Graph[i][j] = 0;

    // Input Graph
    printf("Enter (u v):\n");
    for(i = 0; i < edges; ++i){
        scanf("%d%d", &u, &v);
        // For directed graph edges (u,v) != (v,u)
        Graph[u][v] = 1;
    }
}

void PrintGraph(){
    // Print the current Graph
    printf("\n");
    printf("Graph:\n");
    for(i = 0; i < vertices; ++i){
        for(j = 0; j < vertices; ++j)
            printf("%d ", Graph[i][j]);
        printf("\n");
    }
    printf("\n");
}

int main(){

    printf("Directed Unweighted Graph:\n");
    printf("============================\n\n");

    InputGraph();
    PrintGraph();

    return 0;
}

Input for Undirected Weighted Graph:

undirected weighted input
undirected weighted input

Code Undirected Weighted Graph:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Type:    Undirected Weighted Graph Input
 */

#include<stdio.h>

#define N 100

/*
 * Graph is the graph representation in adjacency matrix
 */
int Graph[N][N];

/*
 * u is the current or source vertex
 * v is the next or destination vertex
 * w is the edge weight or path cost
 */

int vertices, edges;
int u, v, w;
int i, j;

void InputGraph(){
    printf("Enter vertices and Edges:\n");
    scanf("%d%d", &vertices, &edges);

    // Reset graph
    for(i = 0; i < vertices; ++i)
        for(j = 0; j < vertices; ++j)
            Graph[i][j] = 0;

    // Input Graph
    printf("Enter (u v w):\n");
    for(i = 0; i < edges; ++i){
        scanf("%d%d%d", &u, &v, &w);
        // For undirected edge (u,v) = (v,u)
        Graph[u][v] = Graph[v][u] = w;
    }
}

void PrintGraph(){
    // Print the current Graph
    printf("\n");
    printf("Graph:\n");
    for(i = 0; i < vertices; ++i){
        for(j = 0; j < vertices; ++j)
            printf("%d ", Graph[i][j]);
        printf("\n");
    }
    printf("\n");
}

int main(){

    printf("Undirected Weighted Graph:\n");
    printf("============================\n\n");

    InputGraph();
    PrintGraph();

    return 0;
}

 

Input for Undirected Unweighted Graph:

undirected unweighted input
undirected unweighted input

Code Undirected Unweighted Graph:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Type:    Undirected Unweighted Graph Input
 */

#include<stdio.h>

#define N 100

/*
 * Graph is the graph representation in adjacency matrix
 */
int Graph[N][N];

/*
 * u is the current or source vertex
 * v is the next or destination vertex
 */

int vertices, edges;
int u, v;
int i, j;

void InputGraph(){
    printf("Enter vertices and Edges:\n");
    scanf("%d%d", &vertices, &edges);

    // Reset graph
    for(i = 0; i < vertices; ++i)
        for(j = 0; j < vertices; ++j)
            Graph[i][j] = 0;

    // Input Graph
    printf("Enter (u v):\n");
    for(i = 0; i < edges; ++i){
        scanf("%d%d", &u, &v);
        // Here value of 1 represents there is an edge (u,v)
        Graph[u][v] = Graph[v][u] = 1;
    }
}

void PrintGraph(){
    // Print the current Graph
    printf("\n");
    printf("Graph:\n");
    for(i = 0; i < vertices; ++i){
        for(j = 0; j < vertices; ++j)
            printf("%d ", Graph[i][j]);
        printf("\n");
    }
    printf("\n");
}

int main(){

    printf("Undirected Unweighted Graph:\n");
    printf("============================\n\n");

    InputGraph();
    PrintGraph();

    return 0;
}

Directed, Undirected, weighted, Unweighted graph Representation in Adjacency list, matrix Reference Sheet

This is simple attempt to show Directed, Undirected, weighted, Unweighted graph Representation in Adjacency list, matrix. This can be helpful to understand how graph are represented or stored. The 2D adjacency matrix can be stored in 2D array and the adjacency list can be stored in linked list. A large value such as infinity may also mean there is no edge between two vertices. Graph representation in incidence matrix and list is not shown here.

For reference check out 10th chapter of DISCRETE MATHEMATICS AND ITS APPLICATIONS by Kenneth H. Rosen.


 

Graph Representation Reference Sheet:

graph representation reference sheet
graph representation reference sheet

Ternary Heap Sort Algorithm Implementation Using heap Data Structure

Ternary Heap Sort Algorithm Implementation Using heap Data Structure :


Ternary Heap Sort Algorithm Code:

#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<iostream>

#define SIZE 10000
long A[SIZE], heapsize = SIZE;

void maxHeapify(long i){
    long largest;

    /**
     * Find index of first, second, third child
     */
    long l = 3 * i + 1;
    long m = 3 * i + 2;
    long r = 3 * i + 3;

    /**
     * Find largest among the parent and its child. And save that index
     */
    if(l < heapsize && A[l] > A[i])
        largest = l;
    else
        largest = i;

    if(m < heapsize && A[m] > A[largest])
        largest = m;

    if(r < heapsize && A[r] > A[largest])
        largest = r;

    /**
     * If the largest index is not of parent then there is another bigger value
     * So swap that value with parent
     */
    if(largest != i){
        std::swap(A[i], A[largest]);
        maxHeapify(largest);
    }
}

void buildMaxHeap(){
    long j;
    /**
     * Starting from the last parent to root max heapify
     */
    for(j = heapsize / 3 - 1; j >= 0; --j)
        maxHeapify(j);
}

void heapsort(){
    buildMaxHeap();

    long i;
    /**
     * Send biggest value root in the end
     * then max heapify from root again
     * this procedure sorts in ascending order because of max heap
     */
    for(i = heapsize-1; i > 0; --i){
        std::swap(A[0], A[i]);

        --heapsize;
        maxHeapify(0);
    }
}

int main(){
    clock_t begin, end;
    double time_elapsed;

    srand(time(NULL));
    register long i = 0;
    for(; i < SIZE; ++i){
        A[i] = rand() % SIZE;
        //printf("%ld ", A[i]);
    }
    //printf("\n");

    begin = clock();
    heapsort();
    end = clock();

    time_elapsed = (double)(end - begin) / CLOCKS_PER_SEC;

    for(i = 0; i < SIZE; ++i)
        printf("%ld ", A[i]);

    printf("\n\nTime elapsed: %lf\n", time_elapsed);

    return 0;
}

Binary Heap Sort Algorithm Code Using Heap Data Structure

Binary Heap Sort Algorithm Code Using Heap Data Structure:


Binary Heap Sort Code:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 */

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>

#define SIZE 10000
long A[SIZE];

/**
 * In the beginning the heap size is same as the array size
 */
long heapsize = SIZE;

void maxHeapify(long i){
    long largest;

    /**
     * Find right child index
     */
    long l = 2 * i + 1;

    /**
     * Compare left child against the current node
     */
    if (l < heapsize && A[l] > A[i])
        largest = l;
    else
        largest = i;

    /**
     * Find right child index
     */
    long r = 2 * i +2;

    /**
     * Compare right child against the calculated largest value node
     */
    if (r < heapsize && A[r] > A[largest])
        largest = r;

    /**
     * Swap the current value with the largest value
     */
    if (largest != i){
        /**
         * Swap the two values
         */
        std::swap(A[i], A[largest]);

        /**
         * Max heapify again rest of the heap
         */
        maxHeapify(largest);
    }
}


void buildMaxHeap(){
    register long j;
    /**
     * Start from the last parent and go to root
     */
    for (j = heapsize / 2 - 1; j >= 0; --j)
        maxHeapify(j);
}


void heapsort(){
    buildMaxHeap();
    /**
     * Start from the end of heap swap with root and decrease heap size
     * We know in max heap the biggest item is on top so swapping with the
     * last element will put the biggest value in the end. That way the
     * smallest value will be at the beginning and the biggest will be at the end
     * So by using max heap we can sort in Ascending order.
     */
    register long i;
    for (i = heapsize - 1; i > 0; --i){
        std::swap(A[0], A[i]);
        --heapsize;
        maxHeapify(0);
    }
}

int main(){
    register long i = 0;

    clock_t begin, end;
    double time_elapsed;

    srand(time(NULL));
    for (i = 0; i < SIZE; ++i)
        A[i] = rand() % SIZE;

    begin = clock();
    heapsort();
    end = clock();

    time_elapsed = (double)(end - begin) / CLOCKS_PER_SEC;

    /**
     * Comment this code if you do not want to see sorted output but just time
     */
    for(i = 0; i < SIZE; ++i)
        printf("%ld ", A[i]);

    printf("\n\nTime elapsed: %lf\n", time_elapsed);

    return 0;
}

UVA Problem 673 – Parentheses Balance Solution

UVA Problem 673 – Parentheses Balance Solution:


Click here to go to this problem in uva Online Judge.

Solving Technique:

This problem can be solved easily using Stack ( also check out these problems i have solved using stack uva 11192uva 483 ).  Here the only corner case is space character. Input only contains three types of character 1st bracket, 3rd bracket and a space character.

Here i have provided three solutions. All have same logic. But first one is well commented and written for easier understanding. Second one is modified version of first. For the first and second code i take input as string but in the last i take input one by one as characters.

In the second code i have checked if length is odd then i know it can’t be balanced. So i just print NO. Which is “strlen(par) & 1“. It is equivalent to “strlen(par) % 2 == 1” meaning string length is odd.

The logic for this code is whenever we find a closing bracket it must have its corresponding opening bracket before ( to its immediate left ) that. So we remove those two and keep processing rest of the input. Example,

[ [(  )]  ()]

Here we do nothing ( or, store them in string ) when we find an opening bracket. Whenever we find a closing bracket we see the character before that ( to its left ) is its opening bracket. If this condition doesn’t match then there is error in the input. So break immediately. Also when we find a closing bracket with its opening bracket we remove them and process rest of the input. Example,

[ [(  )]  ()]  /* our input */
[ [] ()]       /* we remove first occurrence of closing and its corresponding opening bracket to its left */
[ ()]          /* Process rest of the input */
[ ]
               /* Here nothing is left so it is a valid input */

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.


Critical Input:

More Critical inputs can be found in this link,

https://gist.github.com/quickgrid/72b1adc38d8752cd6905

3
([])
(([()])))
([ ()[  ]  ( )])()

Output:

Yes
No
Yes

Code Usage of Stack ( Explained ):

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 673 ( Parentheses Balance )
 */

#include<stdio.h>

/**
 * Size for our stack although they said 128 but stack safety
 */
#define SIZE 256

/**
 * Our stack or array to hold parenthesis
 */
static char stack[SIZE];
/**
 * Our stack index counter
 */
int top = -1;

/**
 * Push function of out stack, We basically store the character and increase the counter
 * Checking of stack overflow is not implemented since stack size is large enough for this program
 */
void push(char c){
    stack[++top] = c;
}

/**
 * Set the element in current index to NUL and decrease the index
 * Stack underflow never occurs for this program
 */
void pop(){
    stack[top--] = '\0';
}

int main(){
    register unsigned n, i;
    unsigned char c;

    /**
     * Scan the test case count, getchar() is needed because i used gets() below which takes away my new line if getchar() is not used
     */
    scanf("%u", &n); getchar();

    while (n--){
        stack[SIZE] = {'\0'};
        /**
         * Reset the stack index, meaning we start using our stack array from the beginning
         */
        top = -1;
        /**
         * If no error then error is 0 else if there is error then error is 1
         */
        unsigned error = 0;

        /**
         * Our character array to take the input string
         */
        char *par = new char[SIZE + 1];
        gets(par);

        for (i = 0; par[i]; ++i){
            /**
             * Corner case the input can have space
             */
            if(par[i] == ' ')
                continue;

            /**
             * Push the character to stack if open bracket
             */
            if(par[i] == '[' || par[i] == '(')
                push(par[i]);

            /**
             * Pop or remove the element from top of stack if matching closing bracket found
             */
            else if(par[i] == ']' && stack[top] == '[')
                pop();
            else if(par[i] == ')' && stack[top] == '(')
                pop();

            else{
                /**
                 * If matching closing bracket not found then set error flag to 1 (ON)
                 */
                error = 1;
                /**
                 * Since we found a mistake there is no need to process rest of the string
                 */
                break;
            }
        }

        /**
         * If error flag is on or there still exist some brackets on stack then print NO
         */
        if(error || top > -1)
            printf("No\n");
        else
            printf("Yes\n");
    }
    return 0;
}

Taking input as string:(Faster)

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 673 ( Parentheses Balance )
 */

#include<stdio.h>
#include<string.h>

static char stack[256];
static char par[256];
int top;

int main(){
    unsigned n, error;

    scanf("%u", &n);
    getchar();

    while(n--){
        gets(par);

        if(strlen(par) & 1)
            printf("No\n");
        else{
            stack[256] = {'\0'};
            top = -1;
            error = 0;

            for(unsigned i = 0; par[i]; ++i){
                if(par[i] == ' ')
                    continue;

                if(par[i] == '[' || par[i] == '(')
                    stack[++top] = par[i];
                else if((par[i] == ')' && stack[top] == '(') || (par[i] == ']' && stack[top] == '['))
                    --top;
                else{
                    error = 1;
                    break;
                }
            }

            (error || top > -1) ? printf("No\n") : printf("Yes\n");
        }
    }
    return 0;
}

Taking input one by one as characters:

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 673 ( Parentheses Balance )
 */

#include<stdio.h>

#define SIZE 256

char stack[SIZE];

int main(){
    register unsigned n, i;
    unsigned ch;
    scanf("%u", &n); getchar();

    while(n--){
        register int top = -1;
        unsigned error = 0;

        while ((ch = getchar()) != '\n'){
            if (ch == ' ') continue;
            if (ch == '[' || ch == '(') stack[++top] = ch;
            else if ((ch == ']' && stack[top] == '[') || (ch == ')' && stack[top] == '(')) --top;
            else error = 1;
        }

        if (error || top > -1) printf("No\n");
        else printf("Yes\n");
    }
    return 0;
}

UVA Problem 1368 – DNA Consensus String Solution

UVA Problem 1368 – DNA Consensus String Solution:


Click here to go to this problem in uva Online Judge.

Solving Technique:

Rank 174, Run time 12 ms ( 0.012 s ).

First input is number of test cases. Next of two inputs one is number of strings to input and another is the size of string. Our strings will only contain A, C, G, T characters.

For solving this problem we first need to find consensus string. That is of all strings we check each column of all strings and count the maximum occurring character in that column. This character is our consensus string character for that column.

Consensus string size is same as the input string size. Since each of its characters are maximum occurring characters in the input string. Example,

TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT
========
TAAGATAC    /* Consensus String, check each column for max character count */

Now that we have found the consensus string we just need to find consensus error. I will only explain the logic here, I have commented my code below.

TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT
========
TAAGATAC    /* Consensus String */
========
11101021    /* Consensus Error, 1+1+1+0+1+0+2+1 = 7, count every character of a column that don't match that consensus string character */

Now if you understood my explanation time to go write a better solution :).

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.


Input:

3 
5 8 
TATGATAC 
TAAGCTAC 
AAAGATCC 
TGAGATAC 
TAAGATGT 
4 10 
ACGTACGTAC 
CCGTACGTAG 
GCGTACGTAT 
TCGTACGTAA 
6 10 
ATGTTACCAT 
AAGTTACGAT 
AACAAAGCAA 
AAGTTACCTT 
AAGTTACCAA 
TACTTACCAA

Output:

TAAGATAC 
7 
ACGTACGTAA 
6 
AAGTTACCAA 
12

Code:

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 1368 ( DNA Consensus String )
 */

#include<stdio.h>

int main(){
    register unsigned n, a, b, i, j, k, error;
    scanf("%u", &n);

    while(n--){
        scanf("%u%u", &a, &b);

        /**
         * Create the string array
         */
        char **s = new char*[a+1];
        for(i = 0; i < a; ++i){
            /**
             * Allocate space for each string
             */
            s[i] = new char[b+1];
            /**
             * Input a string in i th position
             */
            scanf("%s", s[i]);
        }

        /**
         * Consensus string declaration
         */
        char *conseq = new char[b+1];
        /**
         * K is used below
         */
        for(k = i = 0; i < b; ++i){
            /**
             * Reset A,C,G,T count array
             */
            unsigned int seq[4] = {0};
            for(j = 0; j < a; ++j){
                switch(s[j][i]){
                case 65:    /* 65, 'A' here seq[0] is A */
                    ++seq[0];
                    break;
                case 67:    /* 'C' */
                    ++seq[1];
                    break;
                case 71:    /* 'G' */
                    ++seq[2];
                    break;
                case 84:    /* 'T' */
                    ++seq[3];
                }
            }

            unsigned max = seq[0], maxIndex = 0;
            for(j = 1; j < 4; ++j){
                if(seq[j] > max){
                    /**
                     * Find the max count of A,C,G,T in a column, in all strings
                     */
                    max = seq[j];
                    /**
                     * Remember the maxIndex for creating consensus string
                     */
                    maxIndex = j;
                }
            }

            /**
             * We keep adding to our consensus string the most count of A,C,G,T
             */
            switch(maxIndex){
            case 0:
                conseq[k++] = 65;
                break;
            case 1:
                conseq[k++] = 67;
                break;
            case 2:
                conseq[k++] = 71;
                break;
            case 3:
                conseq[k++] = 84;
            }
        }

        for(error = i = 0; i < b; ++i){
            for(j = 0; j < a; ++j){
                /**
                 * Calculate the error count by moving column by column of all strings, then comparing against the consensus string character in that column
                 */
                if(s[j][i] != conseq[i])
                    ++error;
            }
        }

        /**
         * Print the consensus string and error count EACH ON A NEW LINE
         */
        printf("%s\n%u\n", conseq, error);
    }
    return 0;
}

UVA Problem 612 – DNA Sorting Solution

UVA Problem 612 – DNA Sorting Solution:


Click here to go to this problem in uva Online Judge.

Solving Technique:

The best solution for this problem took 0.020 s. Mine took 0.142 s. There is an efficient algorithm to solve this problem. My approach is brute force, check all possible combination and count. Besides solving the problem another goal was implement some less used techniques/concepts.

So the problem basically requires us to sort and print strings based on sortedness. The way to calculate this is,

  1. The way to calculate this sortness is to take a string and compare each characters to its right.
  2. If the character on the right are smaller than the current character we increase the inversion count.
  3. The greater the count the less sorted ( confused!! ) a string is. ( Please do this with pen and paper )

Another thing to note is that if inversion count for multiple string is same then we should print the string that was given to us first. Last thing is print a blank line after each test case.

Now this code may look confusing,

char **s = new char*[t+1];

It is a way to declare an array of strings in C. The [t+1] initializes the string count. We need use a for loop to initialize string size for each strings. That is,

s[i] = new char[w+1];

Here s[i] is a string. We allocate memory for it using new char[w+1].

Here I used bubble sort to sort the strings. At first i tried selection sort and failed miserably because it doesn’t maintain the relative ordering of the strings. So using the sort I am sorting in ascending order. Also sort the inversion count array since it is mapped to strings array. Swap is a built-in function.

std::swap(inv[j], inv[j+1]); /* Swap the inversion count */
std::swap(s[j], s[j+1]);

Now that you understand the problem time to go write a better solution :).

Update (Added Insertion Sort):

I have added insertion sort for this code. Any stable sort such as insertion, merge sort etc should also work.
Just copy the code below and replace the bubble sort marked portion of code with this insertion sort code. It runs a bit faster than bubble sort. Also don’t forget to add include cstring header file.

/*
 * Insertion Sort
 */
unsigned key;
int q;
char *strkey = new char[w + 1];
for(i = 1; i < t; ++i){
    key = inv[i];
    strcpy(strkey, s[i]);
    q = i - 1;
    while(q >= 0 && inv[q] > key){
        inv[q + 1] = inv[q];
        strcpy(s[q + 1], s[q]);
        --q;
    }
    inv[q + 1] = key;
    strcpy(s[q + 1], strkey);
}

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.


Input:

1

10 6
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT

Output:

CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA

Code ( Using Bubble Sort ):

/*
 * @author Quickgrid ( Asif Ahmed )
 * @link   https://quickgrid.wordpress.com
 * Problem UVA 612 (DNA Sorting)
 */

#include<cstdio>
#include<iostream>

int main(){
    register unsigned n,i,j,k;
    unsigned blank = 0;

    scanf("%u", &n);
    while (n--){
        unsigned w,t;
        scanf("%u%u", &w, &t);

        /* Array of strings, initialize element count */
        char **s = new char *[t + 1];
        /* Mapping array for sortedness count */
        unsigned *inv = new unsigned[t + 1];

        for (i = 0; i < t; ++i){
            /* Initialize size of each string in array */
            s[i] = new char[w + 1];
            scanf("%s", s[i]);
            inv[i] = j = 0;
            for (; j < w; ++j){
                for (k = j + 1; k < w; ++k){
                    if (s[i][j] > s[i][k])
                        /* Count sortedness, number of inversions */
                        ++inv[i];
                }
            }
        }

        /*
         * Bubble sort
         * Any stable sort should be able to sort it correctly e.g. insertion sort, merge sort
         */
        for (i = 0; i < t - 1; ++i){
            for (j = 0; j < t - i - 1; ++j){
                if (inv[j] > inv[j+1]){
                    /* Swap the inversion count */
                    std::swap(inv[j], inv[j+1]);
                    /* Swap the strings */
                    std::swap(s[j], s[j+1]);
                }
            }
        }

        /* Print a blank line for consecutive test cases */
        if (blank) printf("\n");
        blank = 1;

        for (i = 0; i < t; ++i)
            printf("%s\n", s[i]);
    }
    return 0;
}