Chương trình C++ kiểm tra dấu ngoặc cân bằng bằng Stack

Ở đây chúng ta sẽ thảo luận cách kiểm tra dấu ngoặc cân bằng sử dụng ngăn xếp (stack). Chúng ta không chỉ kiểm tra dấu ngoặc mở và đóng mà còn kiểm tra thứ tự của các dấu ngoặc. Ví dụ, biểu thức "[{} () {()}]" là đúng, nhưng "{[}]" là không đúng.

Đầu vào: Một biểu thức với dấu ngoặc "{()}[]" 
Đầu ra: Chúng cân bằng

Thuật toán

Bước 1: Định nghĩa một stack để chứa dấu ngoặc
Bước 2: Duyệt biểu thức từ trái sang phải
Bước 2.1: Nếu ký tự là dấu ngoặc mở (, { hoặc [, thì đẩy vào stack
Bước 2.2: Nếu ký tự là dấu ngoặc đóng ), } hoặc ]
    Thì pop từ stack, và nếu ký tự pop được khớp với dấu ngoặc mở tương ứng thì OK.
    Ngược lại thì không cân bằng.
Bước 3: Sau khi duyệt xong, nếu vẫn còn dấu ngoặc mở trong stack thì không cân bằng.

Mã ví dụ

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

bool isBalanced(string expr) { 
    stack<char> s; 
    char ch; 
    for (int i = 0; i < expr.length(); i++) { 
        //với mỗi ký tự trong biểu thức, kiểm tra điều kiện 
        if (expr[i] == '(' || expr[i] == '[' || expr[i] == '{') { 
            //khi là dấu ngoặc mở, đẩy vào stack 
            s.push(expr[i]); 
            continue; 
        } 
        if (s.empty()) 
            //stack không thể rỗng vì không phải dấu ngoặc mở, phải có dấu ngoặc đóng 
            return false; 
        switch (expr[i]) { 
            case ')': 
                //cho dấu ngoặc đóng tròn, pop và kiểm tra ngoặc vuông và nhọn 
                ch = s.top(); 
                s.pop(); 
                if (ch == '{' || ch == '[') 
                    return false; 
                break; 
            case '}': 
                //cho dấu ngoặc đóng nhọn, pop và kiểm tra ngoặc tròn và vuông 
                ch = s.top(); 
                s.pop(); 
                if (ch == '(' || ch == '[') 
                    return false; 
                break; 
            case ']': 
                //cho dấu ngoặc đóng vuông, pop và kiểm tra ngoặc nhọn và tròn 
                ch = s.top(); 
                s.pop(); 
                if (ch == '(' || ch == '{') 
                    return false; 
                break; 
        } 
    } 
    return (s.empty()); //khi stack rỗng, trả về true 
} 

main() { 
    string expr = "[{}(){()}]"; 
    if (isBalanced(expr)) 
        cout << "Cân bằng"; 
    else 
        cout << "Không cân bằng"; 
}

Kết quả

Cân bằng