제3장 스택과 큐.

Presentation on theme: "제3장 스택과 큐."— Presentation transcript:

1 제3장 스택과 큐

2 3.4 수식의 계산 x=a/b-c+d*e-a*c x=a/(b-c+d)*(e-a)*c

3 3.4 수식의 계산 토큰 우선순위 결합성 () [] -> . 17 L→R -- ++ 16 L→R
토큰            우선순위         결합성  () [] -> L→R -- ++                   16                L→R & * unary - +        15                R→L * / %                       13                L→R + -                           12                L→R > >= < <=            10                L→R == !=                        9                 L→R &&                           5                 L→R ||                               4                  L→R

4 3.4 수식의 계산 수식의 표현 중위 표기(infix notation) : a * b / c
후위 표기(postfix notation)   :  a b * c / 전위 표기(prefix notation)     :  / * a b c 예) x = a / b - c + d * e - a * c         x = ((((a / b) - c) + (d * e)) - (a * c)) 컴파일러 => 후위 표기법 사용

5 3.4 수식의 계산 후위 표기 : x = a b / c - d e * a c * - 괄호 사용 안함
연산자의 우선순위 없음 (L→R 순서의 계산) 중위표기 후위표기 2+3* * + a*b a b * 5 + (1+2)* *

6 3.4 수식의 계산 후위표기 연산방법 연산자를 만날때까지 피연산자를 스택에 저장
연산자를 만나면 연산에 필요한 만큼의 피연산자를 스택에서 가져와서 연산을 실행하고 연산의 결과를 다시 스택에 저장 예) 6 2 / 3 – 4 2 * + 토큰 스택 [0] [1] [2] Top / / / / / / * / * /2-3+4*

7 3.4 수식의 계산 스택과 수식의 표현 방법 #define MAX_STACK_SIZE 100 /*스택의 최대크기*/
#define MAX_EXPR_SIZE 100   /*수식의 최대크기*/ typedef enum { lparen, rparen, plus, minus, times, divide, mod, eos, operand } precedence; int stack[MAX_STACK_SIZE];  /* 전역 배열 */ char expr[MAX_EXPR_SIZE];   /* 입력 스트링 */

8 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) add(&top, symbol-'0'); / *스택 삽입 */ else {          /* 두 피연산자를 삭제하여 연산을 수행후, 결과를 스택에 삽입 */ op2 = delete(&top); /* 스택 삭제 */        op1 = delete(&top); switch(token) { case plus:   add(&top, op1+op2);    break; case minus: add(&top, op1-op2);    break; case times:  add(&top, op1*op2);    break; case divide: add(&top, op1/op2);     break; case mod:   add(&top, op1%op2); } return delete(&top); /* 결과를 반환 */

9 3.4 수식의 계산 precedence get_token (char *symbol, int * n) {
/* 다음 토큰을 취한다. symbol은 문자 표현이며, token은 그것의 열거된 값으로 표현되고, 명칭으로 반환된다. */ *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; }

10 3.4 수식의 계산 중위 표기에서 후위 표기로의 변환 a*(b+c)*d 스택 [0] [1] [2] * * ( * ( * ( +
*    ( *    (     *    (     + output a ab abc abc+ abc+* abc+*d abc+*d* 토큰 a * ( b + c ) d eos top -1 1 2

11 3.4 수식의 계산 isp(in-stack precedence)와 icp(incoming precedence)
precedence stack[MAX_STACK_SIZE]; /* isp와 icp 배열 -- 인덱스는 연산자 lparen, rparen, plus, minus, times, divide, mod, eos의 우선순위 값 */ static int isp[] = { 0, 19, 12, 12, 13, 13, 13, 0 }; static int icp[] = { 20, 19, 12, 12, 13, 13, 13, 0 };

12 void postfix(void) { char symbol; precedence token; int n = 0; int top = 0; /* eos를 스택에 놓는다. */ 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(delete(&top)); /* 토큰들을 제거해서 출력시킴 */ delete(&top); /* 좌괄호를 버린다 */ } else {  /* symbol의 isp ≥ token의 icp ⇨ symbol을 제거하고 출력 */ while (isp[stack[top]] >= icp[token]) print_token(delete(&top)); add(&top, token);     } while ((token=delete(&top)) != eos) print_token(token); printf("\n");

13 과제물 중위 표기법 -> 후위 표기법 변환 알고리즘 후위 표기법 계산 알고리즘