글 읽기 - 1918 후위 표기식 문제, 어떤 입력에서 에러가 있을까요?

hdnua 9년 전 4

윤성우 씨의 열혈 자료구조에서 봤던 내용을 바탕으로 (그대로 썼다는 말은 아니고)

후위 표기식을 구현해봤는데, 다음과 같은 입력은 모두 정상적으로 나옵니다.

test using ideone

Success time: 0 memory: 5108 signal:0
((A+B*C)): ABC*+
Success time: 0 memory: 5100 signal:0
(A+B)*(C-D)/(E*F)+G: AB+CD-*EF*/G+
Success time: 0 memory: 5104 signal:0
(A+B*C-D): ABC*+D-
Success time: 0 memory: 5100 signal:0
(A+B)*C: AB+C*
Success time: 0 memory: 5104 signal:0
A/B-C: AB/C-
Success time: 0 memory: 5096 signal:0
A+B*C: ABC*+
Success time: 0 memory: 5108 signal:0
A+B-C: AB+C-
Success time: 0 memory: 5108 signal:0
A+B: AB+

일단 알아보시기 쉽도록 주석도 약간 넣었습니다. 어떤 입력에서 오류가 날까요?

컴파일러를 개발하는 중이라 후위 표기식 문제는 간단히 맞출 수 있을 거라고 생각했는데 도무지 모르겠습니다.

+, 어떤 입력에서 오류가 나는지를 묻는 질문은 매번 제가 제대로 테스트해보지 않았다는 생각이 들어 약간 죄송한 마음이 듭니다..

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define MAX_EXPR_LEN 1000000

char opStack[MAX_EXPR_LEN] = "";
int opSp = 0;

const char OPERATORS[] = "( ) +-*/"; // (: 0, ): 1, +-: 2, */: 3
int is_op(char data) {
	return (strchr(OPERATORS, data) != 0);
}
int op_pri(char op) {
	int pri = (strchr(OPERATORS, op) - OPERATORS) / 2;
//	printf("op_pri: %c: %d\n", op, pri);
	return pri;
}

int main(void) {
	char infix[MAX_EXPR_LEN] = "";
	char postfix[MAX_EXPR_LEN] = "";
	char data;
	char *pin, *pout;
	char top;
	
	scanf("%s", infix);
	pin = infix, pout = postfix;
	while ((data = *pin++)) {
		if (isalpha(data)) { // 항이면 넣는다
			*pout++ = data;
		} else if (is_op(data)) { // operator
			if (opSp == 0) { // operator stack is empty
				if (data != ')') {
//					printf("1: %c pushed\n", data);
					opStack[opSp++] = data;
				}
			} else if (data == '(') { // 괄호 연산자라면 그냥 넣는다
//				printf("2: ( pushed\n");
				opStack[opSp++] = '(';
			} else {
				while (opSp > 0) {
					top = opStack[opSp-1];
					if (op_pri(data) > op_pri(top)) {
						// 기존 연산자보다 새 연산자의 우선순위가 높다면 탈출 
						// A+B*C의 경우 +, *를 비교하는데 *가 +보다 우선순위가 높으므로 탈출한다 
//						printf("%c : %c -> break\n", data, top);
						if (top == '(') {
							--opSp;
						}
						break;
					}
					--opSp;
					*pout++ = top;
				}
				if (data != ')') {
//					printf("3: %c pushed\n", data);
					opStack[opSp++] = data;
				}
			}
		}
	}
	while (opSp > 0) { // 스택이 빌 때까지
		top = opStack[--opSp]; // 연산자를 출력한다
		if (top == '(') {
			continue;
		}
		*pout++ = top;
	}
	
	printf("%s", postfix);
	return 0;
}

hdnua 9년 전 0

다른 커뮤니티에서 답을 얻었는데, A+(B+C)*D 입력에서 오류가 있었습니다.

닫는 괄호가 연산자로 온 경우와 다른 연산자가 온 경우에 대해 스택에 들어있는 ( 연산자의 처리를 달리 해야 하는군요..

좋은 정보 얻었습니다.

psychobabo 7년 전 1

덕분에 맞았네요~ 감사합니다!

댓글을 작성하려면 로그인해야 합니다.