우주의 보조 질문

과학자들은 삶과 우주, 그리고 모든 것에 대한 궁극적인 질문을 이미 찾아냈습니다. 이에 만족하지 못한 과학자들은 더 구체적인 보조(auxiliary) 질문을 계산할 작은 컴퓨터를 만들었습니다. 컴퓨터는 작동했지만 그 결과가 손상되어, 올바른 질문의 일부 조각만 남았습니다.

제작자들은 이 조각에 문자를 삽입하여 원래의 질문을 복원할 수 있다고 믿습니다. 이때 조각에 있던 문자들의 순서를 바꾸거나 삭제해서는 안 됩니다. 즉, 조각은 복원된 질문의 부분 수열(subsequence)로 나타나야 합니다. 또한 올바른 질문은 곱셈 없이 덧셈만 사용하는 산술식이며, 다음 문법을 따른다고 합니다.

<expression> ::= <term> | <term> + <expression><term> ::= <number> | ( <expression> )<number> ::= 0 ... 9 [ <number> ]

문자 +, (, ), 그리고 숫자 0–9 중 어떤 것이든 (조각의 앞이나 뒤를 포함한) 임의의 위치에 삽입할 수 있습니다. 결과가 이 문법에 맞는 올바른 식이 되도록 하기 위해 삽입해야 하는 문자의 최소 개수를 구하세요. 이러한 복원은 항상 가능하므로 이 최솟값은 언제나 잘 정의됩니다.

남아 있는 조각이 한 줄로 주어집니다. 길이가 최대 1000인 비어 있지 않은 문자열이며, 문자 +, (, ), 그리고 숫자 0–9 로만 이루어져 있습니다.

조각의 문자들을 부분 수열로 유지하면서, 조각을 문법에 맞는 올바른 식으로 만들기 위해 삽입해야 하는 문자의 최소 개수를 정수 하나로 출력하세요.