Số dấu ngoặc đơn tối thiểu cần thêm để chuỗi hợp lệ trong C++

Đề bài

Cho một chuỗi dấu ngoặc đơn. Có thể chứa dấu ngoặc mở '(' hoặc đóng ')'. Chúng ta phải tìm số dấu ngoặc đơn tối thiểu để chuỗi dấu ngoặc kết quả hợp lệ.

Ví dụ

Nếu str = "((()" thì cần 2 dấu ngoặc đóng '))' ở cuối chuỗi.

Thuật toán

• Đếm dấu ngoặc mở
• Đếm dấu ngoặc đóng
• Dấu ngoặc cần = abs(số ngoặc mở - số ngoặc đóng)

Ví dụ

#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int requiredParentheses(string str) {
    int openingParentheses = 0, closingParentheses = 0;
    for (int i = 0; i < str.length(); ++i) {
        if (str[i] == '(') {
            ++openingParentheses;
        } else if (str[i] == ')') {
            ++closingParentheses;
        }
    }
    return abs(openingParentheses - closingParentheses);
}
int main() {
    string str = "((()";
    cout << "Dấu ngoặc cần = " << requiredParentheses(str) << endl;
    return 0;
}

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau:

Dấu ngoặc cần = 2