ardalahmet.com

// ==================================================
// - File______: List.h _____________________________
// - Author____: Ahmet Ardal ________________________
// - Contact___: ardalahmet@hotmail.com _____________
// __________________________________________________
// - Copyright (c) 2009, Some Rights Reserved _______
// ==================================================

#ifndef LIST_H_
#define LIST_H_

/* type definitions */

struct Node
{
    void *pData;
    Node *pNext;
};

struct List
{
    Node *pHead;
    Node *pTail;
    int   size;
};

#define NodeNext(pNode)     (pNode)->pNext
#define NodeData(pNode)     (pNode)->pData

/* Function declarations */

List *ListCreate();

Node *ListPrepend(List *pList, const void *pData);

Node *ListAppend(List *pList, const void *pData);

void *ListDeleteHead(List *pList);

void *ListDeleteNth(List *pList, int idx);

Node *ListFindNode(List *pList, bool (*compare)(const void *, const void *), const void *pCmpData);

void *ListDeleteNode(List *pList, bool (*compare)(const void *, const void *), const void *pCmpData);

void  ListForeach(List *pList, void (*callback)(void *, void *), void *pCallbackData);

void  ListTruncate(List *pList);

int   ListGetSize(List *pList);

bool  ListIsEmpty(List *pList);

void  ListDestroy(List *pList);

#endif  /* LIST_H_ */

// ==================================================
// - File______: List.cpp ___________________________
// - Author____: Ahmet Ardal ________________________
// - Contact___: ardalahmet@hotmail.com _____________
// __________________________________________________
// - Copyright (c) 2009, Some Rights Reserved _______
// ==================================================

#include <cstdlib>
#include "List.h"

List *ListCreate()
{
    List *pList;

    pList = new List;

    pList->pHead = NULL;
    pList->pTail = NULL;
    pList->size  = 0;

    return pList;
}

Node *ListPrepend(List *pList, const void *pData)
{
    Node *pNode;

    pNode = new Node;
    pNode->pData = (void *) pData;
    pNode->pNext = pList->pHead;

    pList->pHead = pNode;

    if (pList->size == 0)
    {
        pList->pTail = pNode;
    }

    ++pList->size;

    return pNode;
}

Node *ListAppend(List *pList, const void *pData)
{
    Node *pNode;

    pNode = new Node;
    pNode->pData = (void *) pData;
    pNode->pNext = NULL;

    if (pList->size == 0)
    {
        pList->pHead = pNode;
    }
    else
    {
        pList->pTail->pNext = pNode;
    }

    pList->pTail = pNode;
    ++pList->size;

    return pNode;
}

void *ListDeleteHead(List *pList)
{
    Node *pNode;
    void *pData;

    if (pList->size == 0)
    {
        return NULL;
    }

    pNode = pList->pHead;
    pData = pNode->pData;
    pList->pHead = pNode->pNext;
    delete pNode;
    --pList->size;

    if (pList->size <= 1)
    {
        pList->pTail = pList->pHead;
    }

    return pData;
}

void *ListDeleteNth(List *pList, int idx)
{
    if ((idx < 0) || (idx >= pList->size))
    {
        return NULL;
    }

    if (idx == 0)
    {
        return ListDeleteHead(pList);
    }

    int i;
    void *pData;
    Node *pCur, *pPrev;

    for (
       pPrev = pList->pHead, pCur = pPrev->pNext, i = 1;
       pCur != NULL;
       pPrev = pCur, pCur = pCur->pNext, ++i
    )
    {
        if (i == idx)
        {
            pPrev->pNext = pCur->pNext;
            pData = pCur->pData;
            delete pCur;
            --pList->size;

            return pData;
        }
    }

    return NULL;
}

Node *ListFindNode(List *pList, bool (*compare)(const void *, const void *), const void *pCmpData)
{
    for (Node *pNode = pList->pHead; pNode != NULL; pNode = pNode->pNext)
    {
        if (compare(pNode->pData, pCmpData))
        {
            return pNode;
        }
    }

    return NULL;
}

