[자료구조] 스택 3 – IT와 전인적 사고

스택이 이용되는 대상 중에 사용자가 직접 스택을 다루는 대상으로는 후위표기법 변환 문제가 있습니다. 중위표기법이라고 해서 우리가 흔히 아는 피연산자 사이에 연산자를 표기하는 표기를 입력받아 연산자 우선 순위대로 후위표기법으로 바꾸는 문제입니다.

중위표기법이 1 + 2 라면 후위표기법은 1 2 + 이고 더 복잡한 3 + 2 * 4 – 9 / 3은 3 2 4 * + 9 3 / – 로 변환되어야 합니다.

전문가에 따르면 CPU의 ALU가 사칙연산을 수행할때 후위표기법으로 처리되기도 한다고 하네요.

중위표기법을 후위표기법으로 바꾸는 방법은 아래와 같습니다.

A + B * C 중위표기법
A + (B * C) 괄호치기
A + (B C ) 곱셈 부분 먼저 후위로 변환 A (B C) + 덧셈 부분 변환
A B C * + 완전한 후위표기법 완성

위 규칙대로 7 + 4 * 3 – 9 / 3 을 예로 들면 순서의 흐름은 이렇습니다. 변환된 결과는 postfix에 저장합니다.

(1) 7은 숫자이므로 그대로 postfix에 넣음. postfix: 7 stack: 비워짐
(2) +는 연산자이고 스택이 비어있으므로 스택에 넣음. postfix: 7 stack: +
(3) 4는 숫자이므로 그대로 postfix에 넣음. postfix:7 4 stack: +
(4) *는 연산자이므로 스택에 넣는다. +보다 우선순위가 높아서 이후에 pop할때 먼저 나온다. postfix:7 4 stack: + *
(5) 3은 숫자이므로 그냥 postfix에 넣음. postfix: 7 4 3 stack: + *
(6) – 는 연산자이고 스택에 자신보다 우선순위 높거나 같은 *, +이 있으므로 이들을 빼서 postfix 에 넣고 -를 스택에 넣는다. postfix: 7 4 3 * + stack: – 참고로 스택에 있던 + * 에서 후입선출에 의해 *가 먼저 나온다
(7) 9는 숫자이므로 그대로 postfix에 넣음. postfix: 74 3 * + 9 stack: –
(8) /는 연산자이므로 그냥 스택에 넣는다. 이 경우에도 – 보다 우선순위 높으니 그냥 넣는다. postfix: 7 4 3 * + 9 stack: – /
(9) 3은 숫자이므로 postfix에 그대로 넣음. postfix 7 4 3 * + 9 3 stack: – /
(10) 스택에 남은 -과 /를 모두 빼서 postfix에 넣는다. 이 경우에도 후입선출. postfix: 7 4 3 * + 9 3 / –

아래는 코드 예시다.


#include<stdio.h>
#include<string.h>

#define STACK_MAX_SIZE 100

struct stack
{
    char stack[STACK_MAX_SIZE];
    int Top;
};
typedef struct stack NODE;

void push(NODE *pu,char item)
{
    if (pu->Top == STACK_MAX_SIZE - 1)
    {
        printf(“\n스택이 꽉 찼습니다.”);
    }
    else
        pu->stack[++pu->Top] = item;
}

char pop(NODE *po)
{
    char item=‘#’;
    if(po->Top == –1)
        printf(“\n스택이 비어있습니다.”);
    else
        item = po->stack[po->Top--];
    return(item);
}

int prec(char symbol)
{
    switch(symbol)
    {
        case '(':
            return(1);
        case ')':
            return(2);
        case '+':
        case '-':
            return(3);
        case '*':
        case '/':
        case '%':
            return(4);
        case '^':
            return(5);
        default:
            return(0);
    }
}

