180301 튜터링 - 스택의 응용 (수정:180514)

< 숙제 Review >

1. 올바른 괄호 문자열인지 판단하는 함수 ("(", "{", "[" 로 구성)

#include <stdio.h>
#define MAX 100
typedef struct stack {
    char s[MAX];
    int top;
} Stack;    
 
void init(Stack *s);
int isEmpty(Stack *s);
int isFull(Stack *s);
void push(Stack *s, char data);
char peek(Stack *s);
void pop(Stack *s);
 
int isRightBraket(char *bk)
{
    int idx;
    Stack s;
    init(&s);
 
    for(idx=0; bk[idx]; idx++) {
        char ch = bk[idx];
        if(ch == '{' || ch == '(' || ch == '[') push(&s, ch);
        else {
            char tmp;
            if(isEmpty(&s)) return 0;
            tmp = peek(&s); pop(&s);
            if((tmp == '{' && ch != '}') || (tmp == '[' && ch != ']') || (tmp == '(' && ch != ')'))
                return 0;
        }
    }
    return isEmpty(&s);
}
 
int main()
{
    char str[]="[(){}[(){}]]";
    isRightBraket(str) ? puts("True") : puts("False");
    return 0;
}

>> 28-29 : 여는 괄호에 대한 짝이 안맞으면 0을 리턴.

>> 30 : 검사가 끝나면 스택은 비워있어야 하므로..!!

>> 26번 라인잉 추가되었다. 이 코드가 없으면 닫는 괄호로 먼저 시작하는 코드들에 대해 에러가 발생한다. (수정:180514)

2. 중위식을 후위식으로 만드는 함수 (http://boj.kr/1918)

- 연산자 우선순위 

>> *, / : 제일 크다.

>> +, - : 두번째

>> ( : 제일 작다.

- 규칙

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

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

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

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

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

#include <stdio.h>
#define MAX 100
 
typedef struct stack {
    char 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, char data)
{
    s->s[++(s->top)] = data;
}
 
char peek(Stack *s)
{
    return s->s[s->top];
}
 
void pop(Stack *s)
{
    (s->top)--;
}
 
int getPriority(char op)
{
    switch(op) {
        case '*': case '/': return 10;
        case '+': case '-': return 1;
    }
    return 0;
}
 
void infixToPostfix(char *t)
{
    Stack s;
    init(&s);
 
    for(int i=0; t[i]; i++) {
        char ch = t[i];
        if('A' <= ch && ch <= 'Z') printf("%c", ch);
        else {
            if(ch == '(') push(&s, ch);
            else if(ch == ')') {
                char op = peek(&s);
                while(op != '(') {
                    printf("%c", op);
                    pop(&s);
                    op = peek(&s);
                }
                pop(&s);
            }
            else {
                int curP = getPriority(ch);
                while(curP <= getPriority(peek(&s))) {
                    printf("%c", peek(&s)); 
                    pop(&s);
                }
                push(&s, ch);
            }
        }
    }
    while(!isEmpty(&s)) {
        printf("%c", peek(&s));
        pop(&s);
    }
}
 
int main()
{
    char s[100];
    scanf("%s", s);
    infixToPostfix(s);
    puts("");
    return 0;
}
 

>> 이전 튜터링(스택) 때 서술한 알고리즘을 그대로 구현한 코드다

>> A+(B*C)*D*E+F   —>    ABC*D*E*+F+  이렇게 결과가 나온다.

3. 중위식을 후위식으로 만든 후 그 후위식을 계산하는 함수

#include <stdio.h>
#include <stdlib.h>
#define MAX 100
 
typedef struct stack {
    char 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, char data)
{
    s->s[++(s->top)] = data;
}
 
char peek(Stack *s)
{
    return s->s[s->top];
}
 
void pop(Stack *s)
{
    (s->top)--;
}
 
int getPriority(char op)
{
    switch(op) {
        case '*': case '/': return 10;
        case '+': case '-': return 1;
    }
    return 0;
}
 
char* infixToPostfix(char *t)
{
    char *res = (char*)malloc(sizeof(char)*100);
    int idx=0;
 
    Stack s;
    init(&s);
 
    for(int i=0; t[i]; i++) {
        char ch = t[i];
        if('0' <= ch && ch <= '9') { res[idx++]=ch; printf("%c", ch); }
        else {
            if(ch == '(') push(&s, ch);
            else if(ch == ')') {
                char op = peek(&s);
                while(op != '(') {
                    printf("%c", op);
                    res[idx++]=op;
                    pop(&s);
                    op = peek(&s);
                }
                pop(&s);
            }
            else {
                int curP = getPriority(ch);
                while(curP <= getPriority(peek(&s))) {
                    printf("%c", peek(&s)); 
                    res[idx++] = peek(&s);
                    pop(&s);
                }
                push(&s, ch);
            }
        }
    }
    while(!isEmpty(&s)) {
        printf("%c", peek(&s));
        res[idx++] = peek(&s);
        pop(&s);
    }
    res[idx] = 0;
    return res;
}
 
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()
{
    char s[100], *t;
    scanf("%s", s);
    printf("%s = ", s);
    t=infixToPostfix(s);
    printf(" = %d\n", exp(t));
    free(t);
 
    return 0;
}
 

>> input : 8/2-3+3*2

>> output : 8/2-3+3*2 = 82/3-32*+ = 7

>> infixToPostfix() 에서 출력을 할 때마다 해당 문자를 배열에 저장하고,

     이전에 구현해놓은 exp() 를 그대로 사용하면 된다..

     여기서 후위식을 저장할 배열을 왜 동적할당을 했는지 생각해보자..!! (지역변수 관련)

4. 미로탐색

...