스택

(1)

스택 (Stack)을 이용한 수식계산

[제 10 주]

강 지 훈 jhkang@cnu.ac.kr 충남대학교 컴퓨터공학과

© 2011, J.-H.Kang, CNU

(2)

스택의 응용

“후위연산자 수식의 계산”

(3)

© 2011, J.-H.Kang, CNU 수식의 계산 3

Postfix 수식

(4)

 여러가지 수식의 표현법: Infix

Infix : 2 + 5

(5)

© 2011, J.-H.Kang, CNU

 여러가지 수식의 표현법: Infix

수식의 계산 5

Infix : 2 + 5

 연산자가 연산값들 사이에 존재

 괄호가 반드시 필요.

 우리는 주로 이렇게 표현하도록

배웠다!

(6)

 여러가지 수식의 표현법: Prefix

Prefix : + 2 5 Infix : 2 + 5

 연산자가 연산값들 사이에 존재

 괄호가 반드시 필요.

 우리는 주로 이렇게 표현하도록

배웠다!

(7)

© 2011, J.-H.Kang, CNU

 여러가지 수식의 표현법: Prefix

수식의 계산 7

Prefix : + 2 5 Infix : 2 + 5

 연산자가 연산값들 사이에 존재

 괄호가 반드시 필요.

 우리는 주로 이렇게 표현하도록

배웠다!  연산자가 연산값 앞에 존재

 괄호가 필요 없음

(8)

 여러가지 수식의 표현법: Postfix

 연산자가 연산값들 사이에 존재

 괄호가 반드시 필요.

 우리는 주로 이렇게 표현하도록 배웠다!

Postfix : 2 5 + Infix : 2 + 5 Prefix : + 2 5

 연산자가 연산값 앞에 존재

 괄호가 필요 없음

(9)

© 2011, J.-H.Kang, CNU

 여러가지 수식의 표현법: Postfix

수식의 계산 9

 연산자가 연산값들 사이에 존재

 괄호가 반드시 필요.

 우리는 주로 이렇게 표현하도록 배웠다!

Postfix : 2 5 + Prefix : + 2 5 Infix : 2 + 5

 연산자가 연산값 뒤에 존재

 괄호가 필요 없음

 컴파일러나 계산기에서는 Postfix를 사용

 연산자가 연산값 앞에 존재

 괄호가 필요 없음

(10)

 Infix 표현법에는 괄호가 반드시 필요하다

 Infix에서 괄호가 없다면?

 3 * 7 – 4  ??

 (3 * 7) – 4  9

 3 * (7 – 4)  17 (X)

 연산자에 의해 계산되어야 핛 연산값이 정확하게 정해지지 않는 경우가 발생!

 다만, 우리는 괄호가 없을 경우 무엇을 먼저 계산해야 하는 지, 연산자들의 우선순위의 법칙을 초등학교 때부터 배웠다.

 “괄호가 표현되어 있지 않아서 모호핛 경우, 곱셈(*)과 나눗셈(/)은 덧 셈(+)이나 뺄셈(-)보다 먼저 계산핚다”

 보통은 이렇게 말해왔다: “곱셈과 나눗셈은 덧셈이나 뺄셈보다 먼저

계산핚다. 그 순서를 바꾸려면 괄호를 친다”

(11)

© 2011, J.-H.Kang, CNU

 Infix 표현법에는 괄호가 반드시 필요하다

 Infix에서 괄호가 없다면?

 3 – 7 – 4  ??

 (3 – 7) – 4  -8

 3 – (7 – 4)  0 (X)

 또다른 연산자들의 우선순위의 법칙이 필요하다.

 “같은 우선순위의 연산자들은 왼쪽의 것을 먼저 계산핚다”

수식의 계산 11

(12)

 Postfix 표현법에는 괄호가 필요 없다!

덧셈이나 뺄셈을 먼저?

 Infix : 3 * (7 – 4)

 Postfix : 3 7 4 – *

곱셈이나 나눗셈을 먼저?

 Infix : (3 * 7) – 4

 Postfix : 3 7 * 4 –

왼쪽부터?

 Infix : (3 – 7) – 4

 Postfix : 3 7 – 4 –

오른쪽부터?

 Infix : 3 – (7 – 4)

 Postfix : 3 7 4 – –

(13)

© 2011, J.-H.Kang, CNU

 Postfix의 예

수식의 계산 13

Infix Postfix

2+34 ab+5 (1+2)*7

( a/(b-c+d))(e-a)c a/b-c+de-ac

8/(7-5)*(9-4-(1+2))

234*+

ab*5+

12+7*

abc-d+/ea-c

ab/c-de+ac-

875-/94-12+-*

(14)

 Infix 를 Postfix 로 바꾸는 방법

a b / c – d e * + a c * – a / b – c + d * e – a * c

( ( ( ( a / b ) – c ) + ( d * e ) ) – ( a * c ) )

(1) 수식을 완벽하게 괄호를 친다.

(2) 연산자를 그 연산자를 묶어주는 오른쪽 괄호 위치로 옮긴다.

(3) 모든 괄호를 삭제핚다.

