스택의 활용 - 계산기 프로그램

 

스택을 활용해서 계산기를 만드는 연습문제이다.

 

중위표기식 ->  후위표기식 -> 후위표기식 계산 순서로 이루어진다.

 

먼저 중위표기식을 후위표기식으로 고쳐보자 

 

1. 중위 to 후위 

헤더 

#ifndef __PostFix_h

#define __PostFix_h

void ConvertRPN(char exp[]);

#endif

소스

#include "Postfix.h"

#include <stdlib.h>

#include "CStack.h"

#include <string.h>

#include <ctype.h>

int PrecOP(char op1, char op2){

    int op1_n = GetOp(op1);

    int op2_n = GetOp(op2);

    if(op1_n == -1 || op2_n == -1){

        printf("에러");

        exit(-1);

    }

    if(op1_n > op2_n) return 1;

    else if(op1 < op2_n) return -1;

    else return 0;

}

int GetOp(char op){

    switch (op)

    {

        case '*':

        case '/':

        return 2;

        case '+':

        case '-':

        return 1;

        case '(':

        return 0;

    }

    return -1;

}

void ConvertRPN(char exp[]){

    Stack stack;

    StackInit(&stack);

    int lens = len(exp);

    char temp[] = (char*)malloc(lens+1);

    memset(temp,0,sizeof(char)*lens+1); //미리 0으로 초기화 해둠

    int Tempindex =0;

    for(int i=0; i<lens; i++){

        char curChar = exp[i];

        if(isdigit(curChar)){

            temp[Tempindex++] = curChar;

        }

        else if(curChar == '(')

        {

            push(&stack,curChar);

        }

        else if(curChar == ')')

        {

            while(!itEmpty(&stack)){

                char c = pop(&stack);

                if(c == '(') break;

                temp[Tempindex++] = c;                

            }

        }

        else{

            while(!itEmpty(&stack) && PrecOP(peek(&stack),curChar)!= -1){

                temp[Tempindex++] = pop(&stack);

            }

            pust(&stack,curChar);

        }

    }

    while(!itEmpty(&stack)){

        temp[Tempindex++] = pop(&stack);

    }

    strcpy(exp,temp);

    free(temp);

}

 

 

 > 중위표기식을 후위표기식으로 고치는 방법은 차량기지 알고리즘을 참고해보자. 

    - 피연산자가 나오면, 출력한다.

    - 여는 괄호가 나오면, 스택에 추가한다. 

    - 닫는괄호가 나오면, 여는괄호가 나올 때 까지 스택에 모든 연산자를 출력한다 (단, 여는괄호는 출력x)

    - 연산자는 스택 있는 연산자와 들어오려는 연산자의 우선순위를 비교한다.

                    > 스택에 있는 연산자가 들어오려는 연산자보다 우선순위가 높거나 같으면, 스택에 연산자 출력

                    > 스택에 연산자가 없거나, 우선순위가 낮은 연산자가 나올 때 까지 이를 반복한다.

 

 

다음은 후위표기식을 계산하는 함수를 정의한 헤더와 소스 파일이다.

 

2. 후위표기식 계산

 

헤더 

#ifndef __Post_ca_H

#define __Post_ca_H

int SolRPN(char exp[]);

   

#endif

소스

#include <string.h>

#include <ctype.h>

#include "CStack.h"

#include "PostCal.h"

int SolRPN(char exp[]){

    Stack stack;

     StackInit(&stack);

   

    for(int i=0; i<len(exp);i++){

        if(isdigit(exp[i]))push(&stack,exp[i]);

        else{

            int backNumber = pop(&stack) -'0';

            int frontNumber = pop(&stack) -'0';

            switch (exp[i])

            {

            case '*':

            push(&stack,frontNumber*backNumber);

            break;

            case '/':

            push(&stack,frontNumber/backNumber);

            break;

            case '+':

            push(&stack,frontNumber+backNumber);

            break;

            case '-':

            push(&stack,frontNumber-backNumber);

            break;

            }

        }

    }

    return pop(&stack);

}

 

 

스택을 이용해 간단하게 후위표기식을 계산할 수 있다.

 

주어진 후위표기식을 돌면서 

> 피연산자는 스택에 넣는다. 

> 연산자를 만나면, 스택에서 피연산자를 꺼내서 계산한 뒤에 다시 스택에 넣는다.

 

 

 

 

 

 

참고자료: 윤성우 열혈자료구조 

 

차량기지 알고리즘 - 위키백과, 우리 모두의 백과사전

 

관련 문제 

https://www.acmicpc.net/problem/1918

1918번: 후위 표기식