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;
}
Advertisements

Tree Implementation in both custom Linked list and Array stack and Traversal In order, Pre order, Post order, Level order, Level print , Height print

Tree Implementation in both custom Linked list and Array stack and Traversal In order, Pre order, Post order, Level order, Level print , Height print:

Code Explanation:

This code is bit complex and will require knowledge on:

  1. Struct
  2. Linked list
  3. Queue
  4. Stack
  5. Binary Tree ( check this and this too  )

Input Format:

Level Order tree input style
Level Order tree input style
binary Tree Graph sample Input for the console picture shown above
binary Tree Graph sample Input for the console picture shown above

Code:

/*
 * Author: Quickgrid
 * Code: Tree creation, traversal in array & linked list ( inorder/preorder/postorder/levelorder )
 * Description:
 */

#include <stdio.h>

#define size 1000   /* used this for queue array */

struct tree{    /* binary tree structure */
    char data;
    struct tree *left;
    struct tree *right;
};
typedef struct tree node;

struct stack{   /* linear/singly linked list stack to hold tree type data */
    node *nodedata;
    struct stack *next;
};
typedef struct stack vertex;

node* q[size];  /* here our array is node data type that we defined above */
int f = 0, r = 0;
vertex *front = NULL, *rear = NULL;
node *root = NULL;

void enq(node *root){   /* circular queue array modular arithmetic */
    int s = (r+1) % (size+1); /* +1 means we don't use 1 box of the array */
    if(f == s){
        printf("Queue Full.\n");
        return;
    }
    q[s] = root; /* root is node type we put it in our node array */
    r = s;  /* s is temporary variable */
}

node *deq(){
    if(f==r){
        printf("Queue Empty.\n");
        return NULL;
    }
    f = (f+1)%(size+1);
    node *temp = q[f]; /* get the last element of the queue to return for further operations */
    q[f] = 0;
    return temp;
}

void levelOrderArray(node *root){
    enq(root);  /* here we enqueue the root or the node that we want to star from */
    while(f!=r){ /* check if our queue is not empty */
        node *v = deq(); /* dequeue one item */
        printf("%c ", v->data);
        if(v->left!=NULL){ /* check if left branch of tree exists */
           enq(v->left); /* send the left node to queue */
        }
        if(v->right!=NULL){ /* check if right branch of tree exists */
            enq(v->right); /* send the right node to queue */
        }
    }
}

void enqueue(node *root){   /* enqueue function for our stack in linked list */
    if(front == NULL){
        front = new vertex();
        front->nodedata = root;
        front->next = NULL;
        rear = front;
    }else{
        vertex *temp = new vertex();
        temp->nodedata = root;
        temp->next = NULL;
        rear->next = temp;
        rear = temp;
    }
}

vertex *dequeue(){
    if(front == NULL){
        printf("queue empty.\n");
        return front;
    }
    vertex *temp,*tmp = front;
    front = front->next;
    delete temp;
    return tmp;
}

void levelorder (node *root){
    enqueue(root);
    while ( front != NULL ){
        vertex *v = dequeue();  /* we dequeue one vertex type data from our vertex stack */
        if(v!=NULL){
            printf("%c",v->nodedata->data);

            if (v->nodedata->left != NULL){ /* nodedata is our data part which holds node type data */
                enqueue(v->nodedata->left);
            }
            if (v->nodedata->right != NULL){
                enqueue(v->nodedata->right);
            }
        }
    }
}

int treeHeight(node *root){
    if(root == NULL){
        return 0;
    }
    int leftHeight = treeHeight(root->left);
    int rightHeight = treeHeight(root->right);

    if(leftHeight > rightHeight){
        return leftHeight+1;
    }else{
        return rightHeight+1;
    }
}

void printGivenLevel(node *root, int level){
    if(root == NULL){
        return;
    }
    if(level == 1){
        printf("%c ", root->data);
    }else if(level > 1){
        printGivenLevel(root->left, level-1);
        printGivenLevel(root->right, level-1);
    }
}

