스카이라인 찾기

과목:	Programming Language
교수:	한상영
제출일:	29-Sep-97
제출자:	김기용, 93208-002, 지리학과

문제: 스카이라인 찾기

직사각형을 나타내는 tuple들을 파일로부터 입력으로 받아 skyline 만을 찾아내는 문제이다.
접근방식:
skyline 은 입력으로 사용되는 tuple 이 더해진 결과이다. 따라서, skyline 에 입력으로 들어오는 tuple 을 더함(+)으로써 새로운 skyline 을 얻는다. 이에 대한 pseudo-code는 다음과 같다.
```
while (tuple 이 존재하는 동안) {
    skyline += tuple;
}
	
```
SkyLine::operator+=
1. class SkyLine 은 output 의 형태인 점들의 list 로 구성한다. 이 list 는 x 를 기준으로 정렬되어 있다.
2. 새로운 tuple (x1, y, x2) 는 두 개의 점 (x1, y), (x2, 0) 으로 재구성되어 list 에 삽입되는데 (insert()),
3. 이때 x1 과 x2 사이에 있는 점 중에서 y 보다 낮은 높이를 가지는 점은 모두 y 의 높이로 끌어올려진다 (pullHeight()).
4. 이 과정이 끝나면 같은 높이를 가지는 점들이 연이어 존재할 가능성이 생기게 되어, 필요 없는 점은 통합해 버린다 (compact()).

Tuple

문자 하나가 입력으로 들어오면 tuple 에게 보낸다. 계속해서 보내다가 (AddChar()) 하나의 tuple 이 완성되어 사용할 수 있게 되면 (IsValid()) 그 tuple 을 사용한 뒤 초기화를 한다 (Clear()).

while ((ch = getchar()) != EOF) {
    tuple.AddChar(ch);
    if (tuple.IsValid()) {
        skyline += tuple;
        tuple.Clear();
    }
}

Exception Handling

프로그램 진행 중에 몇 가지 Exception 이 발생할 수 있는데, 여기서는 세 가지가 가능하다고 보았다. try-catch-throw 를 사용하였기 때문에, g++ 에서 -fhandle-exceptions 옵션을 켜야 한다.

ErrInvalidFormat : 입력이 잘못되었다. 이 프로그램에서는 [0-9\+\-\(\,\.\)] 가 아닌 문자는 모두 무시한 상태에서 scanf가 "(%f,%f,%f)" 를 format 으로 하여 읽기를 시도했을 때 3을 return하는(3개를 읽는) 것을 올바른 입력으로 간주하였다.
ErrTooLongTuple : 입력되는 Tuple 이 너무 길다. 이 프로그램에서 사용한 buffer 의 크기는 256 으로 #define 한 MAXCHAR 인데, tuple 하나가 MAXCHAR 를 넘게 되면 이 Exception 이 발생한다.
ErrNoSpace : skyline 에 새로운 tuple 을 더할 때 두 개의 점을 위한 Node 를 Allocation 받게 되는데, 이것이 만에하나 실패할 경우 발생한다.

Misc.

PrintDouble() : 좌표에 실수가 허용되도록 하라는 지시가 있었는데 요구된 출력에는 실수의 형태가 아니다. 따라서 소수점 뒤에 있는 0은 출력하지 않는 처리가 요구되었다.
Comments : 입력에서 # 을 만나면 newline 을 만날 때까지 입력을 무시하도록 하였다.
Debugging Tool : 입력과 출력을 각각 stdin 과 stdout 으로 했기 때문에 다양한 입력에 대해 올바른 결과를 보여 주는지 확인하기 위해 SkyLine.cpp 뿐 아니라 Win32 와 MFC 를 이용하여 시각적으로 보여 주는 프로그램을 작성하였다. 다음은 그 실행 예이다.

