C - 중위표기식을 후위표기식으로 변환하여 계산하기

◆ 사람들이 보통 사용하는 식은 중위 표기식으로 다음과 같습니다.

(150+60/2)*2+(78-20+60)+1

 

◆ 후위 표기식은 다음과 같은 형태로 스택을 작성하여 구현 할 수 있습니다.

150 60 2 / + 2 * 78 20 - 60 + + 1 +

 

고려사항:

- 괄호 안 연산 우선

- 연산자 우선 순위

- 숫자 자리 수

- 예외 사항 발생 시 리턴

 

절차:

1. 예외 사항 발생 시 예외 메시지 출력 후 리턴 ( 괄호 불 일치, 연산자 에러, 피연산자 에러 )

2. ' ( ' , ' { ' , ' [ ' 이면 PUSH

3. ' ) ' , ' } ' , ' ] ' 이면 ' ( ' , ' { ' , ' [ ' 가 아닐 동안 POP하여 문자 배열에 저장

4. ' + ', ' - ' 일 경우 POP 하여 연산기호 일 경우 문자 배열에 저장, 아닐 경우 다시 PUSH

   현재 연산기호 PUSH

5. ' * ', ' / ' 일 경우 POP 하여 연산 우선 순위가 같은 경우 문자 배열에 저장, 아닐 경우 다시 PUSH

   현재 연산기호 PUSH  

6. 숫자 일 경우 문자 배열에 저장.

   숫자 단위를 구분하기 위해 다음 문자(연산기호, 괄호)를 보고 ' ' 문자 삽입

7. 스택에 남아 있는 문자 POP

8. 문자 배열에 마지막에 '\0' 문자 삽입

 

[ 실행 화면 ]

 

[ 소스 코드]

200 // 중위 표기를 후위 표기로 변환   201 char* infix_to_postfix(char* exp)   202 {   203     int i=0, p=0;   204     int length = strlen(exp);   205     char symbol;   206     char* postfix = (char*)malloc(length * 2);   207    208     for(i=0; i<length; i++)   209     {   210         symbol = exp[i];   211    212         switch(symbol)   213         {          214         case '(' :   215         case '{' :   216         case '[' :   217             push(symbol); // 열림 괄호를 스택에 저장   218             break;   219    220         case ')':   221         case '}':   222         case ']':   223             postfix_case_bloack(postfix, &p);   224             break;   225    226         case '+' :              227         case '-' :      228             postfix_case_operator_1(postfix, symbol, &p);   229             break;   230    231         case '*' :              232         case '/' :                  233             postfix_case_operator_2(postfix, symbol, &p);   234             break;   235    236         default:   237             postfix_case_default(postfix, symbol, exp, &p, i);   238             break;   239         }   240     }

 

 

136 void postfix_case_operator_1(char* postfix, char symbol, int *p)   137 {   138     char temp;   139    140     while(1)   141     {   142         if(top == NULL)   143         {   144             break;   145         }   146         temp = (char)pop(); // 스택에서 하나를 꺼냄   147    148         if(temp == '+' || temp == '-' || temp == '*' || temp == '/') // 연산 기호라면   149         {   150             postfix[(*p)++] = temp; // 문자 배열에 저장\tab   151             postfix[(*p)++] = ' ';   152         }   153         else   154         {   155             push(temp); // 연산 기호가 아니면 다시 스택에 저장   156             break;   157         }   158     }   159     push(symbol); // 현재 연산 기호 저장   160 }

 

 

162 void postfix_case_operator_2(char* postfix, char symbol, int *p)   163 {   164     char temp;   165    166     while(1)   167     {   168         if(top == NULL)   169         {   170             break;   171         }   172         temp = (char)pop(); // 스택에서 하나를 꺼냄   173    174         if(temp == '*' || temp == '/') // 우선순위가 같은 연산 기호라면   175         {   176             postfix[(*p)++] = temp; // 문자 배열에 저장\tab      177             postfix[(*p)++] = ' ';   178         }   179         else   180         {   181             push(temp); // 연산 기호가 아니면 다시 스택에 저장   182             break;   183         }   184     }   185     push(symbol); // 현재 연산 기호 저장   186 }

 

 

188 void postfix_case_default(char* postfix, char symbol, char* exp, int *p, int i)   189 {   190     postfix[(*p)++] = symbol; // 숫자를 문자 배열에 저장   191    192     // 숫자 구분을 위해   193     if(exp[i+1] == '+' || exp[i+1] == '-' || exp[i+1] == '*' || exp[i+1] == '/' ||   194         exp[i+1] == ')' || exp[i+1] == '}' || exp[i+1] == ']' || exp[i+1] == '\0')   195     {   196         postfix[(*p)++] = ' '; // 공란 삽입   197     }   198 }

 

 

73 // 후위 표기 연산    74 element evalPostfix(char *exp)    75 {    76     double opr1, opr2;    77     int value, i=0, count=0;    78     int length = strlen(exp);    79     char symbol;    80     81     for(i=0; i<length; i++)    82     {    83         symbol = exp[i];    84     85         if(symbol >= '0' && symbol <= '9')    86         {    87             while(exp[i + count] != ' ') // 숫자 구분을 위해 검사    88             {    89                 count++;    90             }    91             value = atoi(&exp[i]);    92             i+=count;    93             count=0;    94             push(value);    95         }    96         else    97         {    98             if(symbol != ' ') // 숫자 구분을 위한 ' ' 이 아닌 경우에만    99             {   100                 opr2 = pop();   101                 opr1 = pop();   102    103                 switch(symbol)   104                 {   105                 case '+' : push(opr1 + opr2); break;   106                 case '-' : push(opr1 - opr2); break;   107                 case '*' : push(opr1 * opr2); break;   108                 case '/' : push(opr1 / opr2); break;   109             }   110             }   111         }   112     }   113     return pop();   114 }

 

▶ 전체 소스 코드는 첨부 파일을 다운 받으시면 됩니다.

invalid-file