백준 괄호 추가하기 - 응용(계산기 처럼 사칙연산 순서를 고려한 계산)

백준 괄호추가하기 문제의 경우에는 수학에서 말하는 사칙연산의 순서가 없습니다. 하지만 사칙연산의 순서를 고려해서 계산을 하려면 어떻게 해야할까요?  기본적으로 우선순위를 괄호, 곱하기와 나누기, 나머지 연산 이런 순으로 처리가 되어야 할 것입니다. 그래서 중간 중간 괄호와 곱하기 나누기를 먼저 처리하고 맨 나중에 더하기와 빼기만 처리하면 될 것 같습니다.

 

뼈대는 괄호 추가하기 문제처럼 숫자와 연산자를 나눠서 처리합니다. 괄호는 연산자에 추가해줍니다. ' ( ' 기호가 등장하면 일단 연산자쪽에 추가를 해줍니다. 다만 ' ) '가 나오면 ' ( '가 등장할 때까지의 연산을 먼저 처리합니다. 그리고 그 결과를 ' ( '를 삭제함과 동시에 숫자가 저장되는 자료구조에 넣어주고 연산을 진행합니다.

다음에는 곱하기와 나누기 연산입니다. 곱하기와 나누기는 더하기와 빼기보다는 항상 먼저 계산을 해야합니다. 연산자를 연산자 자료구조에 추가하는 과정에서 아래 예시처럼 곱하기가 나왔습니다. 실제 곱하기 처리는 빼기를 넣기전에 곱하기를 먼저 연산을하고 숫자 자료구조를 업데이트 합니다. 그리고 빼기와 관련된 연산을 추가합니다.

즉 빼기 연산자를 탐색하는 위치에서 이전 연산자를 확인하고, 이전 연산자가 곱하기나 나누기라면 그때 먼저 연산을 하고 자료구조에 넣어줍니다. 마지막에 오는 곱하기와 나누기는 순차적으로 푸는데 문제가 없기에, 연산을 마무리하면 됩니다.

 

여기서 숫자와 연산자를 처리할 때 효율적인 자료구조는 개인적으로 스택을 쓰면 정리가 좀 편해질 듯합니다. 물론 큐나 벡터를 써도 풀이는 가능합니다.

 

 

---

문자열 수식이 주어질 때 해당 연산을 지원하는 엑셀의 eval함수나 파이썬이나 c++에서 제공하는 evaluate 함수들이 어떻게 동작하는지 좀 더 파악을 해봐야 겠습니다.