Programming Exercise: Lab #2

경희대학교 박제만 교수님의 자료구조 수업을 기반으로 정리한 글입니다.

Exercise #1

Problems

• Implement (1) BinarySearch(int item) and (2) BinarySearchNearest(int item).
• Assume that there are No duplicated elements in the list.

▶ (1) BinarySearch(int item) is the function we already learned in the class.

• The only difference is that "it returns the index of the item" if found
• Otherwise, it returns -1

template <class ItemType>
int SortedType<ItemType>::BinarySearch(ItemType item){
   
    int ret = -10;
    
    int first = 0;
    int mid;
    int last = length - 1;
    while (first <= last) {
        mid = (first + last) / 2;
        if (data[mid] < item) {
            first = mid + 1;
        }
        else if (data[mid] > item) {
            last = mid - 1;
        }
        else {
            return mid;
        }
    }
    
    ret = -1;
    
    return ret;
}

▶ BinarySearch()

▶ (2) BinarySearchSmallerNearest(int item) is similar to BinarySearch()

• It also returns "the index of the item" if found
• Otherwise, it returns the index of the item smaller than "item" and nearest to "item"
• If the list does not have elements smaller than "item", return -1

template <class ItemType>
int SortedType<ItemType>::BinarySearchNearestSmaller(ItemType item){

    int nearest = -10;
        
    int first = 0;
    int mid;
    int last = length - 1;
    while (first <= last) {
        mid = (first + last) / 2;
        if (data[mid] < item) {
            first = mid + 1;
        }
        else if (data[mid] > item) {
            last = mid - 1;
        }
        else {
            return mid;
        }
    }

    if (data[last] < item) {
        nearest = last;
    }
    else {
        nearest = -1;
    }
    
    return nearest;
}

▶ BinarySearchNearestSmaller() - v1

template <class ItemType>
int SortedType<ItemType>::BinarySearchNearestSmaller(ItemType item){
    int nearest = -1;
    
    if(item < data[0]){
        return -1;
    }
    
    int mid;
    int first = 0;
    int last = length - 1;
    while(first <= last){
        mid = (first + last) / 2;
        if (item == data[mid]){
            item = data[mid];
            return mid;
        }
        
        if (nearest == -1 || ((abs(data[nearest] - item) > abs(data[mid] - item)) && data[mid] < item)){
            nearest = mid;
        }
        
        if( item < data[mid]){
            last = mid - 1;
        }
        else if(item > data[mid]){
            first = mid + 1;
        }
    }
    
    return nearest;
}

▶ BinarySearchNearestSmaller() - v2 (solution)

• abs: 절대값 함수

Exercise #2

Problems

• Implement the client function, checkMaching(), that confirms if the given string has "Balanced Brackets".
• Balanced Brackets: the pairs and the orders of {, }, (, ), [, ] are correct in the given expression.

▶ return value

 

HINT: we can use "STACK" to solve this problem.

• Push into the STACK when the char is left-sided parenthesis(brackets, 괄호) ( or [ or {
• Pop from the STACK when the char is right-sided parenthesis ) or ] or } and check if the char and the item from STACK match

Ignore all non-parentheses chars (a, s, d, etc.)

End of string && Empty Stack -> return true

