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