void createBinaryTree (node *root)
{
    char ans;

    fflush(stdout);
    printf("%c has any left child: ", root->data);
    fflush(stdin);
    ans = getchar();

    if (ans == 'y') /* create left side of a tree node */
    {
        root->left = new node ();
        root->left->left = NULL;
        root->left->right = NULL;
        fflush(stdout);
        printf("Enter left data of %c: ", root->data);
        fflush(stdin);
        scanf("%c",&root->left->data);
        createBinaryTree (root->left);  /* recursive call with created node as root to check if it has left and right */
    }

    fflush(stdout);
    printf("%c has any right child: ", root->data);
    fflush(stdin);
    ans = getchar();

    if (ans == 'y') /* create right side of a tree node */
    {
        root->right = new node ();
        root->right->left = NULL;
        root->right->right = NULL;
        fflush(stdout);
        printf("Enter right data of %c: ", root->data);
        fflush(stdin);
        scanf("%c",&root->right->data);
        createBinaryTree (root->right);
    }
}

void postOrder(node *root){
    if(root->left!=NULL){
        postOrder(root->left);
    }
    if(root->right!=NULL){
        postOrder(root->right);
    }
    printf("%c ", root->data);
}

void preOrder(node *root){
    printf("%c ", root->data);
    if(root->left!=NULL){   /* check if left side of that node exist */
        preOrder(root->left);   /* recursive call of preorder using this node as the root */
    }
    if(root->right!=NULL){
        preOrder(root->right);
    }
}

void inOrder(node *root){
    if(root->left!=NULL){
        inOrder(root->left);
    }
    printf("%c ", root->data);
    if(root->right!=NULL){
        inOrder(root->right);
    }
}

int main ()
{
    char ans;
    fflush(stdout);
    printf("Do u want to create a tree: ");
    fflush(stdin);
    ans = getchar();

    root = new node ();
    fflush(stdout);
    printf("Enter root of tree: ");
    fflush(stdin);
    scanf("%c",&root->data);
    createBinaryTree(root);

    int height = treeHeight(root);
    printf("\nTree Height: %d", height);

    printf("\nLevel order Linked List: ");
    levelorder(root);   /* Instead of sending root we can send another node to level order from that node */
    printf("\nLevel order Array: ");
    levelOrderArray(root);
    printf("\nPre order : ");
    preOrder(root);
    printf("\nIn order : ");
    inOrder(root);
    printf("\nPost order : ");
    postOrder(root);

    printf("\nEnter level to print:");
    int level;
    scanf("%d", &level);
    if(level >= height || level < 1){
        printf("\nGiven level doesn't exist.");
    }else{
        printf("Level %d: ", level);
        printGivenLevel(root, level);
        printf("\n");
    }
    return 0;
}

UVA Problem 591 ( Box of Bricks ) Solution

UVA Problem 591 ( Box of Bricks ) Solution:


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

Solving Technique:

If we read this problem carefully then there are a some very important clues,

  1. make all stacks the same height (line 2)
  2. he sets out to rearrange the bricks, one by one (line 3)
  3. The total number of bricks will be divisible by the number of stacks (line 7)

From the above points and problems description it is clear that Little Bob can only move the blocks one by one. Also the first line of input will be less or equal to 50 and the block heights will be less than or equal to 100. So we can use integer ( also unsigned integer ) for them.

Another thing it is said that dividing sum of stack heights with stack count is always possible. Meaning that gives us the height of the wall ( total stacks height sum, h[i] / stack count, n ).

The technique is there can be three types of box stack. That is equal to, less than or greater than height of the wall( total stacks height sum, h[i] / stack count, n ).

Since Bob can move boxes one by one it doesn’t matter which stack to start from. We can find the number of blocks to move from by only subtracting those stack that are greater in height than the max wall height. No need to perform this action on stacks that are equal or less high than max wall height.

