[백준] 1918번 후위 표기식 C++

문제 출처: https://www.acmicpc.net/problem/1918

1918번: 후위 표기식

중위 표기식을 후위 표기식으로 변환하는 문제이다.

다음과 같은 규칙에 따라 변환할 수 있다.

 

피연산자 (A, B, C, ..)가 나올 경우 바로 출력해준다.

 

연산자가 나올 경우 

case 1. 스택이 빈 경우 --> 스택에 연산자를 넣어준다.

case 2. 스택에 값이 있는 경우 --> 넣을 연산자보다 우선순위가 높거나 같은 연산자를 모두 pop(출력) 하고 연산자를 push 한다.

 

괄호가 나올 경우

여는 괄호 '('의 경우 스택에 넣어준다.

닫는 괄호 ')'의 경우 여는 괄호가 나올 때까지 스택에 있는 연산자들을 pop(출력) 해주고 여는 괄호도 pop(출력은 X) 해준다.

 

 

Ex) A+B*C

A를 만나서 A를 출력한다. 스택: X 출력 결과: A

+를 만나서 스택이 비어있기 때문에 스택에 넣어준다. 스택:+ 출력 결과: A

B를 만나서 B를 출력한다. 스택: + 출력결과: AB

*를 만나서 자신보다 우선순위가 높거나 같은 연산자를 모두 pop 하지만 스택에 있는 + 보다 현재 넣을 *가 우선순위가 높기 때문에 스택에 넣어준다. 스택: +* 출력 결과: AB

C를 만나서 C를 출력한다. 스택: +* 출력결과: ABC

마지막으로 스택에 있는 모든 값들을 pop 하여 출력 출력 결과: ABC*+