[자료구조] 후위 수식의 계산

[ 문제 ] 후위로 변환된 수식을 입력받아 스택을 사용하여 계산한 후 결과 값을 출력하는 프로 그램을 작성하시오.

• 스택은 배열이나 연결리스트로 구현함
• 수식의 피연산자는 0에서 9사이의 정수이고, 각 수식의 최대길이는 100으로 함
• 수식의 연산자는 곱하기, 나누기, 더하기, 빼기로 구성되며, 정수 연산 수행(나누기의 경우 몫 계산)

예제

◦ 입출력에 대한 설명 (아래 입출력 예시 참조)

1) 첫 번째 라인: 수식의 개수

2) 두 번째 라인: 하나 줄에 후위 수식이 공백 없이 입력됨

#include  <stdio.h>
#include  <string.h>
#include  <stdlib.h>
#define MAX_STACK_SIZE 100

int err = 0;  //에러가 발생했는지 체크하는 변수(0: 에러 없음, 1: 에러 발생)

// ===== 스택 코드의 시작 ===== 
typedef struct {
   char data[MAX_STACK_SIZE];
   //스택의 배열: 최대 용량은 100
   int num;//(현재 스택의 데이터 개수 - 1 )
} StackType;

// 스택 초기화 함수
void Initialize(StackType *s){s->num = -1;}
/**
현재 스택의 데이터 개수를 초기화한다.
이때 (현재 데이터 개수 -1)를 하는 이유는 배열의 인덱스 값으로 맞추기 위함이다.
 */

// 공백 상태 검출 함수
int IsEmpty(StackType *s){return (s->num == -1);}
// 포화 상태 검출 함수
int IsFull(StackType *s){return (s->num >= (MAX_STACK_SIZE - 1));}

// 삽입함수
void Push(StackType *s, char ipt){
   if (IsFull(s)) {
      printf("스택 포화 발생\n");
      return;
   }
   else s->data[++(s->num)] = ipt;
}
// 삭제함수
char Pop(StackType *s){
   if (IsEmpty(s)) {
      printf("스택 공백 발생: 프로그램을 종료합니다.");
      exit(1);
   }
   else return s->data[(s->num)--];
}
// 피크함수
char Peek(StackType *s){
   if (IsEmpty(s)) {
      printf("스택 공백 발생: 프로그램을 종료합니다.");
      exit(1);
   }
   else return s->data[s->num];
}
// ===== 스택 코드의 끝 ===== 

// 후위 표기 수식 계산 함수
int Cal(char arr[]){
   int op1, op2, value;
   char ch;
   StackType s;//스택을 선언

   Initialize(&s);//스택을 초기화

   for (int i = 0; i < (int)strlen(arr); i++) {
      //인자로 받은 배열 만큼 반복

      ch = arr[i];//현재 인덱스의 값을 저장
      
      // 입력이 피연산자이면 : 연산자가 아닌 값
      if (ch != '+' && ch != '-' && ch != '*' && ch != '/') {
         value = ch - '0';   
         Push(&s, value);
      }
      else {   
         //연산자이면 피연산자를 스택에서 제거
         op2 = Pop(&s);//op2에 저장 후 피연산자 삭제됨
         op1 = Pop(&s);//op1에 저장 후 피연산자 삭제됨

         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(void){
   char arrression[MAX_STACK_SIZE];//크기가 MAX_STACK_SIZE인 배열을 선언
   int num;scanf("%d",&num);//정수를 입력받음
   getchar();

   for(int i=0;i<num;i++){//입력받은 정수만큼 반복
      scanf("%s", arrression);//문자열을 입력받고
      int result2 = Cal(arrression);//수식 변환 함수를 실행 후 반환 값을 저장
      printf("%d\n",result2);
   }
   return 0;
}