So the result is the sum of subtraction of each stacks that are greater than from ( all stack sum / stack count ). Also since blocks are moved one by one this is the final result.

Important:   We normally print a new line after each output line but for this problem asks us to Output a blank line after each set. Meaning with our normal line break we need to add another line break. Be sure to add or print a new line after each output. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.


Code Explanation:

  1. First I take the stack count and loop that many times. [ also reset moves, and c ( count ) variable each time ]
  2. Now for each loop I take the height of stack in an array and sum it.
  3. Next I find the wall height by dividing the sum with stack count.
  4. Now I use another loop to loop through the array. In it subtract elements greater than stack height and also sum up this value to moves ( number of box movement needed ).
  5. Lastly I print in the exact format the problem asked.
  6. One more thing I printed an extra newline because the problem asked for a blank line after each set.

Input:

6
5 2 4 1 7 5
0

Output:

Set #1
The minimum number of moves is 5.

Code:

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

#include<stdio.h>

static int a[128];

int main(){
    register int i, c = 1;
    int n, sum, maxHeight, moves, temp;

    while (scanf("%d", &n) && n){
        moves = sum = 0;

        for (i = 0; i < n; ++i){
            scanf("%d", &a[i]);
            sum += a[i];
        }

        maxHeight = sum / n;

        for (i = 0; i < n; ++i){
            if(a[i] > maxHeight)
                moves += a[i] - maxHeight;
        }

        printf("Set #%d\nThe minimum number of moves is %d.\n\n", c++, moves);
    }
    return 0;
}

UVA Problem 11192 ( Group Reverse ) Solution

UVA Problem 11192 ( Group Reverse ) Solution:


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

Solving Technique:

This one is a bit tricky. Also it seems to be closely related to this ( 483 word scramble ) uva problem. Basically for this problem we are to take an integer ( which is the number of groups ) and a string until we are given a 0. Now our input is given like this,

3 ABCEHSHSH

5 FA0ETASINAHGRI0NATWON0QA0NARI0

0

So, the first problem for beginner is taking input for this. From the input we can easily see that there are two parts and the first part is an integer and second part is a string. Also we need to keep taking input until we find 0. What if we divide our scanf or input taking into two parts. First take the integer and check if its 0 or not then if it’s not zero then take the string and continue like this.

Our first input is an integer which is group number or number of parts the string can be divided to. So, from the given problem statement,

TOBENUMBERONEWEMEETAGAINANDAGAINUNDERBLUEICPCSKY

This string has length 48. We have divided into 8 groups of equal length and so the length of each group is 6. Meaning each group or each part of sentence will consist of 6 characters.

UNEBOTNOREBMEEMEWENIAGATAGADNAEDNUNIIEULBRYKSCPC

Our task is to reverse print/output each and every group. We can easily find how many members are in each group by dividing the length of the string with input ( number of groups ) we are given.

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


Code Explanation:

Here I have used stack data structure ( see this and this ) to solve this problem. First I find the length of the string then find how many characters in each group by dividing string length with group number. I also keep a counter ” x “ and keep pushing each character of the string in stack until I reach the last character or until our counter is not equal to the group member count. Also increment the counter each time i push into the stack. Also I keep a condition to check if  I have reach the last character or until our counter is equal to the group member count then pop until our loop counter has reached zero. Since stack is a LIFO data structures the last character i pushed into the stack are the first one to come out ( meaning they are outputted in reverse order ). This process keeps running until we reach the end of the sentence.


Input:

3 ABCEHSHSH
5 FA0ETASINAHGRI0NATWON0QA0NARI0
0

Output:

CBASHEHSH
ATE0AFGHANISTAN0IRAQ0NOW0IRAN0

Commented Code ( See the next Code for easier understanding of stack ):

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

#include<stdio.h>

/**
 * Input string buffer
 */
