設置 | 登錄 | 註冊
Purasbar

作者共發了2篇帖子。

【備份】算式解析代碼

1樓 巨大八爪鱼 2016-6-14 22:12
/** 功能1: 算式計算 **/
#include <errno.h>
#include <math.h>
#include <stdio.h>
#include "common.h"
#include "calc.h"

void calc_start(void)
{
    char str[MAXLEN + 1];
    char exp[MAXLEN + 1];
    double value;
    FILE *fp;
    printf("請輸入要計算的數學算式 (不多於%d字符): ", MAXLEN);
    input(str, sizeof(str)); // 輸入算式
    parse(str, exp); // 將算式轉換為逆波蘭表達式
    if (!errno)
        value = evaluate(exp); // 求逆波蘭表達式的值
    switch (errno)
    {
    case NOERR:
        printf("計算結果為: %g\n", value);
        fp = fopen(FILENAME, "a");
        if (fp != NULL)
        {
            fprintf(fp, "%s=%g\n", str, value);
            fclose(fp);
        }
        else
            puts("警告: 保存計算結果失敗");
        break;
    case ERR_MOD:
        puts("表達式有誤: 只能對兩個整數取模");
        break;
    case ERR_ZERODIV:
        puts("表達式有誤: 除數不能為0");
        break;
    case ERR_UDEFOP:
        puts("表達式有誤: 含有無法識別的運算符");
        break;
    case ERR_UDEFFUN:
        puts("表達式有誤: 含有無法識別的函數名");
        break;
    case ERR_BRACMISMATCH:
        puts("表達式有誤: 括號不匹配");
        break;
    case ERR_INVALIDCOMMA:
        puts("表達式有誤: 無效的逗號");
        break;
    case ERR_INVALID:
        puts("表達式不合法");
        break;
    case ERR_PARAMCNTMISMATCH:
        puts("表達式有誤: 函數參數個數不正確");
        break;
    case EDOM:
        puts("表達式有誤: 冪運算的運算數不合法");
        break;
    case ERANGE:
        puts("計算失敗: 冪運算結果太大或太小, 超出了運算能力");
        break;
    default:
        puts("計算失敗: 未知錯誤");
    }
}

// 計算逆波蘭表達式(RPN)的值
// 參考資料: https://en.wikipedia.org/wiki/Reverse_Polish_notation
double evaluate(const char *exp)
{
    double stack[MAXLEN];
    int i = 0; // 棧指針
    int n; // sscanf讀取的字符數
    errno = NOERR;
    while (*exp != '\0')
    {
        if (sscanf(exp, "%lf%n", stack + i, &n) != 1)
        {
            // 遇到運算符就立即從棧中彈出兩個數並作運算
            // 然後丟棄stack[i]的值
            while (*exp == ' ')
                exp++; // 跳過空格
            if (*exp == '\0')
                break;

            /* 單目運算符或函數 */
            if (i <= 0)
                return errno = ERR_INVALID; // 單目運算符至少需要一個運算數
            if (fncmp(exp, "sin"))
                stack[i - 1] = sin(stack[i - 1]);
            else if (fncmp(exp, "cos"))
                stack[i - 1] = cos(stack[i - 1]);
            else if (fncmp(exp, "tan"))
                stack[i - 1] = tan(stack[i - 1]);
            else if (fncmp(exp, "cot"))
            {
                stack[i - 1] = tan(stack[i - 1]);
                if (stack[i - 1] == 0.0)
                    errno = ERR_INVALID;
                else
                    stack[i - 1] = 1 / stack[i - 1];
            }
            else
            {
                /* 雙目運算符或函數 */
                i--;
                if (i <= 0)
                    return errno = ERR_INVALID; // 雙目運算符至少需要兩個運算數
                switch (*exp)
                {
                case '+':
                    stack[i - 1] += stack[i];
                    break;
                case '-':
                    stack[i - 1] -= stack[i];
                    break;
                case 'x':
                case '*':
                    stack[i - 1] *= stack[i];
                    break;
                case '/':
                    if (stack[i] != 0.0)
                        stack[i - 1] /= stack[i];
                    else
                        return errno = ERR_ZERODIV;
                    break;
                case '%':
                    if (stack[i] == (int)stack[i] && stack[i - 1] == (int)stack[i - 1])
                        stack[i - 1] = (int)stack[i - 1] % (int)stack[i];
                    else
                        return errno = ERR_MOD;
                    break;
                case '^':
                    stack[i - 1] = pow(stack[i - 1], stack[i]);
                    if (errno)
                        return errno;
                    break;
                default:
                    if (fncmp(exp, "max"))
                        stack[i - 1] = max(stack[i - 1], stack[i]);
                    else if (fncmp(exp, "min"))
                        stack[i - 1] = min(stack[i - 1], stack[i]);
                    else
                        return errno = ERR_INVALID;
                }
            }
            
            if (!opjmp(NULL, &exp))
                fnjmp(NULL, &exp);
        }
        else
        {
            i++; // 遇到數就將數入棧
            exp += n; // 字符指針前進
        }
    }
    if (i != 1)
        return errno = ERR_INVALID; // 最終棧中只能有且只有一個數據
    return stack[0]; // 將棧中最後一個數作為計算結果返回
}

