Kiểm tra dấu ngoặc hợp lệ trong C++

Cho biểu thức chứa dấu ngoặc. Kiểm tra các cặp ngoặc có cân bằng không. Các loại: (), {}, []. Ví dụ: "()[(){()}]" hợp lệ, "{[}]" không hợp lệ.

Thuật toán dùng Stack

1. Duyệt biểu thức
2. Nếu gặp ngoặc mở (, {, [ → push vào stack
3. Nếu gặp ngoặc đóng ), }, ] → pop từ stack, kiểm tra có khớp không
4. Sau khi duyệt xong: nếu stack còn phần tử → không cân bằng

Chương trình C++

#include <iostream> 
#include <stack> 
using namespace std; 

bool isBalancedExp(string exp) {
    stack<char> stk;
    char x;
    for (int i = 0; i < exp.length(); i++) {
        if (exp[i] == '(' || exp[i] == '[' || exp[i] == '{') {
            stk.push(exp[i]);
            continue;
        }
        if (stk.empty()) return false;
        switch (exp[i]) {
            case ')':
                x = stk.top(); stk.pop();
                if (x == '{' || x == '[') return false;
                break;
            case '}':
                x = stk.top(); stk.pop();
                if (x == '(' || x == '[') return false;
                break;
            case ']':
                x = stk.top(); stk.pop();
                if (x == '(' || x == '{') return false;
                break;
        }
    }
    return stk.empty();
}

int main() {
    string expresion = "()[(){()}]";
    if (isBalancedExp(expresion))
        cout << "This is Balanced Expression";
    else
        cout << "This is Not Balanced Expression";
}

Kết quả

This is Balanced Expression

Độ phức tạp

• Thời gian: O(n)
• Không gian: O(n) cho stack