Ứng dụng của ngăn xếp

#include <stdio.h>
#include <string.h>

#include "stack.h"

/* Trả về ngoặc mở tương ứng, hoặc 0 nếu c không phải ngoặc đóng. */
static char mo_tuong_ung(char c)
{
    switch (c) {
        case ')': return '(';
        case ']': return '[';
        case '}': return '{';
        default:  return 0;
    }
}

/* Trả về 1 nếu chuỗi có ngoặc cân đối, 0 nếu không.
   Nếu vi_tri khác NULL thì ghi vào đó chỉ số ký tự gây lỗi, hoặc -1. */
int ngoac_hop_le(const char *s, long *vi_tri)
{
    Stack st;

    stack_khoi_tao(&st);

    for (long i = 0; s[i] != '\0'; ++i) {
        char c = s[i];

        if (c == '(' || c == '[' || c == '{') {
            if (stack_push(&st, c) != 0) {          /* quá sâu */
                if (vi_tri) *vi_tri = i;

                return 0;
            }
        } else {
            char can = mo_tuong_ung(c);

            if (can == 0) continue;                  /* không phải ngoặc */

            int mo;

            if (stack_pop(&st, &mo) != 0) {          /* thừa ngoặc đóng */
                if (vi_tri) *vi_tri = i;

                return 0;
            }

            if ((char)mo != can) {                   /* sai loại ngoặc */
                if (vi_tri) *vi_tri = i;

                return 0;
            }
        }
    }

    if (!stack_rong(&st)) {                          /* thừa ngoặc mở */
        if (vi_tri) *vi_tri = (long)strlen(s);

        return 0;
    }

    if (vi_tri) *vi_tri = -1;

    return 1;
}

#include <stdio.h>

int ngoac_hop_le(const char *s, long *vi_tri);

int main(void)
{
    const char *thu[] = {
        "(a + b) * [c - d]",
        "{ if (x) { y[0] = 1; } }",
        "(a + b))",
        "([)]",
        "((a + b)",
        "",
        "khong co ngoac nao",
    };

    for (size_t i = 0; i < sizeof thu / sizeof thu[0]; ++i) {
        long vt;
        int  ok = ngoac_hop_le(thu[i], &vt);

        printf("%-26s %s", thu[i], ok ? "hop le" : "SAI");

        if (!ok) printf(" tai vi tri %ld", vt);

        printf("\n");
    }

    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef enum { TT_CHEN, TT_XOA } LoaiTT;

typedef struct {
    LoaiTT loai;
    size_t vi_tri;
    char   ky_tu;
} ThaoTac;

typedef struct {
    ThaoTac *d;
    size_t   n, cap;
} NganXep;

typedef struct {
    char    van_ban[256];
    size_t  do_dai;
    NganXep da_lam;      /* các thao tác đã thực hiện */
    NganXep da_hoan;     /* các thao tác vừa hoàn tác */
} TrinhSoan;

static int nx_push(NganXep *s, ThaoTac t)
{
    if (s->n == s->cap) {
        size_t moi = s->cap ? s->cap * 2 : 8;
        ThaoTac *tam = realloc(s->d, moi * sizeof *tam);

        if (tam == NULL) return -1;

        s->d = tam; s->cap = moi;
    }

    s->d[s->n++] = t;

    return 0;
}

static int nx_pop(NganXep *s, ThaoTac *ra)
{
    if (s->n == 0) return -1;

    *ra = s->d[--s->n];

    return 0;
}

static void nx_xoa_het(NganXep *s) { s->n = 0; }

/* Thực hiện một thao tác lên văn bản, không đụng tới ngăn xếp. */
static void ap_dung(TrinhSoan *ts, ThaoTac t)
{
    if (t.loai == TT_CHEN) {
        memmove(ts->van_ban + t.vi_tri + 1,
                ts->van_ban + t.vi_tri,
                ts->do_dai - t.vi_tri + 1);

        ts->van_ban[t.vi_tri] = t.ky_tu;
        ++ts->do_dai;
    } else {
        memmove(ts->van_ban + t.vi_tri,
                ts->van_ban + t.vi_tri + 1,
                ts->do_dai - t.vi_tri);

        --ts->do_dai;
    }
}

/* Thao tác nghịch đảo của t. */
static ThaoTac nghich_dao(ThaoTac t)
{
    t.loai = (t.loai == TT_CHEN) ? TT_XOA : TT_CHEN;

    return t;
}

int ts_chen(TrinhSoan *ts, size_t vi_tri, char c)
{
    if (vi_tri > ts->do_dai || ts->do_dai + 1 >= sizeof ts->van_ban) return -1;

    ThaoTac t = { TT_CHEN, vi_tri, c };

    if (nx_push(&ts->da_lam, t) != 0) return -1;

    ap_dung(ts, t);
    nx_xoa_het(&ts->da_hoan);      /* thao tác mới xóa lịch sử làm lại */

    return 0;
}

int ts_hoan_tac(TrinhSoan *ts)
{
    ThaoTac t;

    if (nx_pop(&ts->da_lam, &t) != 0) return -1;

    ap_dung(ts, nghich_dao(t));

    return nx_push(&ts->da_hoan, t);
}

int ts_lam_lai(TrinhSoan *ts)
{
    ThaoTac t;

    if (nx_pop(&ts->da_hoan, &t) != 0) return -1;

    ap_dung(ts, t);

    return nx_push(&ts->da_lam, t);
}

/* Bản đệ quy, ngắn và rõ */
void tien_thu_tu_de_quy(const TNode *r)
{
    if (r == NULL) return;

    printf("%d ", r->data);
    tien_thu_tu_de_quy(r->left);
    tien_thu_tu_de_quy(r->right);
}

/* Bản lặp, dùng ngăn xếp con trỏ tường minh */
void tien_thu_tu_lap(const TNode *r)
{
    if (r == NULL) return;

    const TNode *nx[64];
    size_t       n = 0;

    nx[n++] = r;

    while (n > 0) {
        const TNode *cur = nx[--n];

        printf("%d ", cur->data);

        /* Đẩy PHẢI trước để TRÁI được lấy ra trước, đúng thứ tự tiền thứ tự */
        if (cur->right != NULL) nx[n++] = cur->right;
        if (cur->left  != NULL) nx[n++] = cur->left;
    }
}

/* Cái bộ xử lý làm khi bạn gọi hàm */

f();                    /* push địa chỉ dòng kế tiếp, nhảy tới f */
                        /* trong f: push khung, gồm tham số và biến cục bộ */
    g();                /* push tiếp, ngăn xếp sâu thêm một tầng */
                        /* g trả về: pop khung của g, nhảy về địa chỉ đã lưu */
                        /* f trả về: pop khung của f, nhảy về đây */

/* Vì sao đệ quy vô hạn làm tràn ngăn xếp:
   mỗi lời gọi push thêm một khung, không lời gọi nào pop,
   nên vùng ngăn xếp cạn dần cho tới khi chạm giới hạn. */