countParentheses

Biểu thức ngoặc là xâu chỉ gồm các ký tự ‘(’ hoặc ‘)’. Biểu thức ngoặc đúng được định nghĩa một cách đệ qui như sau:

• Biểu thức rỗng là biểu thức ngoặc đúng.
• Nếu A là biểu thức ngoặc đúng thì (A) cũng là một biểu thức ngoặc đúng.
• Nếu A và B là hai biểu thức ngoặc đúng thì AB cũng là một biểu thức ngoặc đúng.

Cho s là một xâu chỉ gồm các ký tự ‘(‘, ‘)’ và ‘!’, hãy đếm số cách thay các ký tự ‘!’ trong xâu s thành ký tự ‘(‘ hoặc ‘)’ để nhận được xâu mới là biểu thức ngoặc đúng.

Ví dụ:

• Với s = "(!!!" thì countParentheses(s) = 2. Tập các biểu thức ngoặc đúng có thể tạo được là {"(())", "()()"}.
• Với s = "!!((!)" thì countParentheses(s) = 1 vì chỉ có thể tạo được một biểu thức ngoặc đúng duy nhất là "()(())".

Đầu vào/Đầu ra:

• [Thời gian] 0.5s với C++, 3s với Java và C#, 4s với Python, Go và JavaScript.
• [Đầu vào] String s
  1 ≤ s.size() ≤ 20
• [Đầu ra] Integer
  Số cách thay các ký tự ‘!’ trong xâu s thành ký tự ‘(‘ hoặc ‘)’ để nhận được xâu mới là biểu thức ngoặc đúng.