void *ListDeleteNode(List *pList, bool (*compare)(const void *, const void *), const void *pCmpData)
{
    Node *pCur, *pPrev;
    void *pData;

    /* handle first item outside of the loop */
    if ((pPrev = pList->pHead) == NULL)
    {
        return NULL;
    }

    if (compare(pPrev->pData, pCmpData))
    {
        pList->pHead = pPrev->pNext;
        pData = pPrev->pData;
        delete pPrev;
        --pList->size;

        return pData;
    }

    /* first item is not what we are looking for, so traverse the entire list */
    for (
       pCur = pPrev->pNext;
       pCur != NULL;
       pPrev = pCur, pCur = pCur->pNext
    )
    {
        if (compare(pCur->pData, pCmpData))
        {
            pPrev->pNext = pCur->pNext;
            pData = pCur->pData;
            delete pCur;
            --pList->size;

            return pData;
        }
    }

    return NULL;
}

void  ListForeach(List *pList, void (*callback)(void *, void *), void *pCallbackData)
{
    for (Node *pNode = pList->pHead; pNode != NULL; pNode = pNode->pNext)
    {
        callback(pNode->pData, pCallbackData);
    }
}

void ListTruncate(List *pList)
{
    Node *pNode, *pNodeTmp;

    for (pNode = pList->pHead; pNode != NULL; pNode = pNodeTmp)
    {
        pNodeTmp = pNode->pNext;
        delete pNode;
    }

    pList->pHead = NULL;
    pList->pTail = NULL;
    pList->size = 0;
}

int ListGetSize(List *pList)
{
    return pList->size;
}

bool ListIsEmpty(List *pList)
{
    return (pList->size == 0);
}

void ListDestroy(List *pList)
{
    ListTruncate(pList);
    delete pList;
}

// ==================================================
// - File______: testList.cpp _______________________
// - Author____: Ahmet Ardal ________________________
// - Contact___: ardalahmet@hotmail.com _____________
// __________________________________________________
// - Copyright (c) 2009, Some Rights Reserved _______
// ==================================================

#include <iostream>
#include <cstring>
#include "List.h"

using namespace std;

// List data structure test code

struct Point
{
    int x;
    int y;
};

int main()
{
    const int N_POINTS = 7;

    // create a new linked list
    List *pListStrings = ListCreate();

    // append strings to the list
    ListAppend(pListStrings, "ankara");
    ListAppend(pListStrings, "istanbul");
    ListAppend(pListStrings, "izmir");

    // prepend strings to the list
    ListPrepend(pListStrings, "bilecik");
    ListPrepend(pListStrings, "yozgat");
    ListPrepend(pListStrings, "ordu");

    cout << "--- strings -----------------" << endl;
    // print list size
    cout << "list size: " << ListGetSize(pListStrings) << endl;
    // traverse the list and print all items
    for (Node *pNode = pListStrings->pHead; pNode != NULL; pNode = pNode->pNext)
    {
        cout << (const char *) pNode->pData << endl;
    }

    // destroy the list
    ListDestroy(pListStrings);

    // create a new linked list
    List *pListPoints = ListCreate();
    Point *pPoint;

    // create Points dynamically and insert them to the list
    for (int i = 0; i < N_POINTS; ++i)
    {
        pPoint = new Point;
        pPoint->x = i;
        pPoint->y = i * i;
        ListAppend(pListPoints, pPoint);
    }

    cout << "--- points ------------------" << endl;
    // print list size
    cout << "list size: " << ListGetSize(pListPoints) << endl;
    // traverse the list and print all items
    for (Node *pNode = pListPoints->pHead; pNode != NULL; pNode = pNode->pNext)
    {
        pPoint = (Point *) pNode->pData;
        cout << "x: " << pPoint->x << ", y: " << pPoint->y << endl;
    }

    // delete all dynamically allocated Point objects and destroy the list
    for (Node *pNode = pListPoints->pHead; pNode != NULL; pNode = pNode->pNext)
    {
        delete (Point *) pNode->pData;
    }
    ListDestroy(pListPoints);

    return 0;
}