// 判斷str函數名是否和src相同
// src必須以\0結束, 但str不需要
BOOL fncmp(const char *str, const char *src)
{
    while (*src != '\0')
    {
        if (*str != *src)
            return FALSE;
        str++;
        src++;
    }
    return (BOOL)(!isfn(*str));
}

// 求函數名長度
int fnlen(const char *fn)
{
    int n = 0;
    while (isfn(*fn)) // 宏調用中不能出現自增自減運算符
    {
        fn++;
        n++;
    }
    return n;
}

// 跳過或複製指定數量的字符, 並在末尾添加空格
BOOL jmp(char **dest, const char **src, int len)
{
    if (len <= 0)
        return FALSE;
    if (dest != NULL)
    {
        while (len--)
            *(*dest)++ = *(*src)++;
        *(*dest)++ = ' ';
    }
    else
        *src += len;
    return TRUE;
}

// 求運算符的長度
int oplen(const char *op)
{
    switch (*op)
    {
    case '+':
    case '-':
    case '*':
    case 'x':
    case '/':
    case '%':
    case '^':
        return 1;
    default:
        return -1; // 未知長度
    }
}

// 求函數的參數個數
int paramcnt(const char *fn)
{
    if (fncmp(fn, "sin") || fncmp(fn, "cos") || fncmp(fn, "tan") || fncmp(fn, "cot"))
        return 1;
    else if (fncmp(fn, "max") || fncmp(fn, "min"))
        return 2;
    else
        return -1; // 函數不存在
}

// 將數學表達式轉換為逆波蘭表達式
// 參考資料: https://en.wikipedia.org/wiki/Shunting-yard_algorithm
UINT parse(const char *str, char *buf)
{
    BOOL addzero = TRUE; // 是否需要添0
    char left;
    const char *cp; // 臨時用字符串指針
    const char *stack[MAXLEN]; // 運算符及函數名棧, 棧中運算符的優先級必須是從低到高
    int comma_cnt = 0; // 逗號個數
    int i = 0; // 棧指針
    UINT prec, prec2; // 運算符的優先級碼
    errno = NOERR;
    while (*str != '\0')
    {
        while (*str == ' ')
            str++; // 跳過空格

        if (isnum(*str))
        {
            // 如果讀到數字，則直接輸出
            do
            {
                *buf++ = *str++;
            } while (isnum(*str));
            *buf++ = ' ';
            addzero = FALSE;
        }
        else if (isleftbrac(*str))
        {
            // 如果讀到左括號, 則無條件入棧
            stack[i++] = str++;
            addzero = TRUE;
        }
        else if (*str == ')' || *str == ']' || *str == '}')
        {
            // 如果讀到右括號
            switch (*str)
            {
            case ')':
                left = '(';
                break;
            case ']':
                left = '[';
                break;
            case '}':
                left = '{';
                break;
            }
            // ch為對應的左括號
            comma_cnt = 0;
            while (i > 0 && *stack[i - 1] != left)
            {
                // 彈出所有運算符和函數名
                cp = stack[--i];
                if (*cp == ',')
                    comma_cnt++;
                else if (!opjmp(&buf, &cp))
                    fnjmp(&buf, &cp);
            }
            if (i > 0)
            {
                i--; // 括號匹配, 左括號出棧
                while (i > 0)
                {
                    cp = stack[i - 1];
                    if (fnjmp(&buf, &cp))
                    {
                        i--; // 如果頂層是函數名, 則函數名出棧
                        if (paramcnt(stack[i]) != comma_cnt + 1)
                            return errno = ERR_PARAMCNTMISMATCH; // 函數參數個數不匹配, 退出
                    }
                    else
                        break;
                }
            }
            else
                return errno = ERR_BRACMISMATCH; // 括號不匹配, 退出
            str++;
        }
        else if (*str == ',')
        {
            // 如果讀到逗號
            while (i > 0 && !isleftbrac(stack[i - 1][0]))
            {
                // 彈出最近括號後的所有運算符
                cp = stack[--i];
                if (!opjmp(&buf, &cp))
                    fnjmp(&buf, &cp);
            }
            if (i <= 0)
                return errno = ERR_INVALIDCOMMA;
            stack[i++] = str++; // 逗號入棧, 便於檢查函數參數個數是否正確
            addzero = TRUE;
        }
        else if (isop(str))
        {
            // 如果讀到運算符
            prec = precedence(str);
            while (i > 0)
            {
                if (isop(stack[i - 1]))
                {
                    // 如果棧頂是運算符
                    prec2 = precedence(stack[i - 1]);
                    if ((!(prec & OP_RIGHTASSOCIATIVE) && OP_PREC(prec) <= OP_PREC(prec2)) || ((prec & OP_RIGHTASSOCIATIVE) && OP_PREC(prec) < OP_PREC(prec2))) // 比較兩個運算符的優先級
                    {
                        // 不斷地彈出棧頂的更高優先級運算符
                        cp = stack[--i];
                        opjmp(&buf, &cp);
                    }
                    else
                        break; // 優先級更高的運算符已經全部彈出了, 此時該運算符可以入棧了
                }
                else if (isfn(stack[i - 1][0]))
                {
                    // 遇到運算符時, 棧中的函數名無條件彈出
                    cp = stack[--i];
                    if (fnjmp(&buf, &cp))
                    {
                        if (paramcnt(stack[i]) != 1)
                            return errno = ERR_PARAMCNTMISMATCH; // 不使用括號時, 函數參數個數必須為1
                    }
                }
                else
                    break; // 如果棧頂是括號、逗號或其他內容, 則不彈出
            }
            if (addzero && (*str == '+' || *str == '-'))
            {
                // 最左邊出現符號, 則添0
                *buf++ = '0';
                *buf++ = ' ';
                addzero = FALSE;
            }
            // 將運算符入棧
            stack[i++] = str;
            if (!opjmp(NULL, &str)) // 跳過運算符剩下的字符, 防止入棧
                return errno = ERR_UDEFOP; // 運算符不存在, 退出
        }
        else if (isfn(*str))
        {
            // 如果讀到函數名, 則無條件將指向該函數名首字符的指針入棧
            if (paramcnt(str) == -1)
                return errno = ERR_UDEFFUN; // 函數不存在, 退出
            stack[i++] = str;
            fnjmp(NULL, &str);
        }
        else
            return errno = ERR_UDEFOP;
    }

    // 將棧中剩餘的內容全部彈出
    while (i > 0)
    {
        cp = stack[--i];
        if (isleftbrac(*cp)) // 剩餘內容中不能有多餘的括號
            return errno = ERR_BRACMISMATCH;
        if (!opjmp(&buf, &cp))
        {
            if (fnjmp(&buf, &cp))
            {
                if (paramcnt(stack[i]) != 1)
                    return errno = ERR_PARAMCNTMISMATCH; // 不使用括號時, 函數參數個數必須為1
            }
            else
                return errno = ERR_INVALID;
        }
    }
    *buf = '\0';
    return NOERR;
}

