Chương trình C++ biểu thức cân bằng với thay thế dấu sao

Một biểu thức cân bằng của ngoặc là biểu thức chứa cặp ngoặc đúng thứ tự. Điều này có nghĩa là với mỗi ngoặc mở có một ngoặc đóng theo thứ tự đúng.

Ví dụ:

Biểu thức - {([][]{})({}[]{})}

Kết quả - cân bằng

Giải thích - Mỗi ngoặc mở đều có ngoặc đóng tương ứng, tất cả các cặp ngoặc nằm giữa cặp ngoặc mở/đóng theo cặp.

Kết quả - không cân bằng

Giải thích - Có một số cặp ngoặc không theo thứ tự khiến biểu thức không cân bằng.

Trong bài toán cân bằng biểu thức với thay thế, ta được cho một chuỗi chứa biểu thức các ngoặc '{', '}', '[', ']', '(', ')'. Có vị trí thiếu ngoặc và dấu "*" được đặt thay thế. Ta phải kiểm tra xem khi thay thế tất cả dấu sao bằng ngoặc thích hợp thì biểu thức có thể thành biểu thức hợp lệ hay không.

Ví dụ

Đầu vào - exp = "{[*(*)]}"

Đầu ra - biểu thức có thể cân bằng

Giải thích - Có 2 dấu sao cần thay thế. Sau thay thế thành {[(())]}

Đầu vào - exp = "[(*){}{{}}]"

Đầu ra - biểu thức không thể cân bằng

Giải thích - Có 1 dấu sao cần thay thế. Thay thế * bằng bất kỳ ngoặc nào cũng không thể cân bằng.

Sử dụng ngăn xếp (stack) để kiểm tra. Các phép toán:

• Duyệt từng ký tự của chuỗi biểu thức
• Gặp ngoặc mở '{', '[', '(' → đẩy vào ngăn xếp
• Gặp ngoặc đóng '}', ']', ')' → lấy phần tử đỉnh ngăn xếp, kiểm tra có khớp không. Khớp thì tiếp tục, không khớp thì không cân bằng
• Gặp '*' (có thể là mở hoặc đóng):
  • Thử coi là ngoặc mở: đẩy vào ngăn xếp, gọi đệ quy cho ký tự tiếp theo. Nếu false, thử bước sau
  • Coi là ngoặc đóng: phải khớp với đỉnh ngăn xếp thì pop đỉnh
  • Nếu giá trị đóng của * không khớp mở → không cân bằng
• In kết quả dựa trên kết quả

Ví dụ

#include <bits/stdc++.h>
using namespace std;

int isMatching(char a, char b) {
    if ((a == '{' && b == '}') || (a == '[' && b == ']') || (a == '(' && b == ')') || a == '*')
        return 1;
    return 0;
}

int isBalancedexpression(string s, stack<char> ele, int ind) {
    if (ind == s.length())
        return ele.empty();
    char topEle;
    int res;
    if (s[ind] == '{' || s[ind] == '(' || s[ind] == '[') {
        ele.push(s[ind]);
        return isBalancedexpression(s, ele, ind + 1);
    } else if (s[ind] == '}' || s[ind] == ')' || s[ind] == ']') {
        if (ele.empty())
            return 0;
        topEle = ele.top();
        ele.pop();
        if (!isMatching(topEle, s[ind]))
            return 0;
        return isBalancedexpression(s, ele, ind + 1);
    } else if (s[ind] == '*') {
        stack<char> tmp = ele;
        tmp.push(s[ind]);
        res = isBalancedexpression(s, tmp, ind + 1);
        if (res)
            return 1;
        if (ele.empty())
            return 0;
        ele.pop();
        return isBalancedexpression(s, ele, ind + 1);
    }
}

int main() {
    string s = "{[*(*)]}";
    stack<char> ele;
    if (isBalancedexpression(s, ele, 0))
        cout << "Balanced";
    else
        cout << "Not Balanced";
    return 0;
}

Kết quả đầu ra

Balanced