// ==================================================
// - File______: testListAdvanced.cpp _______________
// - Author____: Ahmet Ardal ________________________
// - Contact___: ardalahmet@hotmail.com _____________
// __________________________________________________
// - Copyright (c) 2009, Some Rights Reserved _______
// ==================================================

#include <iostream>
#include <cstring>
#include "List.h"

using namespace std;

// List data structure advanced test code

struct Point
{
    int x;
    int y;
};

void filterNegativeGrades(void *pData, void *pCallbackData)
{
    Point *p = (Point *) pData;

    if ((p->x < 0) && (p->y < 0))
    {
        ListAppend((List *) pCallbackData, p);
    }
}

int main()
{
    const int N_POINTS = 12;

    // create a linked list
    List *pListPoints = ListCreate();
    Point *pPoint;

    // create Points dynamically and insert them to the list
    for (int i = 0; i < N_POINTS; ++i)
    {
        pPoint = new Point;
        pPoint->x = i - 8;
        pPoint->y = pPoint->x;
        ListAppend(pListPoints, pPoint);
    }

    // create a new linked list
    List *pListNegativePoints = ListCreate();

    // filter negative points and add them to the list pListNegativePoints
    ListForeach(pListPoints, filterNegativeGrades, pListNegativePoints);

    cout << "--- all points ------------------" << endl;
    // traverse the list and print all items
    for (Node *pNode = pListPoints->pHead; pNode != NULL; pNode = pNode->pNext)
    {
        pPoint = (Point *) pNode->pData;
        cout << "x: " << pPoint->x << ", y: " << pPoint->y << endl;
    }

    cout << "--- negative points -------------" << endl;
    // traverse the list and print all items
    for (Node *pNode = pListNegativePoints->pHead; pNode != NULL; pNode = pNode->pNext)
    {
        pPoint = (Point *) pNode->pData;
        cout << "x: " << pPoint->x << ", y: " << pPoint->y << endl;
    }

    // delete all dynamically allocated Point objects and destroy the list
    for (Node *pNode = pListPoints->pHead; pNode != NULL; pNode = pNode->pNext)
    {
        delete (Point *) pNode->pData;
    }

    ListDestroy(pListNegativePoints);
    ListDestroy(pListPoints);

    return 0;
}

// ==================================================
// - File______: testListAdvanced-2.cpp _____________
// - Author____: Ahmet Ardal ________________________
// - Contact___: ardalahmet@hotmail.com _____________
// __________________________________________________
// - Copyright (c) 2009, Some Rights Reserved _______
// ==================================================

#include <iostream>
#include "List.h"

using namespace std;

// List data structure advanced test code

struct Point
{
    int x;
    int y;
};

void printPoint(void *pData, void *pCallbackData)
{
    Point *p = (Point *) pData;

    cout << "x: " << p->x << ", y: " << p->y << endl;
}

void printString(void *pData, void *pCallbackData)
{
    cout << (const char *) pData << endl;
}

void deletePoint(void *pData, void *pCallbackData)
{
    delete (Point *) pData;
}

int main()
{
    const int N_POINTS = 12;

    // create a linked list for points
    List *pListPoints = ListCreate();
    Point *pPoint;

    // create Points dynamically and insert them to the list
    for (int i = 0; i < N_POINTS; ++i)
    {
        pPoint = new Point;
        pPoint->x = i - 8;
        pPoint->y = pPoint->x;
        ListAppend(pListPoints, pPoint);
    }

    // print points
    ListForeach(pListPoints, printPoint, NULL);
    cout << "--------------------------------" << endl;

    // delete all dynamically allocated Point objects
    /*for (Node *pNode = pListPoints->pHead; pNode != NULL; pNode = pNode->pNext)
    {
        delete (Point *) pNode->pData;
    }*/

    // delete all dynamically allocated Point objects using ListForeach
    ListForeach(pListPoints, deletePoint, NULL);

    ListDestroy(pListPoints);

    // -------------------------------------------------------
    // create a linked list for strings
    List *pListStrings = ListCreate();

    ListAppend(pListStrings, "adana");
    ListAppend(pListStrings, "ankara");
    ListAppend(pListStrings, "izmir");
    ListAppend(pListStrings, "bilecik");
    ListAppend(pListStrings, "istanbul");

    // print strings
    ListForeach(pListStrings, printString, NULL);
    cout << "--------------------------------" << endl;

    ListDestroy(pListStrings);

    return 0;
}

