Máy tính biểu thức

Trung tố                          Hậu tố
3 + 4 * 2                         3 4 2 * +
(3 + 4) * 2                       3 4 + 2 *
3 + 4 * 2 / (1 - 5) ^ 2           3 4 2 * 1 5 - 2 ^ / +
2 ^ 3 ^ 2                         2 3 2 ^ ^        (kết hợp phải: 2^(3^2) = 512)
(2 ^ 3) ^ 2                       2 3 ^ 2 ^        (= 64)

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

#include "stack-so.h"      /* ngăn xếp double, cùng mẫu Bài 22.1 */

typedef enum {
    TINH_OK,
    TINH_THIEU_TOAN_HANG,
    TINH_THUA_TOAN_HANG,
    TINH_CHIA_KHONG,
    TINH_KY_HIEU_LA
} MaTinh;

/* Tính giá trị biểu thức hậu tố, các ký hiệu cách nhau bằng khoảng trắng.
   Kết quả ghi vào *ra khi trả về TINH_OK. */
MaTinh tinh_hau_to(const char *bt, double *ra)
{
    StackSo st;

    stack_khoi_tao(&st);

    const char *p = bt;

    while (*p != '\0') {
        while (*p == ' ' || *p == '\t') ++p;

        if (*p == '\0') break;

        /* Số: bắt đầu bằng chữ số hoặc dấu chấm */
        if ((*p >= '0' && *p <= '9') || *p == '.') {
            char  *het;
            double v = strtod(p, &het);

            if (het == p) return TINH_KY_HIEU_LA;

            if (stack_push(&st, v) != 0) return TINH_THUA_TOAN_HANG;

            p = het;

            continue;
        }

        /* Toán tử hai ngôi */
        char op = *p++;
        double a, b;

        if (stack_pop(&st, &b) != 0) return TINH_THIEU_TOAN_HANG;   /* PHẢI */
        if (stack_pop(&st, &a) != 0) return TINH_THIEU_TOAN_HANG;   /* TRÁI */

        double kq;

        switch (op) {
            case '+': kq = a + b; break;
            case '-': kq = a - b; break;
            case '*': kq = a * b; break;
            case '/':
                if (b == 0.0) return TINH_CHIA_KHONG;
                kq = a / b;
                break;
            case '^': kq = pow(a, b); break;
            default:  return TINH_KY_HIEU_LA;
        }

        if (stack_push(&st, kq) != 0) return TINH_THUA_TOAN_HANG;
    }

    if (stack_pop(&st, ra) != 0)  return TINH_THIEU_TOAN_HANG;
    if (!stack_rong(&st))         return TINH_THUA_TOAN_HANG;

    return TINH_OK;
}

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

#include "stack-char.h"

static int uu_tien(char op)
{
    switch (op) {
        case '^':            return 4;
        case '*': case '/':
        case '%':            return 3;
        case '+': case '-':  return 2;
        default:             return 0;
    }
}

static int ket_hop_phai(char op)
{
    return op == '^';
}

typedef enum { CH_OK, CH_NGOAC_LECH, CH_KY_HIEU_LA, CH_TRAN } MaChuyen;

/* Chuyển trung tố sang hậu tố. Ghi kết quả vào ra, tối đa co byte. */
MaChuyen sang_hau_to(const char *bt, char *ra, size_t co)
{
    StackChar st;
    size_t    k = 0;

    stack_khoi_tao(&st);

    for (const char *p = bt; *p != '\0'; ++p) {
        if (*p == ' ' || *p == '\t') continue;

        /* Số: chép nguyên cả cụm chữ số ra đầu ra */
        if ((*p >= '0' && *p <= '9') || *p == '.') {
            while ((*p >= '0' && *p <= '9') || *p == '.') {
                if (k + 2 >= co) return CH_TRAN;

                ra[k++] = *p++;
            }

            --p;                        /* bù cho ++p của vòng for */
            ra[k++] = ' ';

            continue;
        }

        if (*p == '(') {
            if (stack_push(&st, '(') != 0) return CH_TRAN;

            continue;
        }

        if (*p == ')') {
            int dinh;

            for (;;) {
                if (stack_pop(&st, &dinh) != 0) return CH_NGOAC_LECH;

                if ((char)dinh == '(') break;

                if (k + 2 >= co) return CH_TRAN;

                ra[k++] = (char)dinh;
                ra[k++] = ' ';
            }

            continue;
        }

        if (uu_tien(*p) == 0) return CH_KY_HIEU_LA;

        /* Toán tử: đẩy ra hết những toán tử đang chờ mà phải tính trước */
        int dinh;

        while (stack_peek(&st, &dinh) == 0 && (char)dinh != '(') {
            int u_dinh = uu_tien((char)dinh);
            int u_moi  = uu_tien(*p);

            int phai_lay = ket_hop_phai(*p)
                         ? (u_dinh >  u_moi)      /* kết hợp phải: chỉ lớn hơn */
                         : (u_dinh >= u_moi);     /* kết hợp trái: lớn hơn hoặc bằng */

            if (!phai_lay) break;

            stack_pop(&st, &dinh);

            if (k + 2 >= co) return CH_TRAN;

            ra[k++] = (char)dinh;
            ra[k++] = ' ';
        }

        if (stack_push(&st, *p) != 0) return CH_TRAN;
    }

    /* Đổ nốt ngăn xếp ra */
    int dinh;

    while (stack_pop(&st, &dinh) == 0) {
        if ((char)dinh == '(') return CH_NGOAC_LECH;

        if (k + 2 >= co) return CH_TRAN;

        ra[k++] = (char)dinh;
        ra[k++] = ' ';
    }

    if (k > 0 && ra[k - 1] == ' ') --k;      /* bỏ khoảng trắng thừa cuối */

    ra[k] = '\0';

    return CH_OK;
}