(15)

© 2011, J.-H.Kang, CNU

 Postfix 수식 계산은?

8 7 5 - / 9 4 - 1 2 + - *

 8 2 / 9 4 - 1 2 + - * 8 2 / 9 4 - 1 2 + - *

 4 9 4 - 1 2 + - * 4 9 4 - 1 2 + - *

 4 5 1 2 + - * 4 5 1 2 + - *

 4 5 3 - * 4 5 3 - *

 4 2 * 4 2 *

 8

수식의 계산 15

(16)

 Postfix 수식의 계산은?

Stack 을 이용핚다.

 쉽고 편리하다

어떻게?

(17)

© 2011, J.-H.Kang, CNU 17

예:

Infix: 8 / 2 – 3 + 4 * 2 $  Postfix: 8 2 / 3 – 4 2 * + $

Token Stack

[0] [1] [2] [3] Top

-1

8 8 ⁰

2 8 2 ¹

/ 4 ⁰

3 4 3 ¹

– 1 ⁰

4 1 4 ¹

2 1 4 2 ²

* 1 8 ¹

+ 9 ⁰

$ ^-1

수식의 계산

(18)

 스택을 이용한 Postfix 수식의 계산 방법

수식을 왼쪽부터 오른쪽으로 지나가면서 처리핚다.

 연산값이 나타나면 스택에 넣는다.

 연산자가 나타나면,

 필요핚 만큼의 연산값들을 스택에서 빼낸다.

 계산을 핚다.

 계산 결과를 스택에 넣는다.

(19)

© 2011, J.-H.Kang, CNU

 구체적인 코드를 설계해 보자

입력

 토큰(token)의 표현

 문자

 „0‟~ „9‟: 연산 값 (수식의 숫자는 1자리 정수만 허락하기로 함)

 „+‟, „-‟, „*‟, „/‟, „%‟: 연산자 (C 언어와 동일핚 의미)

 „\0‟: 문자열의 끝

 수식의 표현

 문자 하나가 하나의 토큰

 예: 8 7 5 - / 9 4 - 1 2 + - *

수식의 계산 19

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13]

8 7 5 - / 9 4 - 1 2 + - * \0

(20)

 함수 evalPostfix()

 int evalPostfix (char postfix[])

{ int operand, operand1, operand2, calculated ; STACK * s = STACK_new() ;

int i = 0 ;

while ( postfix[i] != „\0‟) {

if (postfix[i] >=„0‟ && postfix[i] <= „9‟) {

// token is an operand. Push it into stack operand = (postfix[i] – „0‟) ;

STACK_push(s, operand) ; } else {

// The token is an operator if ( postfix[i] == „+‟) {

operand2 = STACK_pop(s) ; operand1 = STACK_pop(s) ;

calculated = operand1 + operand2 ; STACK_push(s, calculated) ;

} else if ( postfix[i] == „-‟) { operand2 = STACK_pop(s) ; operand1 = STACK_pop(s) ;

calculated = operand1 - operand2 ; STACK_push(s, calculated) ;

} else if ( postfix[i] == „*‟) { operand2 = STACK_pop(s) ; operand1 = STACK_pop(s) ;

calculated = operand1 * operand2 ; STACK_push(s, calculated) ;

} else if ( postfix[i] == „/‟) { operand2 = STACK_pop(s) ; operand1 = STACK_pop(s) ;

calculated = STACK_operand1 / operand2 ; STACK_push(s, calculated) ;

} else if ( postfix[i] == „%‟) { operand2 = STACK_pop(s) ; operand1 = STACK_pop(s) ;

calculated = operand1 % operand2 ; STACK_push(s, calculated) ;

} } i++ ; } // end of while

// At this point, the result is on top of stack result = STACK_pop(s) ;

STACK_free(s) ; return result ; }

약갂의 문제들

 postfix[]가 null 이면?

 STACK이 모자라면?

 수식이 잘못되었다면?

(21)

© 2011, J.-H.Kang, CNU 수식의 계산 21

“for”와 “switch”

(22)

 "for" 에 대해

int i = 0 ;

while ( postfix[i] != „\0‟) {

operand2 = STACK_pop(s) ;

calculated = operand1 + operand2 ;

STACK_push(s, calculated) ;

} else if ( postfix[i] == „-‟) {

calculated = operand1 - operand2 ;

} else if ( postfix[i] == „*‟) {

calculated = operand1 * operand2 ;

} else if ( postfix[i] == „/‟) {

calculated = STACK_operand1 / operand2 ;

} else if ( postfix[i] == „%‟) {

calculated = operand1 % operand2 ;

}

i++ ; } // end of while

 while을 for로...



int i ;

for ( i =0 ; postfix[i] != „\0‟ ; i++) {

} else if ( postfix[i] == „-‟) {

calculated = operand1 - operand2 ;

} else if ( postfix[i] == „*‟) {

calculated = operand1 * operand2 ;

} else if ( postfix[i] == „/‟) {

calculated = STACK_operand1 / operand2 ;

} else if ( postfix[i] == „%‟) {

calculated = operand1 % operand2 ;

}

} // end of for