// ==================================================
// - File______: Stack.h ____________________________
// - Author____: Ahmet Ardal ________________________
// - Contact___: ardalahmet@hotmail.com _____________
// __________________________________________________
// - Copyright (c) 2009, Some Rights Reserved _______
// ==================================================

#ifndef STACK_H_
#define STACK_H_

#include "List.h"

struct Stack
{
    List *pList;
};

Stack *StackCreate();

Node *StackPush(Stack *pStack, const void *pData);

void *StackPop(Stack *pStack);

void *StackTop(Stack *pStack);

int StackGetSize(Stack *pStack);

bool StackIsEmpty(Stack *pStack);

void StackDestroy(Stack *pStack);

#endif  /* STACK_H_ */

// ==================================================
// - File______: Stack.cpp __________________________
// - Author____: Ahmet Ardal ________________________
// - Contact___: ardalahmet@hotmail.com _____________
// __________________________________________________
// - Copyright (c) 2009, Some Rights Reserved _______
// ==================================================

#include <cstdlib>
#include "Stack.h"

Stack *StackCreate()
{
    Stack *pStack = new Stack;

    pStack->pList = ListCreate();

    return pStack;
}

Node *StackPush(Stack *pStack, const void *pData)
{
    return ListPrepend(pStack->pList, pData);
}

void *StackPop(Stack *pStack)
{
    return ListDeleteHead(pStack->pList);
}

void *StackTop(Stack *pStack)
{
    if (ListIsEmpty(pStack->pList))
    {
        return NULL;
    }

    return pStack->pList->pHead->pData;
}

int StackGetSize(Stack *pStack)
{
    return ListGetSize(pStack->pList);
}

bool StackIsEmpty(Stack *pStack)
{
    return ListIsEmpty(pStack->pList);
}

void StackDestroy(Stack *pStack)
{
    ListDestroy(pStack->pList);
    delete pStack;
}

// ==================================================
// - File______: testStack.cpp ______________________
// - Author____: Ahmet Ardal ________________________
// - Contact___: ardalahmet@hotmail.com _____________
// __________________________________________________
// - Copyright (c) 2009, Some Rights Reserved _______
// ==================================================

#include <iostream>
#include "Stack.h"

using namespace std;

// ==================================================
// Stack data structure test code
int main()
{
    // create a new stack
    Stack *pStack = StackCreate();

    // push strings to the stack
    StackPush(pStack, "ankara");
    StackPush(pStack, "istanbul");
    StackPush(pStack, "izmir");
    StackPush(pStack, "yozgat");
    StackPush(pStack, "bilecik");

    // pop strings from the stack and print them
    const char *str;
    while ((str = (const char *) StackPop(pStack)) != NULL)
    {
        cout << str << endl;
    }

    // destroy the stack
    StackDestroy(pStack);

    return 0;
}

// ==================================================
// - File______: Queue.h ____________________________
// - Author____: Ahmet Ardal ________________________
// - Contact___: ardalahmet@hotmail.com _____________
// __________________________________________________
// - Copyright (c) 2009, Some Rights Reserved _______
// ==================================================

#ifndef QUEUE_H_
#define QUEUE_H_

#include "List.h"

struct Queue
{
    List *pList;
};

Queue *QueueCreate();

Node *QueueEnqueue(Queue *pQueue, const void *pData);

void *QueueDequeue(Queue *pQueue);

void *QueuePeek(Queue *pQueue);

int QueueGetSize(Queue *pQueue);

