โปรแกรม C++ ตรวจสอบวงเล็บสมดุลด้วย Stack

ที่นี่เราจะพูดถึงวิธีตรวจสอบวงเล็บที่สมดุลโดยใช้ Stack เราไม่ได้ตรวจสอบแค่วงเล็บเปิดและปิด แต่ยังตรวจสอบลำดับของวงเล็บด้วย ตัวอย่างเช่น นิพจน์ "[{} () {()}]" ถูกต้อง แต่ "{[}]" ไม่ถูกต้อง

Input: นิพจน์มีวงเล็บ "{()}[]"
Output: วงเล็บสมดุล

อัลกอริทึม

ขั้นตอน 1: กำหนด stack เพื่อเก็บวงเล็บ
ขั้นตอน 2: วนลูปนิพจน์จากซ้ายไปขวา
    ขั้นตอน 2.1: ถ้าตัวอักษรเป็นวงเล็บเปิด (, { หรือ [ ให้ push เข้า stack
    ขั้นตอน 2.2: ถ้าตัวอักษรเป็นวงเล็บปิด ), } หรือ ]
        Pop จาก stack และถ้าตัวอักษรที่ pop 出มาตรงกับวงเล็บเปิด ก็ถูกต้อง มิฉะนั้นไม่สมดุล
ขั้นตอน 3: หลังจบการวนลูป ถ้ายังมีวงเล็บเปิดอยู่ใน stack แสดงว่าไม่สมดุล

ตัวอย่างโค้ด

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

bool isBalanced(string expr) {
    stack<char> s;
    char ch;
    
    for (int i=0; i<expr.length(); i++) {
        // ตรวจสอบเงื่อนไขสำหรับแต่ละตัวอักษรในนิพจน์
        if (expr[i]=='('||expr[i]=='['||expr[i]=='{') {
            // เมื่อเป็นวงเล็บเปิด ให้ push เข้า stack
            s.push(expr[i]);
            continue;
        }
        
        if (s.empty())
            // stack ไม่สามารถว่างได้ เพราะไม่ใช่วงเล็บเปิด ต้องมีวงเล็บปิด
            return false;
        
        switch (expr[i]) {
            case ')': // สำหรับวงเล็บปิดโค้ง Pop และตรวจสอบวงเล็บเหลี่ยมและงuffy
                ch = s.top();
                s.pop();
                if (ch=='{' || ch=='[')
                    return false;
                break;
            case '}': // สำหรับวงเล็บปิดเหลี่ยม Pop และตรวจสอบวงเล็บโค้งและงuffy
                ch = s.top();
                s.pop();
                if (ch=='(' || ch=='[')
                    return false;
                break;
            case ']': // สำหรับวงเล็บปิดงuffy Pop และตรวจสอบวงเล็บเหลี่ยมและโค้ง
                ch = s.top();
                s.pop();
                if (ch =='(' || ch == '{')
                    return false;
                break;
        }
    }
    return (s.empty()); // เมื่อ stack ว่าง คืนค่า true
}

main() {
    string expr = "[{}(){()}]";
    if (isBalanced(expr))
        cout << "Balanced";
    else
        cout << "Not Balanced";
}

ผลลัพธ์

Balanced