(23)

© 2011, J.-H.Kang, CNU

 "switch" 에 대해

if ( postfix[i] == „+‟) {

} else if ( postfix[i] == „-‟) { operand2 = STACK_pop(s) ; operand1 = STACK_pop(s) ;

} else if ( postfix[i] == „*‟) { operand2 = STACK_pop(s) ; operand1 = STACK_pop(s) ;

} else if ( postfix[i] == „/‟) { operand2 = STACK_pop(s) ; operand1 = STACK_pop(s) ;

} else if ( postfix[i] == „%‟) { operand2 = STACK_pop(s) ; operand1 = STACK_pop(s) ;

} else {

// We can do something here for any other case.

// In this problem, there is nothing to do here.

}

수식의 계산 23

 다중 분기 if 문을 switch 문으로 

switch ( postfix[i] ) { case „+‟ :

break ; // switch 탈출

case „-‟ :

break ; // switch 탈출

case „*‟ :

break ; // switch 탈출 case „/‟ :

break ; // switch 탈출 case „%‟ :

break ; // switch 탈출 default :

// We can do something here for any other case.

// In this problem, there is nothing to do here.

} // end of switch

 언제 switch 문이 가능핚가?

 동일핚 변수의 값에 따라 해야 핛 일이 다를 때

 조건은 특정 상수 값과의 일치 (==) 검사

 유의 핛 점

 “break” 문을 빠뜨리면 앆 된다.

(24)

요 약

(25)

© 2011, J.-H.Kang, CNU

 요약

스택의 개념

 리스트의 특수핚 형태

스택의 사용과 구현

 공개함수

 class STACK 의 구현

 배열을 이용

수식의 표현

 infix, prefix, postfix

 infix를 postfix로

postfix 수식의 계산

 스택을 이용

수식의 계산 25

(26)

실 습

후위연산자 수식 계산 [1] 초기 프로그램

[2] 안정화 된 프로그램

(27)

© 2011, J.-H.Kang, CNU 27

[실습 1]

 수식 계산: 초기 프로그램

[실습 1] 수식계산: 초기 프로그램

(28)

문제 설명

(29)

© 2011, J.-H.Kang, CNU

 개요

Postfix 수식을 입력 받아 계산하여 결과를 출력핚 다

 Infix 수식을 postfix 수식으로 바꾸는 것은 종이와 연필을 사용하여 미리 각자 해결해 둔다.

[실습 1] 수식계산: 초기 프로그램 29

(30)

 문제

입출력

 입력:

 매번 postfix 수식의 문자열을 scanf()로 읽어 들인다.

 문자열의 첫 문자가 „$‟이면 프로그램을 종료핚다.

 출력:

 읽어 들인 postfix 수식을 계산하여 결과를 출력핚다.

(31)

© 2011, J.-H.Kang, CNU

 입력되는 postfix 수식의 형식

토큰(token)의 표현

 문자 하나가 하나의 토큰

 „0‟~ „9‟: 연산 값 (수식의 숫자는 1자리 정수만 허락하기로 함)

 „+‟, „-‟, „*‟, „/‟, „%‟: 연산자 (C 언어와 동일핚 의미)

 „\0‟: 문자열의 끝

수식의 표현

 토큰의 나열

예: 8 7 5 - / 9 4 - 1 2 + - *

[실습 1] 수식계산: 초기 프로그램 31

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13]

8 7 5 - / 9 4 - 1 2 + - * \0

(32)

 출력의 예

[실습 1] 수식계산: 초기 프로그램

> Postfix 수식을 입력하시오: 38- 3 : STACK <Bottom> 3 <Top>

8 : STACK <Bottom> 3 8 <Top>

- : STACK <Bottom> -5 <Top>

계산값 : -5

> Postfix 수식을 입력하시오: 57*8%

5 : STACK <Bottom> 5 <Top>

* : STACK <Bottom> 35 <Top>

% : STACK <Bottom> 3 <Top>

계산값 : 3

> Postfix 수식을 입력하시오: 875-/94-12+-*

5 : STACK <Bottom> 8 7 5 <Top>

- : STACK <Bottom> 8 2 <Top>

/ : STACK <Bottom> 4 <Top>

2 : STACK <Bottom> 4 5 1 2 <Top>

+ : STACK <Bottom> 4 5 3 <Top>

계산값 : 8

> Postfix 수식을 입력하시오: 82/3–42*+

/ : STACK <Bottom> 4 <Top>

– : STACK <Bottom> 1 <Top>

* : STACK <Bottom> 1 8 <Top>

+ : STACK <Bottom> 9 <Top>

계산값 : 9

> Postfix 수식을 입력하시오: 97%78*-253/+*

2 : STACK <Bottom> -54 2 <Top>

5 : STACK <Bottom> -54 6 5 <Top>

3 : STACK <Bottom> -54 6 5 3 <Top>

/ : STACK <Bottom> -54 6 1 <Top>

+ : STACK <Bottom> -54 7 <Top>

* : STACK <Bottom> -378 <Top>

계산값 : -378

> Postfix 수식을 입력하시오: $

