[자료구조] 중위 수식 변환 프로그램 (1)

코드 수정 및 설명을 추가한 포스팅인 아래 링크를 이용한다.

24.05.17 수정 및 컴파일 확인 완료

[6] 스택 ⑥ 스택의 응용 : 중위수식 변환

[ 문제 ] 스택을 이용하여 중위수식을 후위수식으로 변환하는 프로그램을 작성하시오.

• 스택은 배열이나 연결리스트로 구현함
• 수식의 피연산자는 영문자(대문자)로 나타내고, 각 수식의 최대길이는 100으로 함
• 수식은 아래 우선순위를 갖는 연산자들을 포함함 (숫자가 높을수록 우선순위가 높음)

입력토큰	연산자	우선순위
! + -	단항연산자	6
*	곱셈	5
/	나눗셈	5
+	덧셈	4
-	뺄셈	4
>	관계연산자	3
<	관계연산자	3
&&	논리연산자(AND)	2
||	논리연산자(OR)	1

• 같은 우선순위를 갖는 연산자들은 왼쪽에서 오른쪽으로 계산하도록 함
• 입출력에 대한 설명 (아래 입출력 예시 참조)

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

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

풀이

전위 수식	연산자를 먼저 표기하고 연산에 피연산자를 나중에 표기하는 방식
중위 수식	연산자를 두 피연산자 사이에 표기하는 방법. 가장 일반적으로 사용되는 표현 방법. 산술 연산, 논리 연산, 비교 연산 등에 주로 사용됨.
후위 수식	피연산자를 먼저 표기하고 연산자를 나중에 표기하는 방법

중위 수식을 후위 수식으로 변환하는 과정

1. 연산 순서에 따라 괄호로 묶는다.
2. 가장 낮은 우선 순위의 연산자를 괄호 바로 뒤인 우측으로 옮기는 과정을 높은 우선 순위 방향으로 반복한다.
3. 필요없는 괄호를 모두 제거한다.

[변환전] A*B+C+(D+E)*F
1.연산 순서에 따라 괄호로 묶는다.
(((A*B)+C)+((D+E)*F))
2.연산자를 괄호 바로 뒤인 우측으로 옮긴다.
(((A*B)+C)((D+E)*F))+
(((A*B)C)+((D+E)*F))+
(((A*B)C)+((D+E)F)*)+
(((AB)*C)+((D+E)F)*)+
(((AB)*C)+((DE)+F)*)+
3.필요없는 괄호를 모두 제거한다.
[변환후]AB*C+DEF*+

[변환전] A/B-C+D*E-F*G
1.연산 순서에 따라 괄호로 묶는다.
((((A/B)-C)+(D*E))-(F*G))
2.연산자를 괄호 바로 뒤인 우측으로 옮긴다.
((((A/B)-C)+(D*E))(F*G))-
((((A/B)-C)(D*E))+(F*G))-
((((A/B)C)-(D*E))+(F*G))-
((((A/B)C)-(DE)*)+(F*G))
((((AB)/C)-(DE)*)+(F*G))-
((((AB)/C)-(DE)*)+(FG)*)-
3.필요없는 괄호를 모두 제거한다.
[변환후]AB/C-DE*+FG*-

 

첫 번째 수식

세 번째 수식

 

