제 5 강의. 스택과큐의응용 학습목차 1. 후위표기법 2. 스택을이용한후위표기법변환 3. 스택을이용한후위표기법의계산 1
1. 후위표기법 ( 정의 ) 후위표기법 (postfix notation) : 후위표기법은연산자를피연산자의뒤에놓는방법이다. 스택의응용의예이며수식의계산은계산기에서나컴퓨터프로그래밍을할때자주나타난다. x = a/b-c+d*e-a*c 다음의수식을사람이계산한다고할때계산하는과정을살펴보자. x ( 중간결과는 temp에기록한다 ) = (a/b)-c+d*e-a*c = (temp1)-c+d*e-a*c = (temp1)-c+(temp2)-a*c = (temp1)-c+(temp2)-(temp3) = (temp4)+(temp2)-(temp3) = (temp5)-(temp3) = (temp6) 위처럼계산하는이유는 *, / 연산자가 +.- 연산자보다먼저계산해야하고또연산자 *, / 나 +,- 가동시에있으면왼쪽에있는식부터계산해야하는것을알고있기때문이다 2
사람은아래식을마음속에다음과같이계산을하게된다. 안쪽괄호부터계산을해나간다. x = ((((a/b)-c)+(d*e))-(a*c)) a b c d e a c / * - * + - 그런데컴퓨터에어떻게이러한사실을알려서계산을하게될까요? 3
1) 수식계산 사람과컴퓨터 사람 1) 연산자의우선순위를정한다. 우선순위가같으면왼쪽부터인지오른쪽부터인지정한다. (/,*.+,- 연산자는왼쪽부터이지만, 지수연산자는오른쪽부터이다.) 2) 복잡하면괄호를사용하여계산하며중간결과를저장한다. (((A/(B**C))+(D*E))-(A*C)) 컴퓨터로수식의계산 사람이하는방법대로계산할수도있지만연구결과중간과정을줄이고한번에왼쪽에서오른쪽으로계산할수있는방법을개발하였다. 1) 수식을후위표기법 (postfix notation) 으로바꾼다. 2) 후위식을계산한다. ( 후위표기법으로표기한식을후위식이라하자 ) 4
연산자의우선순위 (precedence) 표보기 C 언어 연산자 우선순위 결합성 (associativity) () [] ->. 17 left-to-right -- ++ 16 left-to-right -- ++! ~ - + & * sizeof 15 right-to-left (type) 14 right-to-left * / % 13 left-to-right + - 12 left-to-right << >> 11 left-to-right > >= < <= 10 left-to-right ==!= 9 left-to-right & 8 left-to-right ^ 7 left-to-right 6 left-to-right && 5 left-to-right 4 left-to-right?: 3 right-to-left = += -= /= *= %= <<= >>= &= ^= = 2 right-to-left, 1 left-to-right 5
수식계산 컴퓨터 (1) 수식을후위표기법 (postfix notation) 으로바꾼다. 사람이사용하는수식의표기방법은중위 (infix) 표기법이라고한다. 중위표기법은연산자 (operator) 를피연산자 (operand) 가운데놓는방법이다. 3 * 5 => ( 피연산자 ) ( 연산자 ) ( 피연산자 ) 후위표기법은연산자를피연산자뒤에놓고표기하는방법이다. 3 5 * => ( 피연산자 ) ( 피연산자 ) ( 연산자 ) 후위표기법으로놓으면괄호없이도계산순서가일정하다. 예 1) 3 * 5 + 4 중위표기법 -> 3 * 5 + 4 후위표기법 -> 3 5 * 4 + 예 2) 3 * ( 5 + 4 ) 중위표기법 -> 3 * (5 + 4) => 괄호가필요하다.(5+4를먼저계산하려면 ) 후위표기법 -> 3 5 4 + * => 괄호가필요없다. * 괄호가필요없으면계산순서를생각할필요가없어서편하다. 6
(2) 후위식을계산한다. 후위식은중위식과계산방법이다르다. 그렇지만중위식처럼식의왼쪽, 오른쪽우선순위에따라옮겨다니지않고왼쪽부터기계적으로계산을하면된다. 예를들어 1 단계 ) 3 5 * 4 + 3 * 5 + 4 = 3 5 * 4 + 식은 2 단계 ) 15 4 + => 3 5 * 를계산하여저장한다. 3 단계 ) 19 => 15 4 + 를계산한다. 다른예로 3 * ( 5 + 4 ) = 3 5 4 + * 1 단계 ) 3 5 4 + * 2 단계 ) 3 9 * => 5 4 + 를계산한다. 3 단계 ) 27 => 3 9 * 를계산한다. 계산하는방법은연산자가나올때까지읽어서연산자의앞에있는피연산자 두개를이용하여계산하고그자리에저장한다. 7
2) 중위표기를후위표기로바꾸기 중위식을후위식으로쉽게바꾸는방법중위식에괄호를친다음연산자를괄호뒤로옮긴후괄호를지운다. 예 ) ((( A / (B ^ C) ) + (D * E) ) - (A * C) ) => A B C ^ / D E * + A C * - 중위표기 (infix) 2 + 3 * 4 a * b + 5 (1 + 2) * 7 a*b/c (a / (b c + d)) * (e - a) * c a / b c + d * e a * c 후위표기 (postfix) 2 3 4 * + a b * 5 + 1 2 + 7 * a b * c / a b c d + / e a - * c * a b / c d e * + a c * - 8
Q/A 1. 중위식을후위식으로바꾸어라. (1) A / B * ( C + D ) + E (2) (((A /B) + C) - (D * E)) 2. 후위식을중위식으로바꾸어라. (1) B C D * E + (2) A B / C D + * E + 9
2. 스택을이용한후위표기법변환 중위표기를후위표기로바꾸는알고리즘은다음과같다. 수식을읽어연산자와피연산자에따라다음과같이처리한다. (1) 피연산자는출력한다. (2) 연산자는앞연산자 ( 스택의맨위 ) 를살펴서출력하거나대기한다 ( 스택에넣는다, 대기된자료들은나중에대기된연산자가먼저나온다, LIFO, 스택을이용 ) (3) 연산자의대기 ( 스택에 push) 여부는연산자간의우선순위에따른다. 예 ) 후위표기변환예 (1) 수식 a+b*c 를후위식 (postfix) 으로변환 -> abc*+ 10
입력단계별, 스택, 출력결과 토큰 ( 입력 ) 스택의모양 top 변수의값출력 a -1 a a+b*c 토큰스택의모양 top 변수의값출력 + + 0 a 토큰 스택의모양 top 변수의값 출력 b + 0 a b 토큰 스택의모양 top 변수의값 출력 * + * 1 a b 토큰 스택의모양 top 변수의값 출력 c + * 1 a b c 토큰스택의모양 top 변수의값출력 eos( 끝 ) -1 a b c * + 11
예 ) 후위표기변환예 (2) 괄호 (parenthesis) 가있는경우중위표기법에괄호가있는경우는변환과정을복잡하게한다. -후위표기법으로표기하면괄호가없어진다. 왼쪽괄호 무조건스택에넣는다. 오른쪽괄호의처리 왼쪽괄호가나올때까지스택에서 pop 한다. 예 ) 수식 a*(b+c)*d -> 후위표기법으로변환후 abc+*d* a*(b+c)*d 토큰 스택의모양 top 변수의값 출력 a -1 a 토큰스택의모양 top 변수의값출력 * * 0 a 토큰스택의모양 top 변수의값출력 ( * ( 1 a 12
토큰스택의모양 top 변수의값출력 b * ( 1 a b a*(b+c)*d 토큰스택의모양 top 변수의값출력 + * ( + 2 a b 토큰스택의모양 top 변수의값출력 c * ( + 2 a b c 토큰스택의모양 top 변수의값출력 ) * 0 a b c + 토큰스택의모양 top 변수의값출력 * * 0 a b c + * 토큰스택의모양 top 변수의값출력 d * 0 a b c + * d 토큰스택의모양 top 변수의값출력 eos -1 a b c + * d * 13
Q/A 1. 다음식을후위식으로바꿀때스택의변화를적어라. (1) A / B * ( C + D ) + E / * ( * + ( * * + (2) 3 + 2 * 4 (3) ((A /B) + C) - (D * E) 14
( 알고리즘 ) 연산자입력시스택처리 연산자가입력되었을때우선순위비교를통한연산자의 push(), pop() 결정 연산자우선순위를 2 가지로만든다 - in-stack precedence(isp), incoming precedence(icp) top stack 비교 token in-stack precedence 스택에있는연산자의우선순위 in-comming precedence 입력될때연산자의우선순위 If (isp[stack[top]] < icp[token]) /* 입력된연산자가스택의맨위연산자보다우선순위가클경우 ) */ -> push() If (isp[stack[top]] icp[token]) /* 입력된연산자가스택의맨위연산자보다작거나같을경우 ) */ -> pop() until (isp[stack[top]] < icp[token]) 15
프로그램을위한선언부분 선언부 /* 수식계산을위한프로그램선언부분 */ #define MAX_STACK_SIZE 100 /* maximum stack size */ #define MAX_EXPR_SIZE 100 /* max size of expression */ /* 열거형타입 precedence 선언 */ typedef enum {lparen, rparen, plus, minus, times, divide, mode, eos, operand } precedence; precedence stack[max_stack_size];/* 스택선언 */ char expr[max_expr_size]; /* 입력문자열 */ static int isp[] = {0,19,12,12,13,13,13,0}; static int icp[] = {20,19,12,12,13,13,13,0}; 16
get_token 함수 /* 입력에서토큰을받아들이는프로그램 */ precedence get_token(char *symbol, int *n) { *symbol = expr[(*n)++]; switch(*symbol) { case ( : return lparen; case ) : return rparen; case + : return plus; case - : return minus; case / : return divide; case * : return times; case % : return mod; case : return eos; default: return operand; } } 17
postfix 함수 /* 중위표기를후위표기로바꾸는프로그램 */ void postfix(void) { char symbol; precedence token; int n = 0; int top = 0; stack[0] = eos; for(token = get_token(&symbol, &n); token!= eos; token = get_token(&symbol, &n)) { if(token == operand) printf( %c, symbol); else if(token == rparen) { while(stack[top]!= lparen) print_token(pop()); pop(); } } else { while(isp[stack[top]] >= icp[token]) print_token(pop()); push(token); } } while((token = pop())!= eos) print_token(token); printf( \n ); 18
3. 스택을이용한후위표기식계산 후위표기 (postfix) 식의계산 - 괄호 (parenthesis) 가필요없다 - 연산자우선순위 (precedence) 가필요없다 프로그램복잡도 - 시간 : O(r) r : 수식의기호의개수 - 기억공간 : S(n) = n n : 연산자의수 19
예 ) 6 2 / 3-4 2 * + 토큰스택의모양 top 변수의값 6 6 0 토큰스택의모양 top 변수의값 2 6 2 1 토큰스택의모양 top 변수의값 / 3 0 토큰스택의모양 top 변수의값 3 3 3 1 20
예 ) 6 2 / 3-4 2 * + 토큰 스택의모양 top 변수의값 - 0 0 토큰 스택의모양 top 변수의값 4 0 4 1 토큰 스택의모양 top 변수의값 2 0 4 2 2 토큰 스택의모양 top 변수의값 * 0 8 1 토큰 스택의모양 top 변수의값 + 8 0 21
Q/A 1. 후위식을계산할때스택의변화를적어라. (1) 1 2 + 7 * 1 2 1 3 7 3 21 (2) 3 3 / 4-5 6 * + 3 4 * - 22
eval() 함수 get_token() 함수 /* 수식에서토큰을한개씩읽는프로그램 */ eval() { if the token is operand convert to number and push to the stack otherwise 1) pop two operands from the stack 2) perform the specified operation 3) push the result back on the stack } 23
eval 함수 /* 후위표기식을계산하는프로그램 */ int eval(void) { precedence token; char symbol; int op1, op2; int n = 0; int top = -1; token = get_token(&symbol, &n); while (token!= eos) { if(token == operand) push(symbol- 0 ); else { op2 = pop(); op1 = pop(); switch(token) { case plus: push(op1 + op2); ( 계속 ) break; 24
case minus: push(op1 - op2); eval 함수 break; case times: push(op1 * op2); break; case divide: push(op1 / op2); } break; case mod: push(op1 % op2); } } token = get_token(&symbol, &n); } return pop(); 25
Review 스택은리스트의특별한형태로삽입과삭제가한쪽끝에서만일어난다. 마치문이한개인관광버스에손님들을타고내릴때, 먼저탄사람이맨나중에내리는것과같은구조이다 (First In Last Out). 다시말하면맨나중에탄사람이맨먼저내리는구조이다 (Last in First Out, LIFO). 큐또한리스트의특별한형태로삽입과삭제가한쪽끝에서만일어난다. 삽입과삭제는서로반대쪽에서일어나는것이스택과다르다. 문이두개인마을버스의타는곳과내리는곳이따로있어서먼저탄사람이먼저내리는구조이다 (First In First Out, FIFO). 컴퓨터에서수식의계산은 (1) 수식을후위표기식으로바꾸고, (2) 후위표기식을계산하는두과정으로이루어진다. 두과정모두스택자료구조를필요로한다. 26