คำอธิบายปัญหา
สมมติว่าเรามีสมการ (expression) สมการนี้มีวงเล็บบางอย่าง เราต้องตรวจสอบว่าวงเล็บสมดุล (balanced) หรือไม่ ลำดับของวงเล็บคือ (), {} และ [] สมมติมีสตริงสองตัว "()[(){()}]" นี้ถูกต้อง แต่ "{[}]" ไม่ถูกต้อง
งานนี้ง่าย เราจะใช้ stack (แสต็ก) ทำได้ เราควรทำตามขั้นตอนเหล่านี้เพื่อหาคำตอบ:
เดินทางผ่านสมการจนหมด
ถ้าตัวอักษรปัจจุบันเป็นวงเล็บเปิด เช่น (, { หรือ [ ให้ push เข้า stack
ถ้าตัวอักษรปัจจุบันเป็นวงเล็บปิด เช่น ), } หรือ ] ให้ pop จาก stack และตรวจสอบว่าวงเล็บที่ pop ออกมาเป็นวงเล็บเปิดที่ตรงกับตัวปัจจุบันหรือไม่ ถ้าตรงถือว่าโอเค มิฉะนั้นไม่สมดุล
หลังจากสตริงหมด ถ้ายังมีวงเล็บเปิดเหลืออยู่ใน stack แสดงว่าสตริงไม่สมดุล
ตัวอย่างโค้ด
#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