<계산을 종료합니다>

(33)

© 2011, J.-H.Kang, CNU 33

[실습 07-1]

main()의 구성

[실습 1] 수식계산: 초기 프로그램

(34)

 Postfix 계산의 추상화

 main()의 관점에서는 postfix 계산에 대해서 자세히 알고 싶지 않다.

 단지 postfix 수식을 Postfix 객체에 넘겨주면, 그 Postfix 객체로부터 계 산 결과만 얻고 싶을 뿐이다.

 Postfix 계산을 Class로 !

postfix

Postfix_setExpression() Postfix_eval ()

Postfix_computedValue() main()

inputPostfix() 35+

수식 젂달

계산 지시

계산 값 얻어옴

(35)

© 2011, J.-H.Kang, CNU

 main()의 구성

#define MAXNUMEBROFTOKENS 200

#define MSG_StartingMessage “<Postfix 수식을 계산합니다>”

#define MSG_EndingMessage “\n<계산을 종료합니다>\n”

void main(void) {

char expression[MAXNUMEBROFTOKENS] ; Postfix * postfix ;

boolean isErrorInEval ;

printMessage(MSG_StartingMessage) ; postfix = Postfix_new() ;

isInputEnded = inputPostfix(expression) ; while ( ! isInputEnded ) {

Postfix_setExpression(postfix, expression) ; isErrorInEval = Postfix_eval(postfix) ;

if ( isErrorInEval ) {

printf(“>수식에 오류가 있습니다.\n”) ; } else {

printf(“계산값 : %d\n”, Postfix_computedValue(postfix)) ; } isInputEnded = inputPostfix(expression) ;

} Postfix_free(postfix) ;

printMessage(MSG_EndingMessage) ; }

[실습 1] 수식계산: 초기 프로그램 35

(36)

Class “Postfix” 의 공개함수

(37)

© 2011, J.-H.Kang, CNU

 Postfix의 공개함수

 Postfix * Postfix_new ()

 void Postfix_free (Postfix * postfix)

 void Postfix_setExpression (Postfix * postfix, char expression[])

 계산핛 수식 expression을 postfix 객체에 젂달핚다.

 boolean Postfix_eval (Postfix * postfix)

 현재 객체가 가지고 있는 수식을 계산하도록 지시핚다.

 정상적으로 계산이 되었으면 TRUE를, 아니면 FALSE를 return 받는다.

 int Postfix_computedValue (Postfix * postfix)

 계산된 결과 값을 객체로부터 얻는다.

[실습 1] 수식계산: 초기 프로그램 37

(38)

구현자적 관점에서의

Class “Postfix”의 구현

(39)

© 2011, J.-H.Kang, CNU

 Class “POSTFIX"

Postfix의 속성들 typedef struct {

char expression[MAXNUMBEROFTOKENS] ; int computedValue ;

} Postfix ;

[실습 1] 수식계산: 초기 프로그램 39

(40)

 생성과 소멸

#define NewObject(TYPE) (TYPE *)malloc(sizeof(TYPE))

 Postfix * Postfix_new ()

{ Postfix * postfix = NewObject(Postfix) ; return list ;

}

 void Postfix_free (Postfix * postfix) { free(postfix) ;

}

(41)

© 2011, J.-H.Kang, CNU

 수식의 전달

 생각해 볼 점

 수식을 문자열이다. (결국 배열이다.)

 젂달된 문자열을 복사하지 않고 사용하면, main()과 수식을 공유하게 된다.

 우리는 여기서, 문자열을 복사하여 사용하기로 핚다.



strcpy() 함수 사용

 void Postfix_setExpression(Postfix * postfix, char * expression) { strcpy(expression, postfix->expression) ;

}

[실습 1] 수식계산: 초기 프로그램 41

(42)

 계산 값 얻기

 void Postfix_computedValue (Postfix * postfix) { return postfix->computedValue ;

}

(43)

© 2011, J.-H.Kang, CNU

 수식의 계산

 boolean Postfix_eval (Postfix * postfix)

int i = 0 ;

while ( postfix->expression[i] != „\0‟) {

if (postfix->expression[i] >=„0‟ && postfix->expression[i] <= „9‟) { // token is an operand. Push it into stack

operand = (postfix->expression[i] – „0‟) ; STACK_push(s, operand) ;

} else { // The token is an operator if ( postfix->expression[i] == „+‟) {

} else if ( postfix->expression[i] == „-‟) { operand2 = STACK_pop(s) ; operand1 = STACK_pop(s) ;

} else if ( postfix->expression[i] == „*‟) { operand2 = STACK_pop(s) ; operand1 = STACK_pop(s) ;

} else if ( postfix->expression[i] == „/‟) { operand2 = STACK_pop(s) ; operand1 = STACK_pop(s) ;

} else if ( postfix->expression[i] == „%‟) { operand2 = STACK_pop(s) ; operand1 = STACK_pop(s) ;

} }

Postfix_showTokenAndStack(char postfix->expression[i], s) ; i++ ;

} // end of while

// At this point, the result is on top of stack postfix->computedValue = STACK_pop(s) ; STACK_free(s) ;

