1497: Xâu ngoặc đơn cân bằng: Mô tả Bessie đang gõ một xâu ngoặc đơn cân bằng vào máy tính, nhưng do không tập trung nên cô ta đã gõ nhầm lẫn một số dấu ngoặc đơn: dấu mở ngoặc thành đóng ngoặc hoặc ngược lại. Hãy giúp cô ta tính xem có bao nhiêu dấu ngoặc đơn trong xâu cần phải được đổi chiều (có nghĩa là đổi dấu mở ngoặc đơn thành dấu đóng ngoặc đơn hoặc ngược lại) để xâu ngoặc đơn ban đầu thành xâu ngoặc đơn cân bằng. Có nhiều cách để định nghĩa một xâu ngoặc đơn là cân bằng. Cách dễ nhất là số lượng dấu mở ngoặc ( bằng số lượng dấu đóng ngoặc ) và với bất kì xâu tiền tố nào, số dấu mở ngoặc đơn ( phải lớn hơn hoặc bằng số dấu đóng ngoặc đơn ). Ví dụ các xâu ngoặc đơn cân bằng: (), (()), ()(()()) và các xâu ngoặc đơn không cân bằng: )(, ())(, ((()))). Dữ liệu vào Gồm một dòng chứa một xâu ngoặc đơn độ dài chẵn và có độ dài tối đa là 105 kí tự. Dữ liệu ra Chứa một số nguyên là số dấu ngoặc đơn nhỏ nhất cần phải được đổi chiều để biến xâu ngoặc đơn ban đầu thành xâu ngoặc đơn cân bằng. Ví dụ dữ liệu vào ())( Ví dụ dữ liệu ra 2