14.4 stack

จานในโรงอาหารวางซ้อนกันเป็นตั้ง จานที่ล้างเสร็จวางไว้บนสุด คนมาหยิบก็หยิบจากบนสุด จานที่วางทีหลังจึงถูกหยิบออกก่อน ของที่เก็บแบบนี้เรียกว่า stack (กองซ้อน) หลักของมันมีชื่อว่า LIFO ย่อมาจาก last in, first out คือเข้าทีหลัง ออกก่อน

stack ฟังดูง่ายจนไม่น่าต้องมีชื่อเรียก แต่โจทย์จำนวนมากที่ดูไม่เกี่ยวกัน กลับแก้ได้ด้วย stack ทั้งนั้น เช่น ปุ่ม undo ที่ย้อนสิ่งที่ทำล่าสุดก่อน ตรวจว่าวงเล็บในสูตรเปิดปิดถูกคู่ไหม และคำนวณนิพจน์ทางคณิตศาสตร์ ในหน้า 9.1 น้องเห็น stack มาแล้วหนึ่งตัว คือ call stack ที่เก็บฟังก์ชันที่เรียกซ้อนกัน

งานของ stack

ทุกงานทำที่ด้านบนด้านเดียว ไม่มีการแตะของที่อยู่ข้างล่าง จึงเก็บด้วยอาเรย์ได้ง่ายมาก ให้ช่อง 0 เป็นก้นตั้ง และใช้ตัวแปร size นับว่ามีของกี่ชิ้น ของบนสุดจึงอยู่ช่อง size - 1 เสมอ และช่องว่างช่องถัดไปคือช่อง size

stack ด้วยอาเรย์

เก็บอาเรย์กับ size ไว้นอก main แล้วเขียนแต่ละงานเป็นฟังก์ชันสั้นๆ ฟังก์ชันใช้ตัวแปร global ได้โดยไม่ต้องส่งเข้าไป ตามที่เห็นในหน้า 8.4

#include <stdio.h>

int stack[100000];
int size = 0;

void push(int x)
{
    stack[size] = x; // (1)!
    size++;
}

int pop(void)
{
    size--; // (2)!
    return stack[size];
}

int top(void)
{
    return stack[size - 1];
}

int is_empty(void)
{
    return size == 0;
}

int main()
{
    push(11);
    push(12);
    push(13);
    printf("top = %d\n", top());
    printf("pop = %d\n", pop());
    printf("pop = %d\n", pop());
    push(14);
    printf("size = %d\n", size);
    while (!is_empty()) { // (3)!
        printf("pop = %d\n", pop());
    }
    return 0;
}

1. ใส่ลงช่องว่างช่องแรก คือช่อง size แล้วค่อยเพิ่ม size เขียนแยกสองบรรทัดตามที่หน้า 1.2 แนะนำ ไม่รวบเป็น stack[size++]
2. ลด size ก่อน ช่อง size ใหม่จึงเป็นของบนสุดพอดี ค่าในช่องนั้นยังค้างอยู่ แต่ถือว่าไม่อยู่ใน stack แล้ว เหมือนตอนลบในหน้า 5.5
3. หยิบจนหมดตั้ง ได้ของออกมาในลำดับกลับกันกับที่วาง

top = 13
pop = 13
pop = 12
size = 2
pop = 14
pop = 11

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

stack ทำด้วย linked list ก็ได้ push คือ push_front ในหน้า 14.1 และ pop คือลบตัวหัวแบบในหน้า 14.2 ใช้เมื่อไม่รู้ล่วงหน้าว่าจะมีของมากสุดกี่ชิ้น แต่ในโจทย์แข่งขันขอบเขตบอกไว้เสมอ แบบอาเรย์จึงพอและเขียนสั้นกว่า

กลับตัวอักษรในแต่ละคำ

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

#include <stdio.h>

char stack[101];
int size = 0;

void push(char c)
{
    stack[size] = c;
    size++;
}

char pop(void)
{
    size--;
    return stack[size];
}

