[백준] 1918 후위 표기식 java

스택을 사용한 문제였다. 어느 부분에 자료구조를 사용해야 하는지 감을 잡을 수 있는 문제이다.

 

우선 연산자, 피연산자, 괄호의 우선순위를 정해준다.

 

'(', ')' = 0

'-', '+' = 1

'*', '/' = 2

 

그리고 input으로 주어진 식에서 탐색되는 경우는 4가지 이다.

 

1. 알파벳

2. 여는 괄호

3. 닫는 괄호

4. 연산자

 

1번의 경우엔 바로 sb에 append해주면 된다.

 

2번의 경우엔 바로 stack에 push 해주면 된다.

 

3번의 경우엔 스택의 top에 여는 괄호가 나올 때 까지 pop을 해서 그 요소를 sb에 append 해주면 된다.

 

4번의 경우엔 stack의 top에 있는 요소가 현재 연산자보다 높거나 같은 경우 계속해서 pop을 해서 sb에 append 해주면 된다. 그리고 스택이 비거나 현재 연산자보다 낮은 우선순위면 stack에 push 해주면 된다.