[자료구조] 스택 (2)

(5) 스택의 응용 : 괄호 검사 문제
조건 1: 왼쪽 괄호의 개수 = 오른쪽 괄호의 개수
조건 2: 같은 종류의 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야한다.
조건 3: 서로 다른 종류의 왼쪽과 오른쪽 괄호 쌍은 서로를 교차하면 안된다.

...
int check(char expr[])
{
    StackType S;
    init(&S);
    int ch, t;
    int n = strlen(expr);
    for(int i=0 ; i<n ; i++)
    {
        ch = expr[i];
        if(ch == '(' || ch =='{' || ch =='[')
            push(&S, ch);
        else if (ch == ')' || ch=='}' || ch==']')
        {
            if(isEmpty(&S))
                return 0;
            else
            {
                t = pop(&S);
                if( (t == '(' &&  ch !=')')||
                    (t == '{' &&  ch !='}')||
                    (t == '[' &&  ch != ']'))
                    return 0;
            }
        }
    }
   if (!isEmpty(&S)) return 0;
   return 1;
}
int main()
{
    char expr[N];
    printf("수식을 입력하세요: ");
    scanf("%s", expr);
    
    if(check(expr))
        printf("괄호 검사 성공\n");
    else
        printf("괄호 검사 실패\n");
    
    return 0;
}

(6) 스택의 응용: 후위 표기 수식의 계산
중위 표기 방법에서는 먼저 계산해야할 부분을 나타내기 위해 괄호를 사용해야 하는데, 후위 표기방식에서는 괄호를 사용하지 않고도 우선 계산해야 할 내용을 나타낼 수 있고, 연산자의 우선순위도 생각할 필요가 없기 때문에 컴파일러에서는 후위 표기 방법을 더 선호한다.

중위 표기법 : ab+5 , (1+2)7
후위 표기법 : ab*5+ , 12+7*

① 수식을 왼쪽에서 오른쪽으로 스캔해, 피 연산자이면 스택에 저장한다.
② 연산자이면 필요한 수만큼 피연산자를 스택에서 꺼내 연산을 실행하고 연산의 결과를 다시 스택에 저장한다.

//후위 표기 수식 함수
int eval(char expr[])
{
    StackType S;
    init(&S);
    
    int op1, op2, value;
    char ch; //식에서 한글자씩 읽을 것
    int n=strlen(expr);
    
    for(int i=0 ; i<n ; i++)
    {
        ch = expr[i];
        if(ch != '+' && ch != '-' && ch != '/' && ch !='*')
        {
            value = ch-'0'; // 0 = 48, 숫자 계산이 될 수 있도록 문자를 변환시켜줌 (8=56, 56-48 =8)
            push(&S, value);
        }
        else //연산자이면 피 연산자를 스택에서 제거해 계산해줄 것임임
        {
            op2 = pop(&S);
            op1 = pop(&S);
            switch(ch)
            {
                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 pop(&S); //최종 결과를 전달해줌줌
}
int main()
{
    int result;
    printf("후위 표기식은 82/3-32*+\n");
    result = eval("82/3-32*+");
    printf("%d\n", result);
    
    return 0;
}

(7) 중위 표기 수식을 후기 표기 수식으로 변환
① 입력 수식을 왼->오로 스캔하다 피연산자를 만나면 바로 후위 표기 수식에 출력한다.
② 연산자를 만나면 어딘가 잠시 저장한다. 스택에 존재하는 연산자가 현재 처리중인 연산자보다 우선순위가 높으면 일단 스택에 있는 연산자들 중에서 우선순위가 높은 연산자들을 먼저 출력한 다음에 처리중인 연산자를 스택에 넣는다. (우선순위가 같은 경우에도 스택 상단 요소를 꺼내 출력한다.)
③ 왼쪽 괄호는 무조건 스택에 삽입한다. 오른쪽 괄호를 만나면 왼쪽 괄호가 삭제될때 까지 위에 쌓여있는 모든 연산자들을 출력한다. (왼쪽 괄호는 제일 우선순위가 낮은 연산자

//연산자 우선순위 반환함수
int prec(char op)
{
	switch (op) {
	case '(': case ')': return 0;
	case '+': case '-': return 1;
	case '*': case '/': return 2;
	}
	return -1;
}
//후위 표기 수식 함수
int eval(char expr[])
{
    StackType S;
    init(&S);
    
    int op1, op2, value;
    char ch; //식에서 한글자씩 읽을 것
    int n=strlen(expr);
    
    for(int i=0 ; i<n ; i++)
    {
        ch = expr[i];
        if(ch != '+' && ch != '-' && ch != '/' && ch !='*')
        {
            value = ch-'0'; // 0 = 48, 숫자 계산이 될 수 있도록 문자를 변환시켜줌 (8=56, 56-48 =8)
            push(&S, value);
        }
        else //연산자이면 피 연산자를 스택에서 제거해 계산해줄 것임임
        {
            op2 = pop(&S);
            op1 = pop(&S);
            switch(ch)
            {
                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 pop(&S); //최종 결과를 전달해줌
}
int main()
{
    char *s = "(2+3)*4+9";
    printf("%s\n", s);
    convert(s);
    printf("\n");
    
    return 0;
}

변환하고 계산까지 구현 ... 은 나중에
변환한 결과를 postfix에 받아서 eval로 넣어줘야하는데 어떻게 하지