(C) 자료구조 - 스택의 응용

1. 스택을 이용한 역순 문자열

스택의 LIFO 특성을 이용하여 역순 문자열을 간단히 만들 수 있다. 

 

1) 문자열을 순서대로 스택에 삽입한다.

 

 

 

 

 

 

 

 

2) 스택에서 삭제하여 문자열을 만든다.

 

 

 

 

 

 

 

 

---

2. 시스템 스택

프로그램에서 수행되는 함수 호출과 복귀 순서는 가장 나중에 호출된 함수가 먼저 실행을 완료하고 복귀하는 순서를 따른다. 이처럼 함수의 호출과 복귀 순서는 역순의 관계를 가지므로 스택의 LIFO 구조를 응용해 관리할 수 있다.

-> 이때 사용하는 스택을 시스템 스택이라 한다.

 

함수나 서브 프로그램 호출이 발생하면 호출된 함수의 작업으로 전환하기 위해 현재 작업 중인 지역 변수, 매개 변수 및 완료 후 복귀할 주소 등의 정보를 스택 프레임에 저장하여 시스템 스택에 삽입한다.

 

시스템 스택의 top은 현재 실행 중인 함수가 호출되었을 때, 이에 대한 작업 전환에 관한 정보가 들어 있는 스택 프레임이 된다. 함수 실행이 끝나면 시스템 스택의 top원소(스택 프레임)를 삭제하면서 프레임에 저장되어 있던 복귀 주소를 확인하고 복귀한다. 

 

함수 호출과 복귀에 따라 이 과정을 반복하여 전체 프로그램 수행이 종료되면 시스템 스택은 공백 스택이 된다.

 

<함수 호출과 복귀에 따른 전체 프로그램 수행 순서>

 

 

 

 

 

 

 

 

 

1) main() 함수 실행 시작 

main() 함수 시작과 관련된 정보를 스택 프레임에 저장하여 시스템 스택에 삽입한다.

 

2) F_1() 함수 호출

main() 함수 실행 중에 F_1() 함수 호출을 만나면 함수 호출과 복귀 등 작업을 전환하는 데 필요한 정보를 스택 프레임에 저장하여 시스템 스택에 삽입한다. 이때 스택 프레임에는 호출된 F_1() 함수의 수행이 끝나고 main() 함수로 복귀할 주소 a가 저장된다.

 

3) 호출된 F_1() 함수 실행

 

4) F_2() 함수 호출 

F_1() 함수를 실행하다가 F_2() 함수 호출을 만나면 함수 호출과 복귀 등 작업을 전환하는 데 필요한 정보를 새로운 스택 프레임에 저장하여 시스템 스택에 삽입한다. 이때 스택 프레임에는 F_1() 함수로 복귀할 주소 b가 저장된다.

 

5) 호출된 F_2() 함수 실행

 

6) F_2() 함수 실행 종료, F_1() 함수로 복귀

함수 실행이 끝나면 F_2() 함수를 호출했던 이전 위치로 복귀하여 이전 함수 F_1()의 작업을 계속해야 한다. 그러러면 이전 작업과 관련 있는 지역 변수, 매개변수 및 복귀 주소 등의 정보가 필요한데, 이런 정보는 시스템 스택에 있으므로 시스템 스택의 top에 있는 스택 프레임을 pop하여 정보를 확인하고 복귀 및 작업 전환을 실행한다.

 

7) F_1() 함수로 복귀하여 F_1() 함수의 나머지 부분 실행

 

8) F_1() 함수 실행 종료, main() 함수로 복귀

F_1() 함수 실행이 끝났으므로 F_1() 함수를 호출했던 main() 함수의 이전 위치로 복귀하여 실행을 계속해야 한다. 그러러면 복귀할 주소 등의 작업 전환 정보가 필요하다. 이런 정보는 시스템 스택에 있으므로 스택의 top에 있는 스택 프레임을 pop하여 정보를 확인하고 복귀 및 작업 전환을 실행한다.

 

9) main() 함수 실행 완료(전체 프로그램 실행 완료)

main() 함수로 복귀하여 나머지 부분을 실행하고 실행이 끝나면 다시 시스템 스택의 top에 있는 스택 프레임을 pop하여 복귀를 실행한다. 주 함수인 main() 함수는 호출한 상위 함수, 즉 복귀할 이전 함수의 주소를 가지고 있지 않으므로 전체 프로그램의 수행이 완료된다. 정상적인 함수 호출과 복귀가 모두 완료되었으므로 시스템 스택은 공백이 된다.

---

3. 스택을 이용한 수식의 괄호 검사

3-1. 수식의 괄호 쌍 검사

-> 수식을 읽으면서 왼쪽 괄호를 만나면 스택에 push하고, 오른쪽 괄호를 만나면 스택을 pop하여 검사한다.