// 求運算符的優先級碼
// 返回值高四位表示優先級, 低四位的最高位表示是左結合(0)還是右結合(1)
UINT precedence(const char *op)
{
    switch (*op)
    {
    case '+':
        return 0x20;
    case '-':
        return 0x21;
    case '*':
    case 'x':
        return 0x30;
    case '/':
        return 0x31;
    case '%':
        return 0x32;
    case '^':
        return 0x48;
    default:
        return 0xf0; // 默認左結合, 最高優先級
    }
}
2樓 巨大八爪鱼 2016-6-14 22:13
#define isfn(ch) ((ch) == '_' || ((ch) >= 'A' && (ch) <= 'Z') || ((ch) >= 'a' && (ch) <= 'z'))
#define isleftbrac(ch) ((ch) == '(' || (ch) == '[' || (ch) == '{')
#define isnum(ch) (((ch) >= '0' && (ch) <= '9') || (ch) == '.') // 判斷字符是否為數字或小數點
#define isop(str) (oplen(str) > 0)

#define max(a, b) (((a) > (b)) ? (a) : (b))
#define min(a, b) (((a) < (b)) ? (a) : (b))

#define fnjmp(dest, src) jmp((dest), (src), fnlen(*src))
#define opjmp(dest, src) jmp((dest), (src), oplen(*src))

#define OP_PREC(code) ((code) >> 4)
#define OP_RIGHTASSOCIATIVE 0x08

void calc_start(void);
double evaluate(const char *exp);
BOOL fncmp(const char *str, const char *src);
int fnlen(const char *fn);
BOOL jmp(char **dest, const char **src, int len);
int oplen(const char *op);
int paramcnt(const char *fn);
UINT parse(const char *str, char *buf);
UINT precedence(const char *op);

內容轉換：

回覆帖子
內容：
用戶名： 您目前是匿名發表。
驗證碼：
看不清？換一張
©2010-2025 Purasbar Ver3.0 [手機版] [桌面版]
除非另有聲明，本站採用知識共享署名-相同方式共享 3.0 Unported許可協議進行許可。