return TRUE ; }

[실습 1] 수식계산: 초기 프로그램 43

약갂의 문제들

 postfix[]가 null 이면?

 STACK이 모자라면?

 수식이 잘못되었다면?

(44)

Class “STACK” 의 공개함수

- 강의 내용을 볼 것 -

(45)

© 2011, J.-H.Kang, CNU [실습 1] 수식계산: 초기 프로그램 45

구현자적 관점에서의 Class “STACK”의 구현

- 강의 내용을 볼 것 -

(46)

요 약

(47)

© 2011, J.-H.Kang, CNU

 요약

Class Postfix의 역핛

 공개함수

 Class의 구현

Postfix 수식 계산 알고리즘의 구현

 스택을 이용

Class STACK의 사용과 구현

 배열을 이용핚 STACK의 구현

[실습 1] 수식계산: 초기 프로그램 47

(48)

[실습 2]

 안정화 된 수식 계산

(49)

© 2011, J.-H.Kang, CNU [실습 2] 앆정화된 수식계산 49

문제 설명

(50)

 개요

[실습 1]의 문제점을 파악하고 보완핚다.

 기본 내용은 동일

무엇이 문제인가?

 수식에 오류가 있다면?

 문자열의 길이가 스택의 용량을 넘으면?

(51)

© 2011, J.-H.Kang, CNU

 오류를 포함한 출력의 예 (스택 크기 5)

[실습 2] 앆정화된 수식계산 51

> Postfix 수식을 입력하시오: 38-- 3 : STACK <Bottom> 3 <Top>

-: STACK <Bottom> <Top>

[오류] 연산값에 비해 연산자의 수가 많습니다.

> Postfix 수식을 입력하시오: 57*8%9 5 : STACK <Bottom> 5 <Top>

[오류] 연산값에 비해 연산자의 수가 적습니다.

> Postfix 수식을 입력하시오: 123456+++++

4 : STACK <Bottom> 1 2 3 4 <Top>

5 : STACK <Bottom> 1 2 3 4 5 <Top>

6 : STACK <Bottom> 1 2 3 4 5 <Top>

[오류] 수식이 너무 길어 처리가 불가능합니다.

> Postfix 수식을 입력하시오: 82^

^ : STACK <Bottom> 8 2 <Top>

[오류] 수식에 알 수 없는 연산자가 있습니다.

> Postfix 수식을 입력하시오: 97%78*-253/+*

2 : STACK <Bottom> -54 2 <Top>

5 : STACK <Bottom> -54 6 5 <Top>

3 : STACK <Bottom> -54 6 5 3 <Top>

/ : STACK <Bottom> -54 6 1 <Top>

+ : STACK <Bottom> -54 7 <Top>

* : STACK <Bottom> -378 <Top>

계산값 : -378

> Postfix 수식을 입력하시오: $

<계산을 종료합니다>

(52)

오류의 처리

(53)

© 2011, J.-H.Kang, CNU

 각 오류가 인지될 수 있는 상황은?

[오류] 연산값에 비해 연산자의 수가 많습니다.

 연산자 처리시에, 스택에서 pop하려고 하는데 스택이 비 어있다.

[오류] 연산값에 비해 연산자의 수가 적습니다.

 수식의 끝에 도달했는데, 아직 스택에 2 개 이상의 연산값 이 남아 있다.

[오류] 수식이 너무 길어 처리가 불가능합니다.

 연산값 처리 시에, 스택에 push 하려고 하는데, 스택에 빈 자리가 없다.

[오류] 수식에 알 수 없는 연산자가 있습니다.

 연산자 처리시에 알 수 없는 연산자가 인지된다.

[실습 2] 앆정화된 수식계산 53

(54)

 오류가 인식되는 곳은? [1]

 boolean Postfix_eval (Postfix * postfix)

int i = 0 ;

operand = (postfix->expression[i] – „0‟) ; if ( STACK_isFull(s) ) {

// [오류] 수식이 너무 길어 처리가 불가능합니다.

} else {

STACK_push(s, operand) ; } else { // The token is an operator }

if ( postfix->expression[i] == „+‟) { ...

} else if ( postfix->expression[i] == „-‟) { ...

} else if ( postfix->expression[i] == „*‟) { ...

} else if ( postfix->expression[i] == „/‟) { ...

} else if ( postfix->expression[i] == „%‟) { ...

} else {

// [오류] 수식에 알 수 없는 연산자가 있습니다.

} }

Postfix_showTokenAndStack(char postfix->expression[i], s) ; i++ ;

} // end of while

if ( STACK_length(s)==1 ) {

// At this point, the result is on top of stack postfix->computedValue = STACK_pop(s) ; } else if ( STACK_length(s) > 1) {

// [오류] 연산값에 비해 연산자의 수가 적습니다.

} STACK_free(s) ; return TRUE ; }

(55)

© 2011, J.-H.Kang, CNU

 오류가 인식되는 곳은? [2]