bool QueueIsEmpty(Queue *pQueue);

void QueueDestroy(Queue *pQueue);

#endif  /* QUEUE_H_ */

// ==================================================
// - File______: Queue.cpp __________________________
// - Author____: Ahmet Ardal ________________________
// - Contact___: ardalahmet@hotmail.com _____________
// __________________________________________________
// - Copyright (c) 2009, Some Rights Reserved _______
// ==================================================

#include <cstdlib>
#include "Queue.h"

Queue *QueueCreate()
{
    Queue *pQueue = new Queue;

    pQueue->pList = ListCreate();

    return pQueue;
}

Node *QueueEnqueue(Queue *pQueue, const void *pData)
{
    return ListAppend(pQueue->pList, pData);
}

void *QueueDequeue(Queue *pQueue)
{
    return ListDeleteHead(pQueue->pList);
}

void *QueuePeek(Queue *pQueue)
{
    if (ListIsEmpty(pQueue->pList))
    {
        return NULL;
    }

    return pQueue->pList->pHead->pData;
}

int QueueGetSize(Queue *pQueue)
{
    return ListGetSize(pQueue->pList);
}

bool QueueIsEmpty(Queue *pQueue)
{
    return ListIsEmpty(pQueue->pList);
}

void QueueDestroy(Queue *pQueue)
{
    ListDestroy(pQueue->pList);
    delete pQueue;
}

// ==================================================
// - File______: testQueue.cpp ______________________
// - Author____: Ahmet Ardal ________________________
// - Contact___: ardalahmet@hotmail.com _____________
// __________________________________________________
// - Copyright (c) 2009, Some Rights Reserved _______
// ==================================================

#include <iostream>
#include "Queue.h"

using namespace std;

// ===================================================
// Queue data structure test code
int main()
{
    Queue *pQueue = QueueCreate();

    QueueEnqueue(pQueue, "Ali");
    QueueEnqueue(pQueue, "Veli");
    QueueEnqueue(pQueue, "Hasan");
    QueueEnqueue(pQueue, "Cemil");

    const char *str;

    str = (const char *) QueuePeek(pQueue);
    cout << "peeked: " << str << endl;
    cout << "Queue size: " << QueueGetSize(pQueue) << endl;

    while ((str = (const char *) QueueDequeue(pQueue)) != NULL)
    {
        cout << str << endl;
    }

    QueueDestroy(pQueue);

    return 0;
}

// ==================================================
// - File______: ce242-spring09-hw3-q2-a.cpp ________
// - Author____: Ahmet Ardal ________________________
// - Contact___: ardalahmet@hotmail.com _____________
// __________________________________________________
// - Copyright (c) 2009, Some Rights Reserved _______
// ==================================================

#include <iostream>
#include "Stack.h"

using namespace std;

bool isParenthesesWellFormed(const char *str);

int main()
{
    char inputStr[256];

    cout << "Enter a string: ";
    cin.getline(inputStr, 256);

    if (isParenthesesWellFormed(inputStr))
    {
        cout << "parentheses are well-formed..." << endl;
    }
    else
    {
        cout << "parentheses are not well-formed..." << endl;
    }
    cout << endl;

    return 0;
}

bool isParenthesesWellFormed(const char *str)
{
    Stack *pStParenth = StackCreate();

    // iterate through the characters of str
    while (*str != '\0')
    {
        switch (*str)
        {
            // when an opening paranthesis is encountered, push it to the stack
            case '(':
            case '{':
            case '[':
                StackPush(pStParenth, str);
                break;

            // when a closing paranthesis is encountered,
            // pop a character from the stack and check it
            case ')':
            case '}':
            case ']':
            {
                const char *pc = (const char *) StackPop(pStParenth);
                if (pc == NULL)
                {
                    StackDestroy(pStParenth);
                    return false;
                }

                if ((*str == ')') && (*pc != '('))
                {
                    StackDestroy(pStParenth);
                    return false;
                }

                if ((*str == '}') && (*pc != '{'))
                {
                    StackDestroy(pStParenth);
                    return false;
                }

                if ((*str == ']') && (*pc != '['))
                {
                    StackDestroy(pStParenth);
                    return false;
                }
            }
                break;

            default:
                break;
        }

        // advance the pointer to the next character
        ++str;
    }   // while (*str != '\0')

    // check whether any closing parenthesis is missing
    if (!StackIsEmpty(pStParenth))
    {
        StackDestroy(pStParenth);
        return false;
    }

    // string is well-formed, return true
    StackDestroy(pStParenth);
    return true;
}

