자료구조 infix를 postfix로 변환되는 알고리즘

본문내용

력하시오 : ");
scanf("%s",expr);
strcat(expr," "); /* 수식에 eos 연결 (공백 삽입) */
printf("[중위표기] %s\n",expr);
postfix( );
printf("[후위표기] %s\n",expr);
printf("계산결과 = %d\n",eval( ));
}
void push(int *top, int item)
{
if(*top >= MAX_STACK_SIZE-1)
{
fprintf(stderr,"\n스택이 꽉 찼습니다.\n"); /* print error message */
exit(1);
}
stack[++*top]=item;
}
void ppush(int *top, precedence item)
{
if(*top >= MAX_STACK_SIZE-1)
{
fprintf(stderr,"\n스택이 꽉 찼습니다.\n"); /* print error message */
exit(1);
}
pstack[++*top]=item;
}
int pop(int *top)
{
if(*top == -1)
{
fprintf(stderr,"\n스택이 비었습니다.\n");
exit(1);
}
return stack[(*top)--];
}
precedence ppop(int *top)
{
if(*top == -1)
{
fprintf(stderr,"\n스택이 비었습니다.\n");
exit(1);
}
return pstack[(*top)--];
}
precedence get_token(char *symbol, int *n)
{
*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;
}
}
int eval(void)
{
precedence token;
char symbol;
int op1, op2;
int n=0; /* 수식 문자열을 위한 카운터 */
int top=-1;
int i;
token =get_token(&symbol, &n);
while (token != eos)
{
if(token == operand) {
push(&top, symbol-'0'); /* 스택 삽입 */
printf("계산과정 : ");
for(i=0;stack[i] != '\0';i++){
printf("%d",stack[i]);
}
printf("\n");
}
else
{
/* 두 피연산자를 삭제하여 연산을 수행한 후, 그 결과를 스택에 삽입함 */
op2 = pop(&top); /* 스택 삭제 */
op1 = pop(&top); /* 스택 삭제 */
switch(token)
{
case plus : push(&top,op1+op2); break;
case minus : push(&top,op1-op2); break;
case times : push(&top,op1*op2); break;
case divide: push(&top,op1/op2); break;
case mod : push(&top,op1%op2); break;
}
printf("계산과정 : ");
printf("%d",*stack);
printf("\n");
}
token = get_token(&symbol, &n);
}
return pop(&top); /* 결과를 반환 */
}
char print_token(precedence token)
{
switch (token)
{
case lparen : return '(';
case rparen : return ')';
case plus : return '+';
case minus : return '-';
case divide : return '/';
case times : return '*';
case mod : return '%';
case eos : return ' ';
default : return ' ';
}
}
void postfix(void)
{ /* 수식을 후위 표기식으로 출력한다. */
precedence token;
char symbol, pexpr[MAX_EXPR_SIZE]={0};
int pn=0, n=0, top=0;
pstack[0]=eos;
token = get_token(&symbol, &n);
while (token != eos)
{
if(token == operand)
{
pexpr[pn++]=symbol;
printf("postfix 표기 과정 %s\n", pexpr);
}
else if (token == rparen)
{ /* 왼쪽 괄호가 나올때까지 토큰들을 제거해서 출력시킴 */
while(pstack[top] != lparen)
pexpr[pn++]=print_token(ppop(&top));
strcat(pexpr, " ");
printf("postfix 표기 과정 %s\n", pexpr);
ppop(&top);
}
else
{
while(isp[pstack[top]] >= icp[token])
pexpr[pn++]=print_token(ppop(&top));
ppush(&top,token);
}
token = get_token(&symbol, &n);
}
while( (token=ppop(&top)) != eos )
pexpr[pn++]=print_token(token);
pexpr[pn++]=' ';
pexpr[pn]='\0';
printf("postfix 표기 과정 %s\n", pexpr);
strcpy(expr,pexpr);}
● 실행 화면
◆ 모든 경우의 수 실행 화면
◎ 2+3+5 ◎ 2*3+5
◎ 2+3*5 ◎ 2*3*5
◎ (2+3)+5 ◎ (2*3)+5
◎ (2+3)*5 ◎ 2*3/5
◎ 2*(3+5) ◎2*3-5
◎ 2+3-5 ◎ 6/(2+1)

키워드

자료구조,   postfix,   infix,   stack