실행 예: #cat input2.txt (2.6,4.8,7.4)(7.5,7.0,9.3)(5.6,5.7,6.0)(2.1,5.1,2.4)(5.8,3.1,9.6) #a.out < input2.txt (2.1,5.1)(2.4,0)(2.6,4.8)(5.6,5.7)(6,4.8)(7.4,3.1)(7.5,7)(9.3,3.1)(9.6,0) #cat input.txt (1,5,3)(4,3,5)(2,7,6)(7,1,9) #a.out < input.txt (1,5)(2,7)(6,0)(7,1)(9,0) #cat errin1.txt (1,2,3)(1.2,3.2,3.4)(3,12345567,3.44444,4.0000000000002)(2.4.5) #a.out < errin1.txt Error: Invalid tuple input: (2.4.5) #cat errin2.txt (1.01234567890123456789<200자 생략>012345678901234567890123456789,1,2) #a.out < errin2.txt Error: Too long tuple input: (1.01234567890123456789<200자 생략>012345678901234567890123456789,; * ErrNoSpace 는 실험해 볼 수 없었다

Source Files

SkyLine.h

//
// SkyLine.h
//

#define MAXCHAR 256

#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))

// enum BOOL { FALSE, TRUE };
typedef int BOOL;

class CoordNode {
public:
    double x, y;
    CoordNode *next;

    CoordNode() { x = 0; y = 0; next = NULL; }
    CoordNode(double sx, double sy) { x = sx; y = sy; next = NULL; }
    void DeleteNextNode();
};

class Tuple {
protected:
    char   str[MAXCHAR];
    int    cur;
    BOOL   bValid;
    BOOL   bComment;

    BOOL   isUseful(char ch);
    void   verify();

public:
    double x1, y, x2;

    Tuple();

    BOOL   AddChar(char ch);

    BOOL   IsValid() { return bValid; }

    void   Clear() { cur = 0; bValid = FALSE; bComment = FALSE; }
    void   Print();
};

class SkyLine {
protected:

    CoordNode *insert(CoordNode *pNode);
    void compact();
    void pullHeight(Tuple &t);

public:
    CoordNode coordHead;

    SkyLine() {}
    ~SkyLine();

    SkyLine &operator +=(Tuple &t);
    void     Print();
};

class Exception {
public:
    enum ErrType {
        NoError, ErrNoSpace, ErrTooLongTuple, ErrInvalidFormat
    } err;

    void *param;

    Exception() { err = NoError; param = NULL; }
    Exception(ErrType etype, void *p) { err = etype; param = p; }
    BOOL Handle();
};

SkyLine.cpp

//
// SkyLine.cpp
//

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

#include "SkyLine.h"

void CoordNode::DeleteNextNode()
{
    CoordNode *pFree;

    pFree = next;
    if (!pFree)
        return;

    next = pFree->next;

    delete pFree;
}

Tuple::Tuple()
{
    x1  = 0;
    x2  = 0;
    y   = 0;

    cur = 0;
    bValid = FALSE;
    str[MAXCHAR-1] = '\0';

    bComment = FALSE;
}

BOOL Tuple::isUseful(char ch)
{
    if (!bComment && ch == '#') {
        bComment = TRUE;
        return FALSE;
    }

    if (bComment) {
        if (ch == '\n')
            bComment = FALSE;
        return FALSE;
    }

    if (isdigit(ch) || ch == '.' || ch == '+' || ch == '-')
        return TRUE;

    if (ch == '(' || ch == ',' || ch == ')')
        return TRUE;

    return FALSE;
}

void Tuple::verify()
{
    int nGet;

    nGet = sscanf(str, "(%lf,%lf,%lf)", &x1, &y, &x2);

    bValid = (nGet == 3) ? TRUE : FALSE;

    if (!bValid) {
        Exception e(Exception::ErrInvalidFormat, this);
        throw e;
    }
}


BOOL Tuple::AddChar(char ch)
{
    if (!isUseful(ch))
        return FALSE;

    str[cur++] = ch;

    if (ch == ')') {
        str[cur] = '\0';
        verify();
        return TRUE;
    }

    if (cur >= MAXCHAR - 2) {
        Exception e(Exception::ErrTooLongTuple, this);
        throw e;
    }

    return FALSE;
}