void infix_postfix(char infix[])
{
    int len, priority;
    char postfix[STACK_MAX_SIZE], ch;

    NODE *ps;
    ps->Top = –1;

    len = strlen(infix);

    infix[len++] = ')';
    push(ps,'(');

    for(int i=0,j=0;i<len;i++)
    {
        switch(prec(infix[i]))
        {
            case 1:
                push(ps,infix[i]);
                break;
            case 2:
                ch=pop(ps);
                while(ch != '(')
                { 
                    postfix[j++] = ch;
                    ch = pop(ps);
                }
                break;
            case 3:
                ch = pop(ps);
                while(prec(ch) >= 3)
                {
                    postfix[j++] = ch;
                    ch = pop(ps);
                }
                push(ps,ch);
                push(ps,infix[i]);
                break;
            case 4:
                ch = pop(ps);
                while(prec(ch) >= 4)
                {
                    postfix[j++] = ch;
                    ch=pop(ps);
                }
                push(ps,ch);
                push(ps,infix[i]);
                break;
            case 5:
                ch = pop(ps);
                while(prec(ch) == 5)
                {
                    postfix[j++] = ch;
                    ch = pop(ps);
                }
                push(ps,ch);
                push(ps,infix[i]);
                break;
            default:
                postfix[j++]=infix[i];
                break;
        }
    }
    printf (“\n후위표기법은 = ”);
    for(i=0;i<j;i++)
        printf (“%c”,postfix[i]);
}

void main(void)
{
    char choice, infix[STACK_MAX_SIZE];
    do
    {
        printf(“\n\n중위표기식을 입력하세요 = ”);
        fflush(stdin);
        gets(infix);
        infix_postfix(infix);
        printf(“\n\n계속하시렵니까? (Y/y) =”);
        fflush(stdin);
        scanf(“%c”,&choice);
    } while(choice == 'Y' || choice == ‘y’);
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

#include<stdio.h>

#include<string.h>

#define STACK_MAX_SIZE 100

struct stack

{

char stack[STACK_MAX_SIZE];

int Top;

};

typedef struct stack NODE;

void push(NODE *pu,char item)

{

if (pu->Top == STACK_MAX_SIZE - 1)

{

printf(“\n스택이 꽉 찼습니다.”);

}

else

pu->stack[++pu->Top] = item;

}

char pop(NODE *po)

{

char item=‘#’;

if(po->Top == –1)

printf(“\n스택이 비어있습니다.”);

else

item = po->stack[po->Top--];

return(item);

}

int prec(char symbol)

{

switch(symbol)

{

case '(':

return(1);

case ')':

return(2);

case '+':

case '-':

return(3);

case '*':

case '/':

case '%':

return(4);

case '^':

return(5);

default:

return(0);

}

void infix_postfix(char infix[])

{

int len, priority;

char postfix[STACK_MAX_SIZE], ch;

NODE *ps;

ps->Top = –1;

len = strlen(infix);

infix[len++] = ')';

push(ps,'(');

for(int i=0,j=0;i<len;i++)

{

switch(prec(infix[i]))

{

case 1:

push(ps,infix[i]);

break;

case 2:

ch=pop(ps);

while(ch != '(')

{

postfix[j++] = ch;

ch = pop(ps);

}

break;

case 3:

ch = pop(ps);

while(prec(ch) >= 3)

{

postfix[j++] = ch;

ch = pop(ps);

}

push(ps,ch);

push(ps,infix[i]);

break;

case 4:

ch = pop(ps);

while(prec(ch) >= 4)

{

postfix[j++] = ch;

ch=pop(ps);

}

push(ps,ch);

push(ps,infix[i]);

break;

case 5:

ch = pop(ps);

while(prec(ch) == 5)

{

postfix[j++] = ch;

ch = pop(ps);

}

push(ps,ch);

push(ps,infix[i]);

break;

default:

postfix[j++]=infix[i];

break;

}

printf (“\n후위표기법은 = ”);

for(i=0;i<j;i++)

printf (“%c”,postfix[i]);

}

void main(void)

{

char choice, infix[STACK_MAX_SIZE];

{

printf(“\n\n중위표기식을 입력하세요 = ”);

fflush(stdin);

gets(infix);

infix_postfix(infix);

printf(“\n\n계속하시렵니까? (Y/y) =”);

fflush(stdin);

scanf(“%c”,&choice);

} while(choice == 'Y' || choice == ‘y’);

}

소스코드는 교재에서 빌려왔습니다.

답글 남기기 응답 취소