◆ 사람들이 보통 사용하는 식은 중위 표기식으로 다음과 같습니다.
(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 } |
▶ 전체 소스 코드는 첨부 파일을 다운 받으시면 됩니다.
CShapDllImport.zip
invalid-file
