'후위표기법'에 해당되는 글 1건

  1. 2009.10.19 C - 중위표기식을 후위표기식으로 변환하여 계산하기 5
Languages/C, C++2009. 10. 19. 00:12

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

(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 }

 

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

'Languages > C, C++' 카테고리의 다른 글

Import C# dll  (2) 2012.08.17
[ 고급반 ] C++ 소켓 통신  (0) 2010.02.08
단기반 실습 - C++  (0) 2009.03.05
단기반 - OOP 프로젝트_C++  (0) 2009.03.05
단기반 - 관리프로그램 프로젝트_C언어  (0) 2009.03.05
Posted by 열ㅇl