ตรวจสอบ Balanced Parentheses ใน Expression ใน C++

สมมติมี Expression ที่มี Parentheses ต้องตรวจสอบว่า Balanced หรือไม่ ลำดับคือ (), {}, [] ตัวอย่าง "()[(){()}]" ถูกต้อง แต่ "{[}]" ผิด

ใช้ Stack: Traverse Expression จนหมด

• ถ้าเป็น Opening Bracket (, {, [ ให้ Push เข้า Stack
• ถ้าเป็น Closing Bracket ), }, ] ให้ Pop จาก Stack ตรวจสอบว่าตรงกับ Opening Bracket ที่สอดคล้องหรือไม่

หลังจบ String ถ้า Stack ยังมี Opening Bracket ค้างอยู่ แสดงว่าไม่ Balanced

ตัวอย่างโค้ด 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";
}

ผลลัพธ์

This is Balanced Expression