/* Dấu trừ là MỘT NGÔI khi nó đứng ở một trong ba chỗ:
     - đầu biểu thức
     - ngay sau một toán tử khác
     - ngay sau một ngoặc mở                                 */
static int la_mot_ngoi(const char *bt, const char *p)
{
    const char *q = p - 1;

    while (q >= bt && (*q == ' ' || *q == '\t')) --q;

    if (q < bt)      return 1;      /* đầu biểu thức */
    if (*q == '(')   return 1;      /* sau ngoặc mở */
    if (uu_tien(*q)) return 1;      /* sau một toán tử */

    return 0;
}

/* Dùng ký hiệu nội bộ 'u' cho dấu âm một ngôi, độ ưu tiên 5, kết hợp phải.
   Ưu tiên cao hơn ^ nên -2 ^ 2 thành (-2) ^ 2 = 4.
   Nếu muốn theo quy ước toán học -(2 ^ 2) = -4 thì đặt ưu tiên 3.5,
   tức thấp hơn ^ nhưng cao hơn *.                                     */

/* Hàm được đối xử như toán tử một ngôi độ ưu tiên cao nhất.
   Khi gặp tên hàm thì đẩy một mã riêng vào ngăn xếp toán tử.
   Khi gặp ngoặc đóng và đỉnh là một hàm thì lấy nó ra luôn.   */

typedef enum {
    HAM_SIN = 128, HAM_COS, HAM_TAN,
    HAM_SQRT, HAM_LOG, HAM_LN, HAM_ABS
} MaHam;

static int doc_ham(const char **p)
{
    static const struct { const char *ten; int ma; } bang[] = {
        { "sqrt", HAM_SQRT }, { "sin", HAM_SIN }, { "cos", HAM_COS },
        { "tan",  HAM_TAN  }, { "log", HAM_LOG }, { "ln",  HAM_LN  },
        { "abs",  HAM_ABS  },
    };

    for (size_t i = 0; i < sizeof bang / sizeof bang[0]; ++i) {
        size_t n = strlen(bang[i].ten);

        if (strncmp(*p, bang[i].ten, n) == 0) {
            *p += n;

            return bang[i].ma;
        }
    }

    return 0;
}

typedef struct {
    MaChuyen ma;
    size_t   vi_tri;      /* chỉ số ký tự gây lỗi */
    char     chi_tiet[64];
} Loi;

static const char *mo_ta(MaChuyen m)
{
    switch (m) {
        case CH_OK:          return "khong loi";
        case CH_NGOAC_LECH:  return "ngoac khong khop";
        case CH_KY_HIEU_LA:  return "ky hieu khong hieu duoc";
        case CH_TRAN:        return "bieu thuc qua dai";
        default:             return "loi khong ro";
    }
}

void in_loi(const char *bt, const Loi *l)
{
    fprintf(stderr, "loi: %s\n", mo_ta(l->ma));
    fprintf(stderr, "  %s\n", bt);
    fprintf(stderr, "  %*s^\n", (int)l->vi_tri, "");

    if (l->chi_tiet[0] != '\0')
        fprintf(stderr, "  %s\n", l->chi_tiet);
}

/* Bảng biến đơn giản, tìm tuyến tính là đủ với vài chục biến. */
typedef struct { char ten[16]; double gia_tri; } Bien;

typedef struct { Bien d[64]; size_t n; } BangBien;

int bb_dat(BangBien *b, const char *ten, double v)
{
    for (size_t i = 0; i < b->n; ++i)
        if (strcmp(b->d[i].ten, ten) == 0) { b->d[i].gia_tri = v; return 0; }

    if (b->n == sizeof b->d / sizeof b->d[0]) return -1;

    snprintf(b->d[b->n].ten, sizeof b->d[b->n].ten, "%s", ten);
    b->d[b->n].gia_tri = v;
    ++b->n;

    return 0;
}

int bb_lay(const BangBien *b, const char *ten, double *ra)
{
    for (size_t i = 0; i < b->n; ++i)
        if (strcmp(b->d[i].ten, ten) == 0) { *ra = b->d[i].gia_tri; return 0; }

    return -1;
}