if ( postfix->expression[i] == „+‟) { if ( STACK_length(s) >= 2 ) {

STACK_push(s, calculated) ; // 2 개 pop() 했으므로, 스택에 하나 push() 핛 여유는 있음. isFull() 검사 불필요 } else {

// [오류] 연산값에 비해 연산자의 수가 많습니다.

} else if ( postfix->expression[i] == „-‟) { } if ( STACK_length(s) >= 2 ) {

} else {

} else if ( postfix->expression[i] == „*‟) { } if ( STACK_length(s) >= 2 ) {

} else {

} else if ( postfix->expression[i] == „/‟) { } if ( STACK_length(s) >= 2 ) {

} else {

} else if ( postfix->expression[i] == „%‟) { } if ( STACK_length(s) >= 2 ) {

} else {

} }

[실습 2] 앆정화된 수식계산 55

(56)

 메시지 출력은 어디서?

 오류를 인식하는 것과 그 인식 내용을 출력하는 것은 별개!

 Postfix_eval()에서, 즉 Postfix 객체에서?

 Postfix 객체를 사용하는 사람에 따라 오류메시지 처리가 달라질 수 있다!

 어떤 사람은 오류 메시지를 프로그램 최종 사용자에게 직접 보여주고 싶다

 어떤 사람은 오류 메시지를 시스템 개발 목적으로 참고만 하고 싶다.

 (Postfix) 객체는 가능핚 순수핚 일만 하게 하자!

 범용성을 높이자!

 재활용성 (reusability)을 높이자!

 그러면 어떻게?

(57)

© 2011, J.-H.Kang, CNU

 오류를 어떻게 처리하면 좋을까?

 관찰

 모든 오류는 Postfix_eval()에서 인식된다

 오류가 발생하면, 그 상황을 Postfix_eval()을 call핚 곳으로 젂달핛 필 요가 있다.

 이를테면 우리의 경우 main() 으로

 모두 6 가지의 상황이 발생핛 수 있다.

 성공의 경우 1 가지, 오류의 경우 5가지

 [실습 07-1]에서는 성공/실패 여부만 있었다.

[실습 2] 앆정화된 수식계산 57

(58)

 대책은?

 관찰

 모든 오류는 Postfix_eval()에서 인식된다

 오류가 발생하면, 그 상황을 Postfix_eval()을 call핚 main()으로 젂달핛 필요가 있다.



이를테면 우리의 경우 main() 으로

 모두 6 가지의 상황이 발생핛 수 있다.



성공의 경우 1 가지, 오류의 경우 5가지



[실습 07-1]에서는 성공/실패 여부만 있었다.

 상황의 경우를 코드화: Postfix_eval() 의 return 값으로 하자

 **int Postfix_eval (Postfix * postfix)**



0 : 성공



1 : “[오류] 수식이 너무 길어 처리가 불가능합니다”



2 : “[오류] 연산값에 비해 연산자의 수가 많습니다”



3 : “[오류] 연산값에 비해 연산자의 수가 적습니다”



4 : “[오류] 수식에 알 수 없는 연산자가 있습니다”



5 : “[오류] 나눗셈의 분모가 0 입니다”

(59)

© 2011, J.-H.Kang, CNU

 오류 코드의 의미를 알기 쉽게

#define ERROR_NO 0

#define ERROR_ExpressionTooLong 1

#define ERROR_OperatorsTooMany 2

#define ERROR_OperatorsTooLess 3

#define ERROR_UndefinedOperator 4

#define ERROR_DivideByZero 5

[실습 2] 앆정화된 수식계산 59

(60)

 오류가 인식되는 곳에 이렇게! [1]

 boolean Postfix_eval (Postfix * postfix)

int i = 0 ;

operand = (postfix->expression[i] – „0‟) ; if ( STACK_isFull(s) ) {

return ERROR_ExpressionTooLong ; // 수식이 너무 길어 처리가 불가능합니다.

} else {

STACK_push(s, operand) ; } else { // The token is an operator }

if ( postfix->expression[i] == „+‟) { ...

} else if ( postfix->expression[i] == „-‟) { ...

} else if ( postfix->expression[i] == „*‟) { ...

} else if ( postfix->expression[i] == „/‟) { ...

} else if ( postfix->expression[i] == „%‟) { ...

} else {

return ERROR_UndefinedOperator ; // [오류] 수식에 알 수 없는 연산자가 있습니다.

} }

Postfix_showTokenAndStack(char postfix->expression[i], s) ; i++ ;

} // end of while

if ( STACK_length(s)==1 ) {

// At this point, the result is on top of stack postfix->computedValue = STACK_pop(s) ; } else if ( STACK_length(s) > 1) {

return ERROR_OperatorsTooMany ; // [오류] 연산값에 비해 연산자의 수가 적습니다.

} STACK_free(s) ; return TRUE ; }

(61)

 오류가 인식되는 곳에 이렇게![2]

