◆ 사람들이 보통 사용하는 식은 중위 표기식으로 다음과 같습니다.
(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'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 |
