알고리즘 풀이/백준(Boj)
백준(BOJ) 16638번 괄호 추가하기 2
100win10
2020. 4. 9. 15:26
문제 : https://www.acmicpc.net/problem/16638
16638번: 괄호 추가하기 2
길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 곱하기의 연산자 우선순위가 더하기와 빼기보다 높기 때문에, 곱하기를 먼저 계산 해야 한다. 수식을 계산할 때는 왼쪽에서부터 순서대로 계산해야 한다. 예를 들어, 3+8×7-9×2의 결과는 41이다. 수식에 괄호를 추가하면, 괄호 안에 들어있는 식은 먼저 계산해야 한다. 단, 괄호 안에는 연산자가 하나만 들어 있어야 한다. 예를 들어,
www.acmicpc.net
풀이 :
기존 괄호 추가하기 문제는 단순히 해당하는 괄호 연산 (A 연산자 B) 를 ( A 연산자 B + 0 ) 의 형태로 바꾸어서
계산해주었지만 곱셈 우선 계산 시 0 * 다음값이 되어 0이 나오므로 다른 방법이 필요하다.
따라서 여분의 배열을 하나더 만들어서 괄호 부분은 A연산자B만 담게 되고 연산자로 곱하기를 만나게 되면 여분의 배
열에 값과 계산해서 다시 넣어주는 형태로 작성하였다.
코드 ( C++ )