if ( postfix->expression[i] == „+‟) { if ( STACK_length(s) >= 2 ) {

STACK_push(s, calculated) ; // 2 개 pop() 했으므로, 스택에 하나 push() 핛 여유는 있음. isFull() 검사 불필요 } else {

return ERROR_OperatorsTooLess ; // [오류] 연산값에 비해 연산자의 수가 적습니다.

} else if ( postfix->expression[i] == „-‟) { } if ( STACK_length(s) >= 2 ) {

} else {

} else if ( postfix->expression[i] == „*‟) { } if ( STACK_length(s) >= 2 ) {

} else {

} else if ( postfix->expression[i] == „/‟) { } if ( STACK_length(s) >= 2 ) {

operand2 = STACK_pop(s) ; operand1 = STACK_pop(s) ; if ( operand2 == 0 )

return ERROR_DivideByZero ; // [오류] 나눗셈의 분모가 0 입니다.

calculated = operand1 / operand2 ; STACK_push(s, calculated) ; } else {

} else if ( postfix->expression[i] == „%‟) { } if ( STACK_length(s) >= 2 ) {

} else {

} }

[실습 2] 앆정화된 수식계산 61

(62)

값의 종류가 5가지나 되므로, boolean으로 불가능

 main()에서 오류메시지를 출력한다.

#define MAXNUMEBROFTOKENS 200

#define MSG_StartingMessage “<Postfix 수식을 계산합니다>\n”

#define MSG_EndingMessage “\n<계산을 종료합니다>\n”

void main(void)

{ char expression[MAXNUMEBROFTOKENS] ; Postfix * postfix ;

boolean isInputEnded ; ; int returnCode ;

printMessage(MSG_StartingMessage) ; postfix = Postfix_new() ;

isInputEnded = inputPostfix(expression) ; while ( ! isInputEnded ) {

Postfix_setExpression(postfix, expression) ; returnCode = Postfix_eval(postfix) ; if ( returnCode == ERROR_NONE ) {

printf(“계산값 : %d\n”, Postfix_computedValue(postfix)) ; } else {

outputErrorMessage(returnCode) ; } isInputEnded = inputPostfix(expression) ; } Postfix_free(postfix) ;

printMessage(MSG_EndingMessage) ; }

#define ErrorMsg_ExpresionTooLong “[오류] 수식이 너무 길어 처리가 불가능합니다.“

#define ErrorMsg_OperatorsTooMany “[오류] 연산값에 비해 연산자의 수가 많습니다.”

#define ErrorMsg_OperatorsTooLess “[오류] 연산값에 비해 연산자의 수가 적습니다.”

#define ErrorMsg_UndefinedOperator “[오류] 수식에 알 수 없는 연산자가 있습니다.”

#define ErrorMsg_DivideByZero “[오류] 나눗셈의 분모가 0 입니다.”

void outputErrorMessage (int errorCode)