void Tuple::Print()
{
    str[cur] = '\0';
    printf("%s", str);
}

SkyLine::~SkyLine()
{
    while (coordHead.next) {
        coordHead.DeleteNextNode();
    }
}

SkyLine &SkyLine::operator +=(Tuple &t)
{
    CoordNode *pLeft, *pRight, *pPrev;

    pLeft = new CoordNode(t.x1, t.y);
    pRight = new CoordNode(t.x2, 0);

    if (!pLeft || !pRight) {
        Exception e(Exception::ErrNoSpace, NULL);
        throw e;
    }


    pPrev = insert(pRight);
    if (pRight->y < pPrev->y) {
        pRight->y = pPrev->y;
    }

    pPrev = insert(pLeft);
    if (pLeft->y < pPrev->y) {
        pLeft->y = pPrev->y;
    }

    pullHeight(t);
    compact();

    return *this;
}

CoordNode *SkyLine::insert(CoordNode *pNode)
{
    CoordNode *pPrev = &coordHead;

    while (pPrev->next) {
        if (pPrev->next->x >= pNode->x) {
            break;
        }
        pPrev = pPrev->next;
    }

    pNode->next = pPrev->next;
    pPrev->next = pNode;

    return pPrev;
}


void SkyLine::pullHeight(Tuple &t)
{
    CoordNode *pNode = coordHead.next;

    while (pNode) {
        if (pNode->x >= t.x2)
            return;
        if (pNode->x > t.x1 && pNode->y < t.y)
            pNode->y = t.y;

        pNode = pNode->next;
    }
}

void SkyLine::compact()
{
    CoordNode *pNode = coordHead.next;

    while (pNode) {
        if (!pNode->next)
            break;
        if (pNode->x == pNode->next->x) {
            pNode->y = max(pNode->y, pNode->next->y);
            pNode->DeleteNextNode();
            continue;
        }
        if (pNode->y == pNode->next->y) {
            pNode->x = min(pNode->x, pNode->next->x);
            pNode->DeleteNextNode();
            continue;
        }

        pNode = pNode->next;
    }
}

void PrintDouble(double num)
{
    static const int MAXDECIMAL = 6;

    if ((double)(int)num == num) {
        printf("%d", (int)num);
        return;
    }

    int    n;
    int    m;
    double mul;

    for (n = 1, m = 10; n < MAXDECIMAL; n++, m *= 10) {
        mul = num * m;
        if ((double)(int)mul == mul) {
            break;
        }
    }

    printf("%.*f", n, num);
}

void SkyLine::Print()
{
    CoordNode *pNode = coordHead.next;

    while (pNode) {
        putchar('(');
        PrintDouble(pNode->x);
        putchar(',');
        PrintDouble(pNode->y);
        putchar(')');
        pNode = pNode->next;
    }

    putchar('\n');
}

BOOL Exception::Handle()
{
    switch (err) {
    case ErrInvalidFormat:
        printf("%s", "Error: Invalid tuple input:\n");
        ((Tuple *)param)->Print();
        putchar('\n');
        return TRUE;

    case ErrTooLongTuple:
        printf("%s", "Error: Too long tuple input:\n");
        ((Tuple *)param)->Print();
        putchar('\n');
        return TRUE;

    case ErrNoSpace:
        printf("%s", "Error: Memory allocation failed.\n");
        return TRUE;

    default:
        return FALSE;
    }
}

int main(void)
{
    int     ch;
    Tuple   tuple;
    SkyLine skyline;

    while ((ch = getchar()) != EOF) {
        try {
            tuple.AddChar(ch);
            if (tuple.IsValid()) {
                skyline += tuple;
                tuple.Clear();
            }
        } catch (Exception e) {
            e.Handle();
            exit(1);
        }
    }

    skyline.Print();

    return 0;
}

스카이라인 찾기

문제: 스카이라인 찾기

접근방식:

`SkyLine::operator+=`

`Tuple`

Exception Handling

Misc.

실행 예

Source Files