การตรวจวงเล็บด้วย Stack

นึกภาพก่อน

เวลาเขียนโค้ด วงเล็บ ( ) ปีกกา { } และก้ามปู [ ] ซ้อนกันได้หลายชั้น กฎมีข้อเดียวคือ วงเล็บที่เปิดหลังสุดต้องถูกปิดก่อน

ลองดู ( [ ] ) ตัว [ เปิดทีหลัง ( จึงต้องปิดก่อน ถ้าเขียนเป็น ( [ ) ] ถือว่าผิด แม้จำนวนเปิดและปิดจะเท่ากัน

"เปิดหลังสุด ปิดก่อน" คือ LIFO พอดี จึงใช้ stack จำวงเล็บเปิดที่ยังรอคู่อยู่ได้ แค่นับจำนวนอย่างเดียวไม่พอ เพราะต้องรู้ด้วยว่าตัวที่เปิดค้างไว้ล่าสุดเป็น ชนิดไหน

วิธีทำ

อ่านสตริงทีละตัวจากซ้ายไปขวา:

1. เป็น วงเล็บเปิด → push ลง stack
2. เป็น วงเล็บปิด → pop ตัวบนสุดออกมาตรวจว่าเป็นวงเล็บเปิดชนิดเดียวกันหรือไม่
3. จะ pop แต่ stack ว่าง → วงเล็บปิดมีมากเกินไป
4. อ่านจบแล้ว stack ยังมีข้อมูล → วงเล็บเปิดมีมากเกินไป

ถ้าอ่านจบและ stack ว่างพอดี แปลว่าถูกต้อง

ความผิดพลาด 3 แบบ

สไลด์มีโจทย์จับคู่เรื่องนี้โดยตรง:

• วงเล็บ ปิด มากกว่าเปิด ↔ "pop แต่กองซ้อนว่าง"
• วงเล็บ เปิด มากกว่าปิด ↔ "วนครบ แต่กองซ้อนไม่ว่าง"

โค้ดจากสไลด์

public static boolean checkParentheses(String t) {
  String open = "{([", close = "})]";
  Stack s = new ArrayStack(100);
  for (int i = 0; i < t.length(); i++) {
    String token = t.substring(i, i + 1);
    if (open.indexOf(token) >= 0) {
      s.push(token);
    } else {
      int k = close.indexOf(token);
      if (k >= 0)
        if (s.isEmpty() ||
            !open.substring(k, k + 1).equals(s.pop()))
          return false;
    }
  }
  return s.isEmpty();
}

จุดที่ต้องอ่านให้ออก:

• a.indexOf(b) คืนตำแหน่งใน a ที่พบ b ถ้าไม่พบคืน -1 ดังนั้น open.indexOf(token) >= 0 แปลว่า token เป็นวงเล็บเปิด
• open กับ close เรียงชนิดตรงกัน: ตำแหน่ง 0 คือ { คู่กับ } ตำแหน่ง 1 คือ ( คู่กับ ) ตำแหน่ง 2 คือ [ คู่กับ ] เมื่อพบวงเล็บปิดที่ตำแหน่ง k วงเล็บเปิดที่ถูกต้องจึงเป็น open.substring(k, k + 1)
• s.isEmpty() || ... ถ้า stack ว่าง เงื่อนไขเป็นจริงทันทีโดยไม่เรียก s.pop() (short-circuit) จึงไม่เกิด exception กรณีนี้คือวงเล็บปิดมากกว่าเปิด
• return s.isEmpty(); ท้ายเมท็อดตรวจกรณีวงเล็บเปิดมากกว่าปิด
• ตัวอักษรที่ไม่ใช่วงเล็บ (k < 0) ถูกข้ามไป

ตัวอย่างไล่ทีละขั้น

ตรวจ ({()[{)]}) (ตัวอย่าง ๒ ในสไลด์):

เมท็อดหยุดทันทีที่พบจุดผิด ไม่อ่านส่วนที่เหลือ

Simulation ด้านล่างมีตัวอย่างทั้ง 4 แบบจากสไลด์ และพิมพ์สตริงเองได้

public static boolean checkParentheses(String t) {
  String open = "{([", close = "})]";
  Stack s = new ArrayStack(100);
  for (int i = 0; i < t.length(); i++) {
    String token = t.substring(i, i + 1);
    if (open.indexOf(token) >= 0) {
      s.push(token);
    } else {
      int k = close.indexOf(token);
      if (k >= 0)
        if (s.isEmpty() ||
            !open.substring(k, k + 1).equals(s.pop()))
          return false;
    }
  }
  return s.isEmpty();
}

จุดที่มักพลาด

1. นับจำนวนแทนการใช้ stack

([)] มีเปิด 2 ปิด 2 เท่ากัน แต่ผิด การนับจำนวนจับได้แค่กรณีเปิด/ปิดเกิน จับกรณีไม่ตรงคู่ไม่ได้

2. จับคู่ความผิดพลาดสลับกัน

"pop ตอน stack ว่าง" คือ ปิด เกิน (มีตัวปิดมาแต่ไม่มีตัวเปิดให้จับคู่) ส่วน "อ่านจบแล้ว stack ไม่ว่าง" คือ เปิด เกิน (มีตัวเปิดค้างอยู่ไม่มีใครปิด)

3. ลืมตรวจตอนจบ

ถ้าเมท็อดคืน true ทันทีที่ออกจากลูป สตริงอย่าง (( จะถูกตัดสินว่าถูก ต้องคืน s.isEmpty()

4. สลับลำดับในเงื่อนไข ||

ถ้าเขียน !open.substring(k, k + 1).equals(s.pop()) || s.isEmpty() จะเรียก pop ก่อนตรวจว่าว่าง เมื่อ stack ว่างจะเกิด NoSuchElementException แทนที่จะคืน false

5. push วงเล็บปิดลง stack

stack เก็บเฉพาะวงเล็บเปิด วงเล็บปิดมีหน้าที่แค่ทำให้เกิดการ pop

ที่มา: STACK_5 (1).pdf หน้า 16–25 (ตัวอย่าง ๑–๔ หน้า 18–21, โจทย์จับคู่หน้า 22, โค้ดหน้า 23)