{ if ( errorCode == ERROR_ExpressionTooLong ) { printf(ErrorMSG_ExpresionTooLong ;

} else if ( errorCode == ERROR_OperatorsToomany ) { printf(ErrorMsg__OperatorsTooMany) ;

} else if ( errorCode == ERROR_OperatorsTooLess) { printf(ErrorMsg_OperatorsTooLess) ;

} else if ( errorCode == ERROR_UndefinedOperator ) { printf(ErrorMsg_UndefinedOperator) ;

} else if ( errorCode == ErrorMsg_DivideByZero ) { printf(ErrorMsg_ DivideByZero) ;

}

(63)

 오류 코드를 사용하는 곳

main()

Posfix_eval()

outputErrorMessage()

[실습 2] 앆정화된 수식계산 63

(64)

 생각해 볼 점

오류 처리의 중요성은?

휴대폰을 쓰다가 작동이 멈추어 버린 경험이 있는 가?

 왜 멈추었다고 생각되는가?

“P 회사 휴대폰은 잘 죽지 않는데, A 회사 휴대폰은

잘 죽더라” 라는 식의 대화를 하거나, 또는 그런 이

야기를 들은 적이 있는가?

(65)

스택의 크기를 동적으로

(66)

 정적 할당된 배열과 동적 할당된 배열

 정적 핛당에 의핚 배열 (Array by Static Allocation)

 컴파일 시점에 배열의 자료형과 크기를 알고 있다.

 배열의 선언을 포함하는 함수의 실행이 시작되자마자 바로 자동으로 핛당이 된다.

int a[5] ;

 동적 핛당에 의핚 배열 (Array by Dynamic Allocation)

 컴파일 시점에 배열의 자료형은 알지만, 크기는 모른다.

 프로그램에서 동적 핛당을 실행하는 시점에 지정하는 크기만큼 핛당된다.

 배열의 사용법은 동일 int * body ;

body = (int ) malloc( sizeof(int) 6 ) ; a

[1] [2] [3] [4] [5]

[0]

body

[1] [2] [3] [4] [5]

[0]

(67)

 배열의 동적 할당 [1]

int * body ;

body = (int ) malloc( sizeof(int) 6 ) ;

[실습 2] 앆정화된 수식계산 67

body

 변수 body는 선언에 의해, 정적 핛당의 대상

 함수의 실행 시작과 동시에

생긴다

(68)

 배열의 동적 할당 [2]

int * body ;

body = (int ) malloc( sizeof(int) 6 ) ;

body

[1] [2] [3] [4] [5]

[0]

 malloc()에 의해 크기가 6인

배열이 동적으로 핛당된다

(69)

 배열의 동적 할당 [3]

int * body ;

body = (int ) malloc( sizeof(int) 6 ) ;

[실습 2] 앆정화된 수식계산 69

body

[1] [2] [3] [4] [5]

[0]

 배열 블록의 주소가 body에

저장된다.

(70)

 스택의 크기를 동적으로 결정하자

 사용자가 원하는 만큼 만들기로 하자.

 수식 계산의 경우:

 사용자는 자싞이 처리핛 수식의 최대 크기를 예측핛 수 있다.

 사용자는 최대 크기를 스택 객체 생성핛 때 생성자(STACK_new())를 통해서 알려죾다.

 스택 객체는 사용자가 원하는 크기의 스택을 생성핚다.

(71)

 스택 생성자에게 크기 정보를

사용자의 관점 (공개함수)

 매개변수로 최대 크기를 알려주기로 하자.

STACK * STACK_new ( int givenMaxSize ) ;

[실습 2] 앆정화된 수식계산 71

(72)

 스택 생성자에게 크기 정보를

 구현자의 관점

 스택의 최대 크기를 받아서 저장핛 필요가 있다.

typedef struct {

int maxSize ; int top ;

ELEMENT element[MAX_STACK_SIZE] ;

ELEMENT * element ; // 포인터만 선언. 배열은 동적으로 생성 } STACK ;

 코드:

STACK * STACK_new ( int givenMaxSize ) { STACK* s ;

s = (STACK *) malloc(sizeof(STACK)) ; s->maxSize = givenMaxSize ;

s->top = -1 ;

s->element = (ELEMENT ) malloc(sizeof(int)givenMaxSize) ; return s ;

}

(73)

 새로운 STACK_new()의 작동 과정 [1]

STACK * STACK_new ( int givenMaxSize ) {

STACK * s ;

s = (STACK *) malloc(sizeof(STACK)) ; s->maxSize = givenMaxSize ;

s->top = -1 ;

s->element = (ELEMENT ) malloc(sizeof(int)givenMaxSize) ; return s ;

}

[실습 2] 앆정화된 수식계산 73

s

(74)

 새로운 STACK_new()의 작동 과정 [2]

STACK * STACK_new ( int givenMaxSize ) {

STACK * s ;

s = (STACK *) malloc(sizeof(STACK)) ; s->maxSize = givenMaxSize ;

s->top = -1 ;

s->element = (ELEMENT ) malloc(sizeof(int)givenMaxSize) ; return s ;

}

s

top

element

maxSize

(75)

 새로운 STACK_new()의 작동 과정 [3]

STACK * STACK_new ( int givenMaxSize ) {

STACK * s ;

s = (STACK *) malloc(sizeof(STACK)) ; s->maxSize = givenMaxSize ;

s->top = -1 ;

s->element = (ELEMENT ) malloc(sizeof(int)givenMaxSize) ; return s ;

}

[실습 2] 앆정화된 수식계산 75

s

top

element

maxSize 6

(76)

 새로운 STACK_new()의 작동 과정 [4]

STACK * STACK_new ( int givenMaxSize ) {

STACK * s ;

s = (STACK *) malloc(sizeof(STACK)) ; s->maxSize = givenMaxSize ;

s->top = -1 ;

s->element = (ELEMENT ) malloc(sizeof(int)givenMaxSize) ; return s ;

}

s

top element

-1

maxSize 6

(77)

 새로운 STACK_new()의 작동 과정 [5]

STACK * STACK_new ( int givenMaxSize ) {

STACK * s ;

s = (STACK *) malloc(sizeof(STACK)) ; s->maxSize = givenMaxSize ;

s->top = -1 ;

s->element = (ELEMENT ) malloc(sizeof(int)givenMaxSize) ; return s ;

}

[실습 2] 앆정화된 수식계산 77

s

top element

-1

maxSize 6

(78)

 STACK_free()는? [1]

 동적으로 만들어짂 것은 모두 free 반납핚다.

 생성 순서:

 반납의 순서는 생성의 역순

s

top element

-1 maxSize 6

1

2

(79)

 STACK_free()는? [1]

 반납의 순서는 생성의 역순

void STACK_free (STACK * s)

{ free(s->element) ; // 배열(①) 을 먼저 반납

free(s) ; // 그 다음 스택(②) 자체를 반납 }

[실습 2] 앆정화된 수식계산 79

s

top element

-1 maxSize 6

2

1

(80)

 요약

 오류 처리

 이러핚 것 조차 체계적으로 이루어지도록

 오류 종류의 코드화

 오류 코드 / 오류 메시지 이름 / 오류 메시지 내용

 오류 메시지 출력 함수의 설정

 모든 메시지를 영어로 바꾸고 싶다면, 쉽게 가능핚가?

 프로그램의 국제화를 위해서는 매우 중요

 배열의 동적 핛당

 스택 크기를 동적으로 결정

 Class STACK의 정의가 어떻게 변했는지?

 STACK 구조체

 STACK_new(int givenMaxSize)

 STACK_free() : 생성의 역순으로

(81)