BOJ 1918: 후위표기식
글쓴이: HDNua / 작성시간: 금, 2014/12/26 - 7:19오후
문제 링크 - https://www.acmicpc.net/problem/1918
윤성우 씨의 열혈 자료구조에서 봤던 내용을 바탕으로 (그대로 썼다는 말은 아니고)
후위 표기식을 구현해봤는데, 다음과 같은 입력은 모두 정상적으로 나옵니다.
((A+B*C)): ABC*+
(A+B)*(C-D)/(E*F)+G: AB+CD-*EF*/G+
(A+B*C-D): ABC*+D-
(A+B)*C: AB+C*
A/B-C: AB/C-
A+B*C: ABC*+
A+B-C: AB+C-
A+B: AB+
일단 알아보시기 쉽도록 주석도 약간 넣었습니다. 어떤 입력에서 오류가 날까요?
컴파일러를 개발하는 중이라 후위 표기식 문제는 간단히 맞출 수 있을 거라고 생각했는데 도무지 모르겠습니다.
+, 어떤 입력에서 오류가 나는지를 묻는 질문은 매번 제가 제대로 테스트해보지 않았다는 생각이 들어 약간 죄송한 마음이 듭니다..
이 질문은 Baekjoon Online Judge 질문 게시판에 먼저 올렸다가 답변이 없어서 올리는 것입니다.
#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; }
Forums:
답변이 없네요..
한 번만 더 수면 위로 올려보고 그래도 답변 없으면 그러려니 하겠습니다..
저는 이렇게 생각했습니다.
지나가다....
컴파일러면 yacc를 사용하실듯 한데, yacc에서 우선순위 정의가 되는데 굳이 postfix가 필요하신건가요? 그냥 궁금해서요......태클은 아닙니다.......
---------------------------------------------------------------
Opensource에 기여하는 것이 꿈입니다.
내가 만든 코드를 모두가 사용할 때 까지~
아.. 지금 풀고 있는게 문제라서요.
컴파일러 구현할 때는 그냥 수식 트리를 쓰고 있습니다만 문제에서 후위표기식으로 구현해보라길래 해봤습니다.
저는 이렇게 생각했습니다.
A+(B+C)*D
A+(B+C)*D
감사합니다.
괄호 연산자에서 역시 문제가 생기는군요.. 소중한 정보 감사합니다.
저는 이렇게 생각했습니다.
댓글 달기