int main()
{
    char word[101];
    int first = 1;
    while (scanf("%100s", word) == 1) {
        for (int i = 0; word[i] != '\0'; i++) {
            push(word[i]);
        }
        if (!first) {
            printf(" ");
        }
        first = 0;
        while (size > 0) {
            printf("%c", pop());
        }
    }
    printf("\n");
    return 0;
}

stack is last in first out

kcats si tsal ni tsrif tuo

ตัวเลขใน %100s คือจำนวนตัวอักษรมากสุดที่ scanf จะเก็บลง word ต่อครั้ง ตั้งให้น้อยกว่าขนาดอาเรย์หนึ่งช่องเพื่อเหลือที่ให้ '\0' คำที่ยาวเกินจึงไม่เขียนเลยท้ายอาเรย์

ตรวจวงเล็บ

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

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

#include <stdio.h>

char stack[100001];
int size = 0;

char opening_of(char c) // (1)!
{
    if (c == ')') {
        return '(';
    } else if (c == ']') {
        return '[';
    }
    return '{';
}

int is_balanced(char s[])
{
    size = 0; // (2)!
    for (int i = 0; s[i] != '\0'; i++) {
        char c = s[i];
        if (c == '(' || c == '[' || c == '{') {
            stack[size] = c;
            size++;
        } else {
            if (size == 0) { // (3)!
                return 0;
            }
            if (stack[size - 1] != opening_of(c)) {
                return 0;
            }
            size--;
        }
    }
    return size == 0; // (4)!
}

int main()
{
    char s[100001];
    while (scanf("%100000s", s) == 1) {
        if (is_balanced(s)) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }
    return 0;
}

1. บอกว่าวงเล็บปิดแต่ละตัวต้องคู่กับวงเล็บเปิดตัวไหน
2. เริ่ม stack ว่างใหม่ทุกครั้ง ถ้าลืม ของที่ค้างจากบรรทัดก่อนจะมาปนกับบรรทัดนี้
3. เช็กว่าง ก่อน ดูตัวบนสุดเสมอ ถ้า stack ว่างแล้วไปอ่าน stack[size - 1] คือ stack[-1] ซึ่งไม่มีอยู่จริง
4. ปิดครบทุกตัวหรือยัง