1.  숫자가 나오면 그대로 출력한다.
2. (이 나오면 스택에 push한다.
3. * / 나오면 스택에 push한다.
4. + - 연산이 나오면 여는 괄호('('), 여는 괄호가 없다면 스택의 끝까지 출력하고 그 연산자를 스택에 push한다.
5. 닫는 괄호( ')' )가 나오면 여는 괄호( '(' )가 나올때까지 pop하여 출력한다.

[1차 코드: 오류 수정 전]

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

#define MAX_STACK_SIZE 100

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

typedef char element;


// ===== 스택 코드의 시작 ===== 
typedef struct {
   element data[MAX_STACK_SIZE];
   char top;
} StackType;

// 스택 초기화 함수
void init_stack(StackType *s)
{
   s->top = -1;
}

// 공백 상태 검출 함수
int is_empty(StackType *s)
{
   return (s->top == -1);
}
// 포화 상태 검출 함수
int is_full(StackType *s)
{
   return (s->top == (MAX_STACK_SIZE - 1));
}
// 삽입함수
void push(StackType *s, element item)
{
   if (is_full(s)) {
      fprintf(stderr, "스택 포화 에러\n");
      return;
   }
   else s->data[++(s->top)] = item;
}
// 삭제함수
element pop(StackType *s)
{
   if (is_empty(s)) {
      fprintf(stderr, "스택 공백 에러\n");
      exit(1);
   }
   else return s->data[(s->top)--];
}
// 피크함수
element peek(StackType *s)
{
   if (is_empty(s)) {
      fprintf(stderr, "스택 공백 에러\n");
      exit(1);
   }
   else return s->data[s->top];
}
// ===== 스택 코드의 끝 ===== 

// 후위 표기 수식 계산 함수
int eval(char exp[])
{
   int op1, op2, value, i = 0;
   int len = strlen(exp);
   char ch;
   StackType s;

   init_stack(&s);
   for (i = 0; i < len; i++) {
      ch = exp[i];
      if (ch != '+' && ch != '-' && ch != '*' && ch != '/') {
         value = ch - '0';   // 입력이 피연산자이면
         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 prec(char op)
{
   switch (op) {
   case '(': case ')': return 0;
   case '+': case '-': return 1;
   case '*': case '/': return 2;
   }
return -1;
}

void check_error(element exp[]) {
   err = -1;
   int len = strlen(exp);

   // error 0 : / 연산자 후 0이 오면 예외처리
   for (int i = 0; i < len; i++) {
      if (i + 1 < len && exp[i] == '/' && exp[i + 1] == '0') {
         printf("<error 발생>>\n");
         printf("infix_to_postfix error0: divide by 0\n\n");
         err = 0;
         break;
      }
   }

   int count = 0;
   // error 1 : 괄호의 짝이 맞지 않으면 예외처리
   for (int i = 0; i < len; i++) {
      if (exp[i] == '(') {
         count++;
      }
      else if (exp[i] == ')') {
         count--;
      }
   }
   if (count > 0) {
      printf("<error 발생>>\n");
      printf("infix_to_postfix error1: 괄호 매칭 불가능\n\n");
      err = 1;
   }
   else if (count < 0) {
      printf("<error 발생>>\n");
      printf("infix_to_postfix error1: 괄호 매칭 불가능2\n\n");
      err = 1;
   }

   // error 2 : 예외 문자 포함
   for (int i = 0; i < len; i++) {
      if (exp[i] == '(' || exp[i] == ')') {
         continue;
      }
      else if (exp[i] == '+' || exp[i] == '-' || exp[i] == '*' || exp[i] == '/') {
         continue;
      }
      else if ('A' <= exp[i] && exp[i] <= 'Z') {
         continue;
      }
      else {
         printf("<error 발생>>\n");
         printf("infix_to_postfix error2: 예외 문자 포함\n\n");
         err = 2;
      }
   }

   // error 3 : 한 자리 수 이상의 수 입력에 대해 예외 처리(예시: 23, 123, ...)
   int count_len = 0;
   int max_len = 0;
   for (int i = 0; i < len; i++) {
      if ('0' <= exp[i] && exp[i] <= '9') {
         count_len++;
         if (count_len >= max_len) {
            max_len = count_len;
         }
      }
      else {
         count_len = 0;
      }
   }
   if (max_len >= 2) {
      printf("<error 발생>>\n");
      printf("infix_to_postfix error3: 한 자리수 이상의 입력 포함\n\n");
      err = 3;
   }
}

// 수식 변환함수
element* infix_to_postfix(element exp[])
{
   // 입력받은 표기식 에러 검사
   check_error(exp);
   // 에러가 있다면 다시 실행
   if (err != -1) {
      return NULL;
   }

   int i, idx = 0; //i는 for문의 제어변수, idx는 post_arr의 index
   int len = strlen(exp);
   char ch, op;
   StackType s;
   element* postfix_arr = (element*)malloc(MAX_STACK_SIZE);
   if (postfix_arr == NULL) {
      fprintf(stderr, "메모리 할당 에러\n");
      exit(1);
   }

   init_stack(&s);  //스택 초기화

   // 중위 표기식으로 표현된 식을 순회
   for (int i = 0; i < len; i++)
   {
      // 값을 뽑는다
      ch = exp[i];

      // 일반 숫자라면 그대로 postfix_arr에 추가
      if ('A' <= ch && ch <= 'Z') {
         postfix_arr[idx++] = ch;
      }

      // 연산자 +,-,*,/라면
      else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
         // 스택의 top 값이 현재 연산자보다 우선순위가 높다면
         while (!is_empty(&s) && (prec(ch) <= prec(peek(&s))))
         {
            // 해당 값들은 모두 추가해준다.
            postfix_arr[idx++] = peek(&s);
            pop(&s);
         }
         // 자기자신을 스택에 추가한다.
         push(&s, ch);
      }

      // '('는 무조건 스택에 추가한다.
      else if (ch == '(') {
         push(&s, ch);
      }

      // ')'가 나오면 '('가 나올때 까지 스택에서 pop하여 추가해준다.
      else if (ch == ')') {
         op = pop(&s);
         while (op != '(')
         {
            postfix_arr[idx++] = op;
            op = pop(&s);
         }
      }
   }

   //아직 스택에 남아있는 값들을 모두 추가해준다.
   while (!is_empty(&s)) {
      op = peek(&s);
      pop(&s);
      postfix_arr[idx++] = op;
   }

   // 문자열의 끝을 지정해준다.
   postfix_arr[idx] = '\0';
   return postfix_arr;
}

int main(void){
   element expression[MAX_STACK_SIZE];
   char word[100];
    int num;scanf("%d",&num);
    getchar();
    for(int i=0;i<num;i++){
        scanf("%s", expression);
      element *result = infix_to_postfix(expression);
      if (err == -1) {
         printf("%s\n", result);
      }
    }
   return 0;
}
//
//A&&B||C||!(E>F)
//2/7-1+3*7-5*3

 

https://www.crocus.co.kr/1703

중위 표기법을 후위 표기법으로 변환후 계산하기

해당 블로그의 코드를 참조 및 수정하였다.