[백준 / BOJ] 1918 후위 표기식

문제

출처 : www.acmicpc.net/problem/1918

1918번: 후위 표기식

중위 표기법으로 입력된 수식을 후위표기법으로 바꾸는문제다.

후위표기법이란, 연산자가 피연산자 뒤에 위치하는 표기법이다.

후위 표기법의 예는

A+B = AB+

A+B*C = ABC*+ 

A*B+C = AB*C+

A*(B+C) = ABC+*

등이 있다.

 

풀이

구현문제다...

재귀로 풀었다.

처음에는 연산자를 피연산마 맨뒤에 쌓아놓기만 하면 되는거로 구현했다가 다 지우고 다시짰었다...

 

문제에서 시키는대로 구현하면되는데, 괄호처리를 해줘야한다. 괄호처리는 재귀로 구현했다.

 

구현은 

- left, right범위는 문자열 탐색 시작 idx, 끝 idx이다.

1. left, right 범위에서 괄호가 있는지 체크한다.

 

2. 이때 괄호를 만나면 괄호의 범위를 체크해준다.

2-1. '('를 만날때마다 (의 숫자를 +1 해준다. 이때, ')'를 만나면 (의 숫자를 -1 해준다. 만약 '('의 숫자가 0이되면, 0이되는 지점이 가장 바깥 괄호의 끝점을 알수있다.

 

3. left를 괄호의 시작범위 + 1 right를 괄호의 끝범위 -1로 지정하고 1번으로 돌아간다.(재귀)

 

4. 더이상 괄호가없다면, 가장 깊이들어간 괄호부터 풀어가며 연산을 수행한다.

4-1. left, right범위에서 *, / 연산을 찾아서 피연산자 뒤로 이동시킨다. 이때, 이동시킬 피연산자가 이미 다른 연산자에의해 연산이 진행된 상태라면, 연산이 안된위치까지 탐색후 이동시켜야한다. 이 과정을 check배열을 만들어서 이미 연산된 피연산자라면, check[해당 연산자 idx] = 1로 체크해줬다.

4-2. left, right범위에서 +, - 연산을 찾아서 4-1과 똑같이 이동시켜준다.

 

위 과정을 구현하면 답

구현문제 풀때마다 너무 시간이 오래걸리는거 같다...좀더 차분히 생각하고 푸는연습을 해야겠다

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1918%20%ED%9B%84%EC%9C%84%20%ED%91%9C%EA%B8%B0%EC%8B%9D/main.cpp

devxb/JJUNalgo