{[()()]}
([)]
(()
())
)(

YES
NO
NO
NO
NO

สี่บรรทัดหลังผิดคนละแบบ ([)] คู่ผิดชนิด (() เหลือวงเล็บเปิด ()) ปิดตอน stack ว่าง และ )( มีวงเล็บเปิดปิดเท่ากันแต่ผิดลำดับ ชุดทดสอบของโจทย์แนวนี้มีครบทุกแบบเสมอ ทดสอบของตัวเองให้ครบด้วย

คำนวณ postfix

นิพจน์ที่เราเขียนกันปกติ เช่น (8 + 2 * 5) / (1 + 3 * 2 - 4) เรียกว่า infix คือเครื่องหมายอยู่ระหว่างตัวเลข ต้องรู้ลำดับคูณก่อนบวก และต้องมีวงเล็บ คอมพิวเตอร์คำนวณตรงๆ ได้ยาก อีกแบบหนึ่งคือ postfix ที่เขียนเครื่องหมายไว้หลังตัวเลขสองตัวที่มันใช้ นิพจน์เดียวกันเขียนเป็น postfix ได้ว่า

8 2 5 * + 1 3 2 * + 4 - /

postfix ไม่ต้องมีวงเล็บ และไม่ต้องจำลำดับการคำนวณเลย อ่านจากซ้ายไปขวาด้วย stack ตามกฎสองข้อ

1. เจอตัวเลข push
2. เจอเครื่องหมาย pop สองครั้ง ตัวที่ออกมาก่อนคือตัวขวา ตัวที่ออกทีหลังคือตัวซ้าย คำนวณ ซ้าย เครื่องหมาย ขวา แล้ว push ผลกลับ

อ่านครบแล้วจะเหลือค่าเดียวใน stack คือคำตอบ

โปรแกรมอ่านทีละคำด้วย %s เพราะตัวเลขมีหลายหลักได้ ถ้าตัวแรกของคำเป็นเลขโดด แปลงทั้งคำเป็นตัวเลขแบบหน้า 6.1 ถ้าไม่ใช่ก็เป็นเครื่องหมาย ใช้ long long เพราะผลคูณต่อกันหลายครั้งโตเร็ว

#include <stdio.h>

long long stack[1000];
int size = 0;

void push(long long x)
{
    stack[size] = x;
    size++;
}

long long pop(void)
{
    size--;
    return stack[size];
}

int main()
{
    char token[20];
    while (scanf("%19s", token) == 1) {
        if (token[0] >= '0' && token[0] <= '9') {
            long long number = 0;
            for (int i = 0; token[i] != '\0'; i++) {
                number = number * 10 + (token[i] - '0');
            }
            push(number);
        } else {
            long long right = pop(); // (1)!
            long long left = pop();
            if (token[0] == '+') {
                push(left + right);
            } else if (token[0] == '-') {
                push(left - right);
            } else if (token[0] == '*') {
                push(left * right);
            } else {
                push(left / right);
            }
        }
    }
    printf("%lld\n", pop());
    return 0;
}

1. ตัวที่ push ทีหลังออกก่อน ตัวแรกที่ pop ได้จึงเป็นตัวขวา บวกกับคูณสลับกันได้ แต่ลบกับหารสลับไม่ได้

8 2 5 * + 1 3 2 * + 4 - /

6

การหารใช้ / ของภาษา C ตรงๆ จึงตัดเศษทิ้งไปทาง 0 แบบหน้า 1.2 ถ้าโจทย์กำหนดการหารแบบอื่นต้องเขียนเพิ่มเอง

ลองทำให้พัง

แบบที่ 1 pop ตัวซ้ายก่อน

ในโปรแกรม postfix สลับสองบรรทัดเป็น long long left = pop(); แล้วตามด้วย long long right = pop(); ป้อนนิพจน์ 10 2 - ซึ่งควรได้ 8

#include <stdio.h>

long long stack[1000];
int size = 0;

void push(long long x)
{
    stack[size] = x;
    size++;
}

long long pop(void)
{
    size--;
    return stack[size];
}

int main()
{
    char token[20];
    while (scanf("%19s", token) == 1) {
        if (token[0] >= '0' && token[0] <= '9') {
            long long number = 0;
            for (int i = 0; token[i] != '\0'; i++) {
                number = number * 10 + (token[i] - '0');
            }
            push(number);
        } else {
            long long left = pop();
            long long right = pop();
            if (token[0] == '+') {
                push(left + right);
            } else if (token[0] == '-') {
                push(left - right);
            } else if (token[0] == '*') {
                push(left * right);
            } else {
                push(left / right);
            }
        }
    }
    printf("%lld\n", pop());
    return 0;
}

10 2 -

-8

ได้ 2 - 10 แทน 10 - 2 บั๊กนี้หลบได้ถ้าทดสอบแค่ 3 4 + หรือ 3 4 * เพราะบวกกับคูณสลับข้างแล้วได้เท่าเดิม ทดสอบเครื่องหมายลบและหารด้วยเสมอ

แบบที่ 2 pop ตอน stack ว่าง

โปรแกรม postfix เชื่อว่าข้อมูลเข้าถูกต้องเสมอ ลองป้อนนิพจน์ที่ผิด เช่น 3 + ที่มีตัวเลขไม่พอ หรือ 2 3 ที่ไม่มีเครื่องหมาย บนเครื่องที่เขียนเอกสารนี้ 3 + ได้ 3 และ 2 3 ได้ 3 ไม่มี error ไม่พัง ดูเหมือนคำตอบปกติ

กรณี 3 + pop ครั้งที่สองเกิดตอน size เป็น 0 จึงลดเป็น -1 แล้วอ่าน stack[-1] ซึ่งอยู่นอกอาเรย์ บนเครื่องนี้ตรงนั้นบังเอิญเป็น 0 จึงได้ 0 + 3 แต่จะเป็นค่าอะไรก็ได้ตามหน้า 5.5 กรณี 2 3 ไม่มีอะไรผิดกฎของภาษา แค่ printf หยิบตัวบนสุดคือ 3 ออกมา แล้วไม่มีใครสังเกตว่ายังมี 2 ค้างอยู่

ถ้าโจทย์รับประกันว่าข้อมูลเข้าถูกต้อง ไม่ต้องเช็กก็ได้ แต่ถ้าโจทย์ให้บอกว่านิพจน์ถูกหรือผิด หรือเวลาที่หาบั๊กของตัวเองไม่เจอ ให้เช็กก่อน pop ทุกครั้งแบบนี้

#include <stdio.h>

long long stack[1000];
int size = 0;

void push(long long x)
{
    stack[size] = x;
    size++;
}

long long pop(void)
{
    size--;
    return stack[size];
}

int main()
{
    char token[20];
    while (scanf("%19s", token) == 1) {
        if (token[0] >= '0' && token[0] <= '9') {
            long long number = 0;
            for (int i = 0; token[i] != '\0'; i++) {
                number = number * 10 + (token[i] - '0');
            }
            push(number);
        } else {
            if (size < 2) { // (1)!
                printf("invalid: not enough numbers for %s\n", token);
                return 0;
            }
            long long right = pop();
            long long left = pop();
            if (token[0] == '+') {
                push(left + right);
            } else if (token[0] == '-') {
                push(left - right);
            } else if (token[0] == '*') {
                push(left * right);
            } else {
                push(left / right);
            }
        }
    }
    if (size != 1) { // (2)!
        printf("invalid: %d numbers left\n", size);
        return 0;
    }
    printf("%lld\n", pop());
    return 0;
}

1. เครื่องหมายต้องการตัวเลขสองตัว ถ้ามีไม่ถึง หยุดเลย return 0; ใน main คือจบโปรแกรม
2. อ่านครบแล้วต้องเหลือค่าเดียวพอดี

3 +

invalid: not enough numbers for +

อีกด้านหนึ่งคือ push ตอนอาเรย์เต็ม ซึ่งจะเขียนเลยท้ายอาเรย์ไปทับของอื่น ผลเหมือนอาการที่ 2 ในหน้า 5.5 วิธีป้องกันคือคิดจากขอบเขตของโจทย์ว่า stack สูงได้มากสุดเท่าไร แล้วประกาศอาเรย์ให้พอ เช่น ตรวจวงเล็บของสตริงยาวแสนตัว stack สูงได้ถึงแสนเมื่อทุกตัวเป็นวงเล็บเปิด โปรแกรม brackets จึงประกาศ 100001 ช่อง ถ้าคิดแล้วไม่แน่ใจ ให้ push เช็ก size กับขนาดอาเรย์ก่อนใส่

สรุป

• stack เข้าทีหลังออกก่อน ทุกงานทำที่ด้านบนด้านเดียว
• ทำด้วยอาเรย์กับ size push ใส่ช่อง size แล้วเพิ่ม pop ลด size แล้วอ่านช่อง size ตัวบนสุดคือช่อง size - 1
• ใช้เมื่อต้องจับคู่กับ "ตัวล่าสุดที่ยังค้างอยู่" เช่น วงเล็บ หรือเมื่อต้องย้อนลำดับ
• ตรวจวงเล็บ เช็ก stack ว่างก่อนดูตัวบนสุด และจบแล้ว stack ต้องว่าง
• postfix pop ได้ตัวขวาก่อนตัวซ้าย ทดสอบเครื่องหมายลบและหารเสมอ
• pop ตอนว่างอาจไม่พังแต่ได้ค่ามั่ว ถ้าข้อมูลเข้าอาจผิด ต้องเช็ก size ก่อน