프로그래밍/코드분석
[백준1918번] (C) 후위표기식
WITN
2018. 5. 15. 23:10
백준 1918번
착안점
- 각 연산자(operator)의 우선순위값을 return해주는 isOperator 함수를 만들어줬다.
(
,)
: 우선순위 0
+
,-
: 우선순위 1
*
,/
: 우선순위 2
피연산자
: 우선순위 -1 (즉, A, B, C)
- postfix함수가 가장 중요한 함수라고 할 수 있다.
for문을 이용해 글자 하나하나씩 읽어나간다.
- 우선순위 -1 : 피연산자는 그대로 출력
- 열린괄호
(
: 스택에 push - 닫힌괄호
)
: 스택에 있는(
를 만날 때까지 pop - 우선순위 1 이상
- 스택이 비어있지 않고 && 스택에 있는 연산자의 우선순위가 더 높다면 pop
- 그외의 경우라면 스택에 push
- 맨 마지막에서는 스택에 남아있는 것이 없도록 모두 pop
#include <stdio.h> #include <string.h> #define MAX_SIZE 100 typedef struct Stack{ int top; char s[MAX_SIZE]; }Stack; void push(Stack *s, char elem){ s->top++; s->s[s->top] = elem; } char pop(Stack *s){ char temp = s->s[s->top]; s->top--; return temp; } int is_empty(Stack *s){ if (s->top != -1) return 0; return 1; } char peek(Stack *s){ return s->s[s->top]; } int isOperator(char op){ switch(op){ case '(': case ')': return 0; case '+': case '-': return 1; case '*': case '/': return 2; default: return -1; } } void postfix(char *str){ int i=0; Stack s; s.top = -1; for(i=0; i<strlen(str); i++){ if(isOperator(str[i]) == -1){ printf("%c", str[i]); } else if(str[i]=='('){ push(&s, str[i]); } else if(str[i]==')'){ while(peek(&s) != '('){ printf("%c", pop(&s)); } pop(&s); } else if (isOperator(str[i]) >=1 ){ // 스택이 비어있지 않고 && 스택 top의 우선순위가 더 높다면 pop while(!is_empty(&s) && isOperator(str[i]) <= isOperator(peek(&s))){ printf("%c", pop(&s)); } push(&s, str[i]); } } while(!is_empty(&s)){ printf("%c", pop(&s)); } } int main(void){ char str[100]; int i=0; scanf("%s", str); postfix(str); }