static char s[128];

/**
 * Global index for accessing input array, may be declared inside main
 */
int top = -1;

int main(){
    register unsigned j,u,n,i,x;

    /**
     * Input group count and Check if count is Not Zero
     */
    while (scanf("%u", &n) && n) {
        scanf("%s", s);

        /**
         * Find out input string size
         */
        for (j = 0; s[j]; ++j);

        /**
         * Find out length of each group
         */
        n = j / n;

        /**
         * Group Reverse loop
         */
        for (x = i = 0; i < j; ++i) {
            /**
             * For checking is the item after is NUL terminator
             */
            u = s[i + 1];

            /**
             * @var u
             * If the character after current is NUL then NOT u, is True
             *
             * @var n
             * Check to see if characters in group count is NOT full, then push more to stack
             */
            if ( !u || x != n ) {
                /**
                 * Push current character on top of stack
                 */
                s[++top] = s[i];
                /**
                 * Keep a count of characters pushed on stack
                 */
                ++x;
            }

            /**
             * If character limit per group is reached then Condition is True
             */
            if ( !u || x == n ) {
                /**
                 * Empty the the stack for every pushed character
                 */
                while (x--){
                    /**
                     * Output character by character in reversed form
                     */
                    printf("%c", s[top]);
                    --top;
                }
                x = 0;
            }

        }
        printf("\n");
    }
    return 0;
}

Code:

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 */

#include<stdio.h>

char s[101];
int top = -1;

void push(char c){
    if(top + 1 >= 101)
        return;

    s[++top] = c;
}

void pop(){
    if (top == -1)
        return;

    printf("%c", s[top]);
    s[top--] = '\0';
}

int main(){
	int n,j,i,x;
	while (scanf("%d", &n) == 1 && n != 0){
        x = 0;
        scanf("%s", &s);
        for (i = 0; s[i]; ++i);
        n = i / n;

        for (i = 0; s[i]; ++i){
            if (s[i+1] == '\0' || x != n){
                push(s[i]);
                ++x;
            }

            if (s[i+1] == '\0' || x == n){
                while (x--)
                    pop();

                x = 0;
            }
        }

        printf("\n");
	}
	return 0;
}

BFS Sequence for Unirected Graph in C++

Code Explanation:

Coming soon maybe…… Until then please look at the commented code.

Example Graph:

Example Undirected Graph for applying BFS
Example Undirected Graph for applying BFS

Code:

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

#include<stdio.h>

#define size 100

/**
 * Here nodes are represented with characters
 */
char vertex[size], visited_sequence[size], q[size];

/**
 * The graph which is a 2D matrix
 */
int graph[size][size];

/**
 * Counters for visited sequence, queue etc
 */
int count_visited_seq = 0, f = 0, r = 0, n;


/**
 * Update the visited sequence array
 */
void visit(char v)
{
    visited_sequence[count_visited_seq++] = v;
}


/**
 * Check the visited sequence array against a node
 * to see if it is already visited
 */
int isVisited(char v)
{
    for(int i = 0; i != count_visited_seq; ++i)
    {
        if(visited_sequence[i] == v)
        {
            return 1; // means already visited
        }
    }
    return 0; // not visited
}


/**
 * Display the BFS visited sequence
 */
void displayVisitedSequence()
{
    for(int i = 0; i < count_visited_seq; ++i)
    {
        printf("%c ", visited_sequence[i]);
    }
    printf("\n");
}


void enqueue(char v)
{
    int s = (r + 1) % (size + 1);
    if(s == f)
    {
        return;
    }
    q[s] = v;
    r = s;
}


char dequeue()
{
    if(f == r)
    {
        return '\0';
    }
    f = (f + 1) % (size + 1);
    char v = q[f];
    q[f] = '\0';
    return v;
}


/**
 * Check the adjacent nodes of given node to see if there is an edge
 * Also check if it is not already visited then enter it to queue
 */
void checkAdjecency(char v)
{
    for(int i = 0; i != n; ++i)
    {
        if(vertex[i] == v)
        {
            for(int j = 0; j != n; ++j)
            {
                if(graph[i][j] == 1 && !isVisited(vertex[j]))
                {
                    enqueue(vertex[j]);
                }
            }
        }
    }
}


/**
 * Create undirected graph, map characters as nodes identifiers
 * Reset the graph meaning set 0, to point out no edge exist
 */
void createGraph()
{
    int i, j;
    for(i = 0; i < 26; ++i)
    {
        vertex[i] = i + 'A';
    }

    printf("How many vertex:\n");
    scanf("%d", &n);
    for(i = 0; i != n; ++i)
    {
        for(j = 0; j != n; ++j)
        {
            graph[i][j] = 0;
        }
    }

    for(i = 0; i != n; ++i)
    {
        for(j = i + 1; j != n; ++j)
        {
            printf("%c-%c exist:\n", vertex[i], vertex[j]);
            scanf("%d", &graph[i][j]);
            if(graph[i][j] == 1)
            {
                graph[j][i] = graph[i][j];
            }
        }
    }
}


/**
 * Start processing the queue
 */
void BFS()
{
    char v;
    int exit = 0;
    while(1)
    {
        fflush(stdout);
        printf("Enter a node to Enqueue:\n");
        fflush(stdin);
        scanf("%c", &v);
        for(int i = 0; i != n; ++i)
        {
            if(vertex[i] == v)
            {
                enqueue(vertex[i]);
                exit = 1;
            }
        }
        if(exit)
        {
            break;
        }
    }

    while(f != r)
    {
        char v = dequeue();
        if(!isVisited(v))
        {
            visit(v);
        }
        checkAdjecency(v);
    }
}


int main()
{
    createGraph();
    BFS();
    displayVisitedSequence();
    return 0;
}

Stack Queue Array Hybrid (Data Structure)

Description: Here i combined my knowledge of stack and queue array into a single code. Firstly we are working with Queue. We can enqueue items in a queue. But when we dequeue the dequeued item is pushed to the stack ( We push the dequeued item in stack ) . The items pushed in stack are in the same order as they were in queue  since Queue is FIFO ( First In First Out ) data structure. We can also pop items from that stack. Now when we pop them they are enqueued back to the queue. The interesting thing is when they are popped they fill up the queue in reverse order since Stack is LIFO ( Last In First Out ) data structure.


input system
stack queue data structure 1
input system
stack queue data structure 2

Stack Functions: pop(), push(), displayStack(), searchStack()

Queue Functions: enqueue(), dequeue(), displayQueue(), searchQueue()


Code:

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

#include<stdio.h>

#define size 100

int q[size+1], f = 0, r = 0;
int s[size], top = -1;

void showMenu()
{
    printf("1.Enqueue\n");
    printf("2.Dequeue\n");
    printf("3.Show Queue\n");
    printf("4.Search Queue\n");
    printf("5.Show Stack\n");
    printf("6.Search Stack\n");
    printf("7.Pop stack\n");
    printf("8.Exit\n");
}

void push(int item)
{
    if(top+1 >= size)
    {
        printf("stack Overflow.\n");
        return;
    }
    s[++top] = item;
}

void displayQueue()
{
    int i = (f+1) % (size+1);
    for(int j=i; j!=r+1; ++j)
    {
        if(j>size)
        {
            j = 0;
        }
        if(f != r)
        {
            printf("%d ", q[j]);
        }
    }
    printf("\n");
}

void enqueue(int num)
{
    int s = (r+1) % (size+1);
    if(s == f)
    {
        printf("Queue Full.\n");
        return;
    }
    q[s] = num;
    r = s;
}

void dequeue()
{
    if(f == r)
    {
        printf("Queue empty.\n");
        return;
    }
    f = (f+1) % (size+1);
    printf("%d\n", q[f]);
    push(q[f]);
    q[f] = 0;
}

