180220 튜터링 - 스택

< 숙제 Review >

- 3자리마다 콤마 찍기 (재귀)

#include <stdio.h>
 
void comma(int n)
{
    int tmp = n/1000;
    if(tmp > 0) {
        comma(tmp);
        printf(",%03d", n%1000);
    }
    else {
        printf("%d", n);
    }
}
 
int main()
{
    int n;
    scanf("%d", &n);
 
    comma(n);
 
    return 0;
}

- %03d : 3자리 확보, 빈자리는 0으로..!!

< Tutoring >

- 스택의 정의 : 나중에 들어온 데이터가 먼저 꺼내진다. 

>> 그냥 프링글스 ㅎㅎ

- 스택의 ADT 및 구현하기

#include <stdio.h>
#define MAX 100
typedef struct stack {
    int s[MAX];
    int top;
} Stack;    
 
void init(Stack *s)
{
    s->top = -1;
}
 
int isEmpty(Stack *s)
{
    return s->top == -1;
}
 
int isFull(Stack *s)
{
    return s->top == MAX-1;
}
 
void push(Stack *s, int data)
{
    s->s[++(s->top)] = data;
}
 
int peek(Stack *s)
{
    return s->s[s->top];
}
 
void pop(Stack *s)
{
    (s->top)--;
}
 
int main()
{
    Stack s;
    init(&s);
 
    isEmpty(&s) ? puts("Empty") : puts("Not Empty");
    isFull(&s) ? puts("Full") : puts("Not Full");
 
    push(&s, 1); 
    push(&s, 3); 
    push(&s, 5); 
    push(&s, 7);
 
    printf("%d\n", peek(&s)); pop(&s);
    printf("%d\n", peek(&s)); pop(&s);
    printf("%d\n", peek(&s)); pop(&s);
    printf("%d\n", peek(&s)); pop(&s);
 
    isEmpty(&s) ? puts("Empty") : puts("Not Empty");
 
    return 0;
}
 

>> 실행결과

Empty

Not Full

7

5

3

1

Empty

- 연결리스트를 이용한 구현 (coded by ㄱㄱㄷ ㅋㄱ ㄱㅇㄹ)

#include <stdio.h>
#include <stdlib.h>
 
typedef struct node{
   char data;
   struct node * next;
} Node;
 
typedef struct listStack {
   Node * top;
} ListStack;
 
void init(ListStack * list) {
   list->top = NULL;
}
 
int isEmpty(ListStack * list) {
   return list->top == NULL;
}
 
int peek(ListStack * list) {
   if(isEmpty(list)) {
      printf("빈 스택임");
      return -111111;
   }
   
   return (list->top)->data;
}
 
void push(ListStack * list, int data) {
   Node * tmp = (Node*) malloc(sizeof(Node));
   tmp->data = data;
   tmp->next = list->top;
   list->top = tmp;
}
 
void pop(ListStack * list) {
   Node *tmp = list->top;
   list->top = tmp->next;
   free(tmp);
}
 
int main()
{
    ListStack s;
    init(&s);
 
    isEmpty(&s) ? puts("Empty") : puts("Not Empty");
 
    push(&s, 1); 
    push(&s, 3); 
    push(&s, 5); 
    push(&s, 7);
 
    printf("%d\n", peek(&s)); pop(&s);
    printf("%d\n", peek(&s)); pop(&s);
    printf("%d\n", peek(&s)); pop(&s);
    printf("%d\n", peek(&s)); pop(&s);
 
    isEmpty(&s) ? puts("Empty") : puts("Not Empty");
    return 0; 
}
 

>>  

- 스택의 응용

1) 괄호검사 (coded by ㄱㄱㄷ ㅋㄱ ㄱㅇㄹ) // 

void RightBracket(const char * str) {
   ListStack l1;
   init(&l1);
   
   int i; for(i=0; str[i]; i++) {
      if(str[i] == '(') push(&l1, '(');
      if(str[i] == ')') {
         if(!isEmpty(&l1)) pop(&l1);
         else {
            printf("NO\n");
            return;
         }
      }
   }
   
   if(isEmpty(&l1)) printf("YES\n");
   else printf("NO\n");
}

>> 5 줄에서 for 문의 조건식을 보자. 

>> 문자열의 마지막은 널문자이다. 널문자의 아스키코드값은 0.

>> 0은 조건식에서 거짓이다.

2) 후위식의 계산

- 알고리즘 : 

>> 연산자를 만나면 앞에 두 피연산자를 꺼내서 계산, 

>> 먼저 꺼낸 피연산자를 우측에 두고 , 나중에 꺼낸 피연산자를 좌측에 두고 연산을 진행한다.

< 소스코드 >

int exp(const char *eq)
{
    int i;
    Stack s;
    init(&s);
 
    for(i=0; eq[i]; i++) {
        if('0' <= eq[i] && eq[i] <= '9') push(&s, eq[i]-'0');
        else {
            int op2 = peek(&s); pop(&s);
            int op1 = peek(&s); pop(&s);
            switch(eq[i]) {
            case '+': push(&s, op1+op2); break;
            case '-': push(&s, op1-op2); break;
            case '*': push(&s, op1*op2); break;
            case '/': push(&s, op1/op2); break;
            }
        }
    }
    return peek(&s);
}
 
int main()
{
    printf("%d\n", exp("234*+"));       // 14
    printf("%d\n", exp("82/3-32*+"));   // 7
    return 0;
}
 

>> 10 : 오른쪽 피연산자가 먼저 꺼내짐에 주의.

>> 7 : 문자열의 끝은 널문자인데, 널문자의 아스키코드값은 0. 0은 조건식에서 거짓. 즉 널물자를 만나면 for 문을 탈출한다.

>> for 문의 조건식에 strlen(eq[i]) 라고 적는것은 안좋다.

     for 문의 경우 초기식 - (조건식, 바디, 증감식)의 반복 으로 이루어 지는데, 조건식을 확인할 때마다 strlen() 함수가 작동한다.

     O(n) 으로 해결할 것도 O(n^2) 이 되버리는 신기한(?) 일이 발생한다.

3) 중위식을 후위식으로 바꾸기.

- 연산자 우선순위 

>> *, / : 제일 크다.

>> +, - : 두번째

>> ( : 제일 작다.

- 규칙

>> 피연산자를 만나면 그대로 출력

>> 연산자를 만나면 스택에 push.

>> 스택의 맨 위 연산자의 우선순위가 새로 추가되는 연산자의 우선순위보다 높거나 같다면 꺼내서 출력

>> ( 가중치에 상관없이 스택에 쌓는다. 

>> ) 가 나오면 스택에서 ( 위에 쌓여 있는 모든 연산자를 출력. 그리고 ( 는 꺼내서 버린다.

< 소스코드 >

>> 숙제.

< 숙제 >

- 복습 잘하기

- 올바른 괄호 문자열인지 판단하는 함수( "(", "{", "[" : 세 종류의 괄호 사용)

- 중위식을 후위식으로 만드는 코드.(http://boj.kr/1918)

- 중위식을 후위식으로 만든 다음 그 후위식을 계산하는 코드

- 큐 예습해오기.