윤성우의열혈자료구조 : C 언어를이용한자료구조학습서 Chapter 06. 스택 (Stack) Introduction To Data Structures Using C
Chapter 06. 스택 (Stack) Chapter 06-1: 스택의이해와 ADT 정의 2
스택 (Stack) 의이해 스택은 먼저들어간것이나중에나오는자료구조 로서 초코볼이담겨있는통에비유할수있다. 스택은 LIFO(Last-in, First-out) 구조 의자료구조이다. 초코볼통에초코볼을넣는다. 초코볼통에서초코볼을꺼낸다. 이번에꺼낼초코볼의색이무엇인지통안을들여다본다. push pop peek 스택의기본연산 일반적인자료구조의학습에서스택의이해와구현은어렵지않다. 오히려활용의측면에 서생각할것들이많다! 3
스택의 ADT 정의 ADT 를대상으로배열기반의스택 또는연결리스트기반의스택을구현할수있다. PUSH 연산 POP 연산 PEEK 연산 4
Chapter 06. 스택 (Stack) Chapter 06-2: 스택의배열기반구현 5
구현의논리 두번의 PUSH 연산 인덱스가 0 인위치를스택의바닥으로 정의해야배열길이에상관없이바닥 의인덱스값이동일해진다. 인덱스 0 의배열요소가 ' 스택의바닥 ( 초코볼통의바닥 )' 으로정의되었다. 마지막에저장된데이터의위치를기억해야한다. push pop Top 을위로한칸올리고, Top 이가리키는위치에데이터저장 Top 이가리키는데이터를반환하고, Top 을아래로한칸내림 6
스택의헤더파일 배열기반을고려하여정의된스택의구조체! 7
배열기반스택의구현 : 초기화및기타함수 -1 은스택이비었음을의미 빈경우 TRUE 를반환 8
배열기반스택의구현 : PUSH, POP, PEEK 9
배열기반스택의활용 : main 함수 실행결과 10
Chapter 06. 스택 (Stack) Chapter 06-3: 스택의연결리스트기반구현 11
연결리스트기반스택의논리와헤더파일의정의 이렇듯메모리구조만보아서는스택임이구분되지않는다! 저장된순서의역순으로데이터 ( 노드 ) 를참조 ( 삭제 ) 하는연결리스트가바로연결기반의스택이다! 문제 06-1 에서는 CLinkedList.h 와 CLinkedList.c 를 단순히활용하여스택의구현을요구한다! 12
연결리스트기반스택의구현 1 새노드를머리에추가하고, 삭제시머리부 터삭제하는단순연결리스트의코드에지 나지않는다. 13
연결리스트기반스택의구현 2 연결리스트기반스택을직접구현하는것보다 의미있는것은문제 06-1 을해결하는것이다! 14
연결기반스택의활용 : main 함수 배열기반리스트관련 main 함수와완전히동일하게 정의된 main 함수! 실행결과 15
Chapter 06. 스택 (Stack) Chapter 06-4: 계산기프로그램구현 16
구현할계산기프로그램의성격 다음과같은문장의수식을계산할수있어야한다. ( 3 + 4 ) * ( 5 / 2 ) + ( 7 + ( 9 5 ) ) 다음과같은문장의수식계산을위해서는다음두가지를고려해야한다. 소괄호를파악하여그부분을먼저연산한다. 연산자의우선순위를근거로연산의순위를결정한다. 계산기구현에필요한알고리즘은스택과는별개의것이다. 다만그알고리즘의구현에있어서스택이매우요긴하게활용된다. 17
세가지수식의표기법 : 전위, 중위, 후위 중위표기법 (infix notation) 예 ) 5 + 2 / 7 수식내에연산의순서에대한정보가담겨있지않다. 그래서소괄호와연산자의우선 순위라는것을정의하여이를기반으로연산의순서를명시한다. 전위표기법 (prefix notation) 예 ) + 5 / 2 7 수식내에연산의순서에대한정보가담겨있다. 그래서소괄호가필요없고연산의 우선순위를결정할필요도없다. 후위표기법 (postfix notation) 예 ) 5 2 7 / + 전위표기법과마찬가지로수식내에연산의순서에대한정보가담겨있다. 그래서소 괄호가필요없고연산의우선순위를결정할필요도없다. 18 소괄호와연산자의우선순위를인식하게하여중위표기법의수식을직접계산하게프로그래밍 하는것보다후위표기법의수식을계산하도록프로그래밍하는것이더쉽다!
중위 후위 : 소괄호고려하지않고 1 수식을이루는왼쪽문자부터시작해서하나씩처리해나간다. 피연산자를만나면무조건변환된수식이위치할자리로이동시킨다. 19
중위 후위 : 소괄호고려하지않고 2 연산자를만나면무조건쟁반으로이동한다. 숫자를만났으니변환된수식이위치할자리로이동! 20
중위 후위 : 소괄호고려하지않고 3 / 연산자의우선순위가높으므로 + 연산자위에올린다. 쟁반에기존연산자가있는상황에서의행동방식! 쟁반에위치한연산자의우선순위가높다면 쟁반에위치한연산자를꺼내서변환된수식이위치할자리로옮긴다. 그리고새연산자는쟁반으로옮긴다. 쟁반에위치한연산자의우선순위가낮다면 쟁반에위치한연산자의위에새연산자를쌓는다. 우선순위가높은연산자는우선순위가낮은 연산자위에올라서서, 우선순위가낮은연산 자가먼저자리를잡지못하게하려는목적! 21
중위 후위 : 소괄호고려하지않고 4 피연산자는무조건변환된수식의자리로이동! 나머지연산자들은쟁반에서차례로옮긴다! 22
중위 후위 : 정리하면 변환규칙의정리내용 피연산자는그냥옮긴다. 연산자는쟁반으로옮긴다. 연산자가쟁반에있다면우선순위를비교하여처리방법을결정한다. 마지막까지쟁반에남아있는연산자들은하나씩꺼내서옮긴다. 23
중위 후위 : 고민될수있는상황 상황 1 + 연산자가우선순위가높다고가정하고 (+ 연산자가먼저등장했으므로 ) 일을진행한다. 즉 + 연산자를옮기고그자리에 연산자를가져다놔야한다. 상황 2 24
중위 후위 : 소괄호고려 1 후위표기법의수식에서는먼저연산이이뤄져야하는연산자가뒤에연산이이뤄지는연산자보다앞에위치해야한다. 따라서소괄호안에있는연산자들이후위표기법의수식에서앞부분에위치해야한다. ( 연산자의우선순위는그어떤사칙연산자들보다낮다고간주! 그래서 ) 연산자가등장할때까지쟁반에남아소괄호의경계역할을해야함! 25
중위 후위 : 소괄호고려 2 26 ) 연산자를만나면쟁반에서 ( 연산자만날때까지연 산자를변환된수식의자리로옮긴다!
중위 후위 : 소괄호고려 3 조금달리설명하면 ( 연산자는쟁반의또다른바닥이다! 그리고 ) 연산자는변환이되어야하는 작은수식의끝을의미한다. 그래서 ) 연산자를만나면 ( 연산자를만날때까지연산자를이동시 켜야한다. 지금까지설명한내용에해당하는코드의구현에앞서중위표기법의수식을후위표기 법의수식으로바꾸는연습을할필요가있다. 27
추가주의사항 책에서 ( 은어떤연산자보다도우순순위가낮다고설명하고있다. 오해의소지가있음. 이미다른연산자가쟁반위에있어도 ( 는무조건그위에쌓는다. 예 3-(2+8) 328+- ((3-2)/4) 32-4/ ((4+2)/4)-(3+2/(7*5))? 28
중위 후위 : 프로그램구현 1 변환함수의타입 함수이름의일부인 RPN 은후위표기법의또다른이름인 Reverse Polish Notation 의약자이다. 중위표기법수식을배열에담아함수의인자로전달한다. 호출완료후 exp 에는변환된수식이담긴다. 29
중위 후위 : 프로그램구현 2 함수 ConvToRPNExp 의첫번째 helper function! 연산자의우선순위에대응하는값을반환한다. 값이클수록우선순위가 높은것으로정의되어있다. ( 연산자는 ) 연산자가등장할때까지쟁반에남아있어야하기때문에가 장낮은우선순위를부여! ) 연산자는소괄호의끝을알리는메시지의역할을한다. 따라서쟁반으로가지않는다. 때문에 ) 연산자에대한반환값은정의되어있을필요가없다! 30
중위 후위 : 프로그램구현 3 함수 ConvToRPNExp 의두번째 helper function! 두연산자의우선순위비교결과를반환한다. ConvToRPNExp 함수의실질적인 Helper Function 은위의함수하나이다! 31
중위 후위 : 프로그램구현 4 void ConvToRPNExp(char exp[]) { Stack stack; int explen = strlen(exp); char * convexp = (char*)malloc(explen+1); 문자열 exp 의길이를반환함. 변환된수식을담을공간마련 int i, idx=0; char tok, popop; 새로운문자열을저장할공간을마련함. NULL 문자를추가하기위해 +1 함. memset(convexp, 0, sizeof(char)*explen+1); StackInit(&stack); 마련한공간을 0 으로초기화 for(i=0; i<explen; i++) {.... } 일련의변환과정을이반복문안에서수행 while(!sisempty(&stack)) convexp[idx++] = SPop(&stack); 스택에남아있는모든연산자를이동시키는반복문 } 32 strcpy(exp, convexp); free(convexp); 변환된수식을반환!
중위 후위 : 프로그램구현 5 void ConvToRPNExp(char exp[]) {.... for(i=0; i<explen; i++) { tok = exp[i]; } 33 } if(isdigit(tok)) tok에저장된문자가피연산자라면 { convexp[idx++] = tok; } else tok에저장된문자가연산자라면 { switch(tok) {.... 연산자일때의처리루틴을 switch문에담는다! } }
중위 후위 : 프로그램구현 6 함수 ConvToRPNExp 의일부인 switch 문 tok 에저장된연산자를스택에저장하기위한과정 스택맨위의연산자가 tok 보다우선순위가높거나같다면 34
중위 후위 : 프로그램의실행 ConvToRPNExp 함수의선언과정의 스택관련함수의선언과정의 main 함수의정의 실행결과 35
후기표기법수식의계산 피연산자두개가연산자앞에항상위치하는구조 후위표기법수식으로 후위표기법수식으로 1 과 2 의곱진행 2 와 4 의곱진행 2 와 3 의합진행 36
후기표기법수식계산프로그램의구현 계산의규칙 피연산자는무조건스택으로옮긴다. 연산자를만나면스택에서두개의피연산자를꺼내서계산을한다. 계산결과는다시스택에넣는다. 37
후기표기법수식계산프로그램의구현 이어서 숫자라면 연산자였다면 38 문자를숫자로변환 주의! 먼저꺼낸것이 op2 이고, 나중에꺼낸것이 op1 임. 마지막엔하나의값만남게되고, 그값을 pop 함.
후위표기법수식계산프로그램의실행 EvalRPNExp 함수의선언과정의 스택관련함수의선언과정의 main 함수의정의 실행결과 39
계산기프로그램의완성 1 계산의과정 중위표기법수식 ConvToRPNExp EvalRPNExp 연산결과 계산기프로그램의파일구성 InfixCalculator.h InfixCalculator.c 40
계산기프로그램의완성 2 InfixCalculator.h InfixCalculatorMain.c 실행결과 InfixCalculator.c 41
수고하셨습니다 ~ Chapter 06 에대한강의를마칩니다! 42