// 수식의 괄호를 검사하는 연산
int testPair(char* exp) {
    char symbol, open_pair;
    // char형 포인터 매개변수로 받은 수식 exp의 길이를 계산하여 length 변수에 저장
    int i, length = strlen(exp);
    top = NULL;
 
    for (i = 0; i < length; i++) {
        symbol = exp[i];
        switch (symbol) {
            // (1) 왼쪽 괄호는 스택에 삽입
        case '(' :
        case '[' :
        case '{' :
            push(symbol); break;
            // (2) 오른쪽 괄호를 읽으면,
        case ')' :
        case ']' :
        case '}' :
            if (isStackEmpty()) return 0;
            else {
                // (2)-1 스택에서 마지막으로 읽은 괄호를 꺼냄
                open_pair = pop();
                // (2)-2 괄호 쌍이 맞는지 검사
                if ((open_pair == '(' && symbol != ')') ||
                    (open_pair == '[' && symbol != ']') ||
                    (open_pair == '{' && symbol != '}'))
                    // (2)-3 괄호 쌍이 틀리면 수식 오류
                    return 0;
                // (2)-4 괄호 쌍이 맞으면 다음 symbol 검사를 계속함
                else break;
            }
        }
    }
    if (top == NULL) return 1;        // 수식 검사를 마친 후 스택이 공백이면 1을 반환
    else return 0;
}

---

4. 스택을 이용한 수식의 후위 표기법 변환

1) 전위 표기법

연산자를 피연산자 앞에 표기하는 방법. ex) +AB

 

2) 중위 표기법 (주로 사용)

연산자를 피연산자의 가운데에 표기하는 방법. ex) A+B

 

- 중위 표기법의 수식을 전위 표기법으로 변환하는 예

1) 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현한다.

       ((A*B) - (C/D))

2) 각 연산자를 그에 대응하는 왼쪽 괄호의 앞으로 이동시킨다.

       -(*(A B) / (C D))

3) 괄호를 제거한다.

       -* A B / C D

 

- 중위 표기법 수식을 후위 표기법으로 변환하는 예

1) 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현한다.

    ((A*B) - (C/D))

2) 각 연산자를 그에 대응하는 오른쪽 괄호의 뒤로 이동시킨다.

    ((A B) * (C D) / ) -

3) 괄호를 제거한다.

    A B * C D/-

3) 후위 표기법 

연산자를 피연산자 뒤에 표기하는 방법. ex) AB++

-> 컴퓨터 내부에서 수식을 처리하는 데 가장 효율적인 방법

-> 괄호나 연산자 우선순위를 따로 처리하지 않고 왼쪽에서 오른쪽으로 표기된 순서대로 처리할 수 있다.

-> 컴퓨터에 중위 표기법 형태의 수식을 입력하면 컴퓨터 내부에서는 효율적인 처리를 위해 스택을 사용하여 입력된 수식을 후위 표기법으로 변환한다.

 

<컴퓨터 내부에서 중위 표기법을 후위 표기법으로 바꾸는 방법>

1. 왼쪽 괄호를 만나면 무시하고 다음 문자를 읽는다.

2. 피연산자를 만나면 출력한다.

3. 연산자를 만나면 스택에 삽입한다.

4. 오른쪽 괄호를 만나면 스택을 pop하여 출력한다.

5. 수식이 끝나면 스택이 공백이 될 때까지 pop하여 출력한다.

---

5. 스택을 이용한 후위 표기법 수식의 연산

<스택을 사용해 후위 표기법 수식을 계산하는 방식>

1) 피연산자를 만나면 스택에 push한다.

2) 연산자를 만나면 필요한 만큼의 피연산자를 스택에서 pop하여 연산하고, 연산 결과를 다시 스택에 push한다.

3) 수식이 끝나면 마지막으로 스택을 pop하여 출력한다.

 

- 수식을 후위 표기법으로 연산하기

5-1. 후위 표기법 수식을 계산하는 연산

// 후위 표기법 수식을 계산하는 연산
element evalPostfix(char* exp) {
    int opr1, opr2, value, i = 0;
    // char형 포인터 매개변수로 받은 수식 exp의 길이를 계산하여 length 변수에 저장
    int length = strlen(exp);
    char symbol;
 
    top = NULL;
 
    for (i = 0; i < length; i++) {
        symbol = exp[i];
        if (symbol != '+' && symbol != '-' && symbol != '*' && symbol != '/') { // 피연산자인 경우
            value = symbol - '0'; // int형 변수로 저장
            push(value);
        }
        else {
            opr2 = pop();
            opr1 = pop();
            // 변수 opr1과 opr2에 대해 symbol에 저장된 연산자를 연산
            switch (symbol) {
            case '+' : push(opr1 + opr2); break;
            case '-' : push(opr1 - opr2); break;
            case '*' : push(opr1 * opr2); break;
            case '/' : push(opr1 / opr2); break;
            }
        }
    }
    // 수식 exp에 대한 처리를 마친 후 스택에 남아있는 결과값을 pop하여 반환
    return pop();
}

 

5-2. 35*62/- 후위 표기법으로 연산