아래는 제가 작성한 소스 코드인데요, main함수에 있는 중위 연산식을 후위 연산식으로 변환 하는 것이 infixToPostfix함수, 변환된 후위 연산식을 계산하는 것이 evalPostfix함수 입니다. 제가 중위 연산식을 후위 연산식으로 변환하는 알고리즘이
- 왼쪽 괄호를 만나면 무시하고, 다음 문자를 읽는다.
- 피연산자를 만나면 출력한다.
- 연산자를 만나면 stack에 삽입한다.
- 오른쪽 괄호를 만나면 stack을 pop하여 출력한다.
- 수식이 끝나면 공백이 될 때까지 stack을 pop하여 출력한다.
이렇게 알고 있는데요, 제가 만든 infixToPostfix의 결과를 출력할 시에 '피연산자인 숫자들만 출력이 되고 연산자들이 출력이 안 되는 점' 이 몇 번을 머릿속으로 컴파일을 해도 제 머리론 답이 나오지 않아 질문합니다. 제가 생각한 후위 연산식으로 변환한 뒤의 결과물은 25-34*1-+93/-
이고, evalPostfix 함수는 신경 안 써주셔도 됩니다.
#include<stdio.h>
void infixToPostfix(const char*);
int evalPostfix(const char*);
char stack[50];
char stack_result[50];
int top = -1;
char pop(char* a) {
return a[top--];
}
void push(char* a, char data) {
a[++top] = data;
}
void infixToPostfix(const char* c) {
for (int i = 0; c[i] != NULL; i++) {
if (c[i] == '(') { // 왼쪽 괄호
continue;
}
else if (c[i] == ')') { // 오른쪽 괄호
char x = pop(stack);
printf("%c", x);
push(stack_result, x);
}
else if (c[i] >= 48 && c[i] <= 57) { // 피연산자
printf("%c", c[i]);
push(stack_result, c[i]);
}
else { // 연산자
push(stack, c[i]);
}
}
while (top > -1) {
pop(stack);
}
}
int evalPostfix(const char* ch) {
for (int i = 0; ch[i] != NULL; i++) {
if (ch[i] >= 48 && ch[i] <= 57) { // 피연산자
push(stack, ch[i]);
}
else { // 연산자
int opr2 = pop(stack);
int opr1 = pop(stack);
switch (ch[i]) {
case '+':
push(stack, opr1 + opr2);
break;
case '-':
push(stack, opr1 - opr2);
break;
case '*':
push(stack, opr1 * opr2);
break;
case '/':
push(stack, opr1 / opr2);
break;
}
}
}
return pop(stack);
}
void main() {
int result;
const char* express = "((2-5)+((3*4)-1)-(9/3))";
printf("중위 표기식: %s", express);
printf("후위 표기식: ");
infixToPostfix(express);
result = evalPostfix(express);
printf("\n\n연산 결과 => %d", result);
getchar();
}
아래는 출력 결과물 입니다.
중위 표기식: ((2-5)+((3*4)-1)-(9/3))후위 표기식: 25 34 1 93
연산 결과 => 0