• [ }: Popped item [ and the char } NOT matches -> return false
• {([]): STACK is NOT EMPTY at the End of String { remains -> return false
• ({})]: It tries to pop from EMPTY STACK -> return false

bool checkMatching(char string[], int length) {
    StackType<char> tempStack;

    for (int i = 0; i < length; i++) {
        if (string[i] == '(' || string[i] == '[' || string[i] == '{') {
            tempStack.push(string[i]);

        }
        else if (string[i] == ')' || string[i] == ']' || string[i] == '}') {
            if (tempStack.isEmpty()) {
                return false;
            }
            char top = tempStack.pop();

            if ((string[i] == ')' && top != '(') ||
                (string[i] == ']' && top != '[') ||
                (string[i] == '}' && top != '{')) {
                    return false;
                }
        }
    }
    return tempStack.isEmpty();
}

▶ checkMatching() - v1

 

※ string[i] == ('(' || '[' || '{') 이런 식으로 작성하면 여러 문자를 비교하는 것이 아니라, || 연산으로 계산된 하나의 값과 비교하는 것이기 때문에 조건이 항상 참 또는 특정 값을 갖는다.

bool checkMatching(char string[], int length){
    StackType<char> tempStack;
    
    for (int i=0; i<length; i++){
        char ch = string[i];
        if(ch == '[' || ch == '(' || ch == '{'){
            tempStack.push(ch);
        }
        else if(ch == ']' || ch == ')' || ch == '}'){
            char popped = tempStack.pop();
            if((ch == ']' && popped != '[') || (ch == ')' && popped != '(') || (ch == '}' && popped != '{')){
                return false;
            }
        }
    }
    
    if(tempStack.isEmpty()){
        return true;
    }
    else{
        return false;
    }
}

▶ checkMatching() - v2 (solution)

 

Exercise #3

Problems

• Implement MazeExplorer() function that finds the path from "entry" to "exit" in the maze(미로).

▶ Maze is 2D char array.

• '1' means the wall
• '0' means the empty space
• location entry(1,0); / location exit(4,5);

mazeExplorer() uses STACK to maintatin the trace of traversal(여행).

• Print the visited coordinate(좌표).
• Start with "entry" push all adjacent(인접한) "empty space" into STACK.
• Pop from STACK and repeat.

Priority of visiting

• Upward -> rightward -> downward -> left ward
  • Pop을 할 때 실제로 방문을 하는 것이기에, STACK의 구조상, 역순으로 push해 주어야 한다.

Correct Outputs: path founds -> return true / EMPTY stack, NOT found -> return false

• [1][0]
• [1][1]
• [0][1]
• [2][1]
• [2][2]
• [2][3]
• [1][3]
• [1][4]
• [3][3]
• [4][3]
• [4][4]
• [4][5] 

mazeExplorer():

• Prints all visited points in order ([ ] [ ] format).
  • you can use printLocation() function to print.
• Returns true if there is a route from "entry" to "exit".
• Returns false if there is no route from "entry" to "exit".

bool mazeExplorer(char map[][MAZE_SIZE], location entryPoint, location exitPoint){
    StackType<location> tempStack;
    tempStack.push(entryPoint);
    
    map[entryPoint.row][entryPoint.col] = '.';

    while (!tempStack.isEmpty()) {
        location current = tempStack.pop();
        printLocation(current);

        if (current.row == exitPoint.row && current.col == exitPoint.col) {
            return true;
        }

        location directions[] = {
            {current.row, current.col - 1}, // 왼쪽으로 이동
            {current.row + 1, current.col}, // 아래로 이동
            {current.row, current.col + 1}, // 오른쪽으로 이동
            {current.row - 1, current.col}  // 위로 이동
        };

        for (location next : directions) {
            if (next.row >= 0 && next.row < MAZE_SIZE && next.col >= 0 && next.col < MAZE_SIZE
                && map[next.row][next.col] == '0') {
                tempStack.push(next);
                map[next.row][next.col] = '.';
            }
        }
    }
    return false;
}

▶ mazeExplorer() - v1

bool mazeExplorer(char map[][MAZE_SIZE], location entryPoint, location exitPoint){
    StackType<location> tempStack;
    tempStack.push(entryPoint);

    while(!tempStack.isEmpty()){
        location cur = tempStack.pop();
        int cur_row = cur.row;
        int cur_col = cur.col;
        
        printLocation(cur);
        map[cur_row][cur_col] = '.';
        
        if(cur_row == exitPoint.row && cur_col == exitPoint.col){
            return true;
        }
        else{
            if(map[cur_row][cur_col-1] == '0'){
                tempStack.push(location(cur_row, cur_col-1));
            }
            if(map[cur_row+1][cur_col] == '0'){
                tempStack.push(location(cur_row+1, cur_col));
            }
            if(map[cur_row][cur_col+1] == '0'){
                tempStack.push(location(cur_row, cur_col+1));
            }
            if(map[cur_row-1][cur_col] == '0'){
                tempStack.push(location(cur_row-1, cur_col));
            }
        }
    }

    return false;
}

▶ mazeExplorer() - v2 (solution)

 

※ DFS 문제