// ==================================================
// - File______: ce242-spring09-hw3-q2-b.cpp ________
// - Author____: Ahmet Ardal ________________________
// - Contact___: ardalahmet@hotmail.com _____________
// __________________________________________________
// - Copyright (c) 2009, Some Rights Reserved _______
// ==================================================

#include <iostream>
#include <cstring>
#include "Stack.h"

using namespace std;

bool isParenthesesWellFormed(const char *str);

int main()
{
    char inputStr[256];

    cout << "Enter a string: ";
    cin.getline(inputStr, 256);

    if (isParenthesesWellFormed(inputStr))
    {
        cout << "parentheses are well-formed..." << endl;
    }
    else
    {
        cout << "parentheses are not well-formed..." << endl;
    }
    cout << endl;

    return 0;
}

bool isParenthesesWellFormed(const char *str)
{
    const char opening[] = "({[";
    const char closing[] = ")}]";
    const char *pcFound;
    const char *pcPopped;

    Stack *pStParenth = StackCreate();

    // iterate through the characters of str
    while (*str != '\0')
    {
        if (strchr(opening, *str) != NULL)
        {
            StackPush(pStParenth, str);
        }
        else if ((pcFound = strchr(closing, *str)) != NULL)
        {
            if ((pcPopped = (const char *) StackPop(pStParenth)) == NULL)
            {
                StackDestroy(pStParenth);
                return false;
            }

            if (opening[pcFound - closing] != *pcPopped)
            {
                StackDestroy(pStParenth);
                return false;
            }
        }

        // advance the pointer to the next character
        ++str;
    }   // while (*str != '\0')

    // check whether any closing parenthesis is missing
    if (!StackIsEmpty(pStParenth))
    {
        StackDestroy(pStParenth);
        return false;
    }

    // string is well-formed, return true
    StackDestroy(pStParenth);
    return true;
}

// ==================================================
// - File______: ce242-spring09-hw3-q3.cpp ________
// - Author____: Ahmet Ardal ________________________
// - Contact___: ardalahmet@hotmail.com _____________
// __________________________________________________
// - Copyright (c) 2009, Some Rights Reserved _______
// ==================================================

#include <iostream>
#include "Stack.h"

using namespace std;

void printWordsReverse(char *str);

int main()
{
    char inputStr[256];

    cout << "Enter a string: ";
    //cin >> inputStr;
    cin.getline(inputStr, 256);
    /*cout << ":" << inputStr << ":" << endl;
    return 0;*/

    printWordsReverse(inputStr);
    cout << endl << endl;

    return 0;
}

void printWordsReverse(char *str)
{
    // create a Stack to store words in it
    Stack *pStWords = StackCreate();

    // push first word onto Stack
    StackPush(pStWords, str);

    // traverse the string,
    // separate words with null characters
    // and push more words onto Stack
    while (*str != '\0')
    {
        if (*str == ' ')
        {
            *str++ = '\0';
            StackPush(pStWords, str);
        }

        ++str;
    }

    // pop words from Stack and print them until the Stack becomes empty

    // first method
    const char *pWord;
    while ((pWord = (const char *) StackPop(pStWords)) != NULL)
    {
        cout << pWord << " ";
    }

    //// second method
    //for (
    //    const char *pWord = (const char *) StackPop(pStWords);
    //    pWord != NULL;
    //    pWord = (const char *) StackPop(pStWords)
    //)
    //{
    //    cout << pWord << " ";
    //}

    StackDestroy(pStWords);
}