Valid Parenthesis String - ตรวจสอบวงเล็บสมดุลใน C++

ภาพรวมปัญหา

ตรวจสอบนิพจน์ที่มีวงเล็บ (), {}, [] ว่าสมดุล (balanced) หรือไม่

ตัวอย่าง: "()[(){()}]" → Valid, "{[}]" → Invalid

อัลกอริทึม (Stack)

1. วนอ่านตัวอักษรทุกตัว:
   • ถ้าเป็นวงเล็บเปิด (, {, [ → push เข้า stack
   • ถ้าเป็นวงเล็บปิด ), }, ] → pop จาก stack ตรวจสอบว่าคู่ตรงกันหรือไม่
2. จบสตริงแล้วถ้า stack ไม่ว่าง → ไม่สมดุล

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

Input / Output

Input:  "()[(){()}]"
Output: This is Balanced Expression