void searchQueue(int item)
{
    int i = (f+1) % (size+1);
    for(int j=i; j!=r+1; ++j)
    {
        if(j > size)
        {
            j = 0;
        }
        if(f!=r)
        {
            if(q[j] == item)
            {
                printf("%d found in queue\n", item);
            }
        }
    }
}

void searchStack(int item)
{
    for(int i=0; i<=top; ++i)
    {
        if(s[i] == item)
        {
            printf("%d found at index: %d\n", item, i);
        }
    }
}

void displayStack()
{
    for(int i=0; i<=top; ++i)
    {
        printf("%d ", s[i]);
    }
    printf("\n");
}

void pop()
{
    if(top == -1)
    {
        printf("Stack Underflow.\n");
        return;
    }
    printf("%d\n", s[top]);
    enqueue(s[top]);
    s[top--] = 0;
}

int main()
{
    int choice, exitcode = 1, item;

    do
    {
        showMenu();
        printf("Enter choice:\n");
        scanf("%d", &choice);
        switch(choice)
        {
        case 1:
            printf("Enter item to enqueue:\n");
            scanf("%d", &item);
            enqueue(item);
            printf("Stack: ");
            displayStack();
            printf("Queue: ");
            displayQueue();
            break;
        case 2:
            dequeue();
            printf("Stack: ");
            displayStack();
            printf("Queue: ");
            displayQueue();
            break;
        case 3:
            displayQueue();
            break;
        case 4:
            printf("Enter item to search:\n");
            scanf("%d", &item);
            searchQueue(item);
            printf("Stack: ");
            displayStack();
            printf("Queue: ");
            displayQueue();
            break;
        case 5:
            displayStack();
            break;
        case 6:
            printf("Enter item to search:\n");
            scanf("%d", &item);
            searchStack(item);
            printf("Stack: ");
            displayStack();
            printf("Queue: ");
            displayQueue();
            break;
        case 7:
            pop();
            printf("Stack: ");
            displayStack();
            printf("Queue: ");
            displayQueue();
            break;
        case 8:
            exitcode = 0;
            break;
        }
    }
    while(exitcode == 1);

    return 0;
}

UVA Problem 483 (Word Scramble) Solution

UVA Problem 483 (Word Scramble) Solution:


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

Solving Technique:

This problem asks us to reverse each words in a given sentence. There may be other better and faster solutions. I’ve implemented my solution using stack. First we are looking for space or null character. If those are not found we keep pushing characters in stack until we find space or null character. While doing that we also keep a count of number of items we pushed in the stack. So now if we find a space character or a null character we keep popping and printing the items the number of times pushed. We also check to see if we reached the last character in which case we don’t print any space character.

Important: We should not reverse the whole string but only each words. Also make sure there are no trailing space ( I got Presentation Error (PE) for this ) after the end of sentence. Also there should not be extra blank lines.


Critical Input:

I love you.
You love me.
We're a happy family.

Critical Output:

I evol .uoy
uoY evol .em
er'eW a yppah .ylimaf

Code:

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

#include<stdio.h>

int top = -1;
char st[1000], sentence[1000];

void push(char c){
    st[++top] = c;
}

void pop(){
    printf("%c", st[top]);
    st[top--] = '\0';
}

int main(){
    int c = 0;
    
    while (gets(sentence)){
        for (int i = 0; sentence[i]; ++i){
            if (sentence[i + 1] == '\0' || sentence[i] != ' '){
                push(sentence[i]);
                ++c;
            }
            if (sentence[i] == ' ' || sentence[i + 1] == '\0'){
                for (int j = 0; j < c; ++j){
                    pop();
                }
                c = 0;
                if(sentence[i + 1] != '\0'){
                    printf(" ");
                }
            }
        }
        printf("\n");
    }

    return 0;
}