UVA Problem 11988 – Broken Keyboard (a.k.a. Beiju Text) Solution

UVA Problem 11988 – Broken Keyboard (a.k.a. Beiju Text) Solution:


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

Solving Technique:

The input may be classified into three things. One is append to beginning represented with ‘[‘, another is append to end represented with ‘]’ and the other types any other character except above mentioned. The other character are appended to the next position of last inserted character.

So task is move all characters following ‘[‘ to beginning until ‘]’ is found or end of string is reached. Similar logic applies to ‘]’ character. Also it is a recursive definition, keep applying this logic for all the following third brackets.


Other ideas:

Some other ideas to solve this problem can be, formatting the input to remove useless brackets then create a tree from inputs and perform in-order traversal to get the result. Another idea is create a linked list of strings.


Code Explanation:

I may later ( takes quite bit of time to create graphics ) provide a graphical representation of inserting in the doubly linked list ( 2nd code ). Meanwhile I provided a commented version ( 2nd code ) to make it a little easier to understand.

Here I have provided two codes. Both are linked list implementations. First one is singly linked list with no tail pointer( rather inefficient although I try to reduce some complexity by Boolean flag checking to reduce traversing the list to find tail pointer ). It is not able to keep track of tail pointer efficiently. Need to do some traversing ( some times almost the whole linked list ) to find the tail pointer.

The second implementation is doubly linked list with tail node as the tail pointer. The tail pointer has character has 0 which is ASCII decimal code for NULL character. I use this to stop printing otherwise a space character is printed at the end of output.

 

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. Please compile with c++ compiler as some of my codes are in c and some in c++.


More Inputs of This Problem on uDebug.


Input:

This_is_a_[Beiju]_text
[[]][][]Happy_Birthday_to_Tsinghua_University

 


Output:

BeijuThis_is_a__text
Happy_Birthday_to_Tsinghua_University

Code Singly Linked list Without Tail:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 11988 - broken keyboard
 * Technique: Singly Linked List with no
 *            tail Pointer(slow).
 */

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


#define N 100000

static char input[N];


struct vertex{
    char c;
    struct vertex* next;
};

typedef struct vertex node;


node* insertNode(node* n, char c){

    node* temp = new node();
    temp->c = c;
    temp->next = n->next;
    n->next = temp;

    return temp;
}


void printList( node* dummy ){

    node* tmp = dummy;

    while( tmp = tmp->next )
        putchar( tmp->c );

    printf("\n");
}


int main(){

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);


    while( gets(input) ){

        node* dummy = new node();
        dummy->next = NULL;
        node* cur = dummy;


        node* tail = dummy;

        bool rightopen = false;

        for(int i = 0; input[i]; ++i){

            if( input[i] == '[' ){
                cur = dummy;
                rightopen = true;
                continue;
            }
            if( input[i] == ']' ){
                rightopen = false;

                node *tmp = tail;

                while( tmp->next != NULL )
                    tmp = tmp->next;

                tail = cur = tmp;
                continue;
            }

            cur = insertNode(cur, input[i] );
            if( !rightopen )
                tail = cur;
        }

        printList( dummy );

    }


    return 0;
}

Code Doubly Linked list With Tail Pointer:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 11988 - broken keyboard
 * Technique: Doubly Linked List with
 *            dummy tail node as Pointer.
 */

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


#define N 100000


static char input[N];



// Doubly linked list.
struct vertex{
    char c;
    struct vertex* next;
    struct vertex* prev;
};
typedef struct vertex node;



node* insertNode(node* n, char c){

    // Create the new node to hold current character.
    node* temp = new node();
    temp->c = c;


    // Create forward connection from this created node
    // to the next node of passed in node (n).
    // Also create backward connection from the passed
    // in node to current node.
    temp->next = n->next;
    n->next->prev = temp;


    // Create forward connection from passed in node (n) to the
    // newly created node (temp).
    // Also create backward connection from created node to the
    // passed in node.
    n->next = temp;
    temp->prev = n;


    // return the pointer to the current node.
    return temp;
}



void printList( node* dummy ){

    // Dummy (head) is not a part of output.
    node* tmp = dummy->next;


    // Since I use tail pointer, check if its tail.
    while( tmp->c ){
        putchar( tmp->c );
        tmp = tmp->next;
    }

    printf("\n");
}



int main(){

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);


    while( gets(input) ){

        // Dummy node is just to keep track of beginning.
        // It does not contain any input character.
        // Tail is used to insert before the last node.
        // Tail is also another dummy node keeps track of
        // the end.
        node* dummy = new node();
        node* tail = new node();


        // NULL may not be necessary since I use tail character
        // checking to stop printing.
        tail->prev = dummy;
        dummy->next = tail;
        tail->next = NULL;
        dummy->prev = NULL;


        // Set current node to dummy (beginning). Set tail
        // to NULL character equivalent ASCII value.
        node* cur = dummy;
        tail->c = 0;


        for(int i = 0; input[i]; ++i){

            // Update node pointer to beginning based on bracket.
            // If not bracket use previous pointer location.
            if( input[i] == '[' ){
                cur = dummy;
                continue;
            }
            if( input[i] == ']' ){
                cur = tail->prev;
                continue;
            }

            cur = insertNode(cur, input[i] );
        }


        // Print output characters one by one.
        printList( dummy );

    }


    return 0;
}