C 语言数学解析器

archive time: 2022-10-26

很久没更新了, 今天我们用 C 做一个数学计算器

最近突然想尝试写一个 Parser,不过一直没有思路,所以不知道如何实践

然后在看 tauri 相关的例子的时候突然想到可以做一个数学式的 Parser

虽然 tauriRust 的,但是我打算先用 C 写个原型

自定义类型

我打算使用自定义类型来存储结果

原式 2 - (3 + sin(3.14 / 2)) / 7 + 2 ^ 2,结果

Add( Sub( Const( value: 2.0000 ) Div( Par( Add( Const( value: 3.0000 ) Sin( Par( Div( Const( value: 3.1400 ) Const( value: 2.0000 ) ) ) ) ) ) Const( value: 7.0000 ) ) ) Pow( Const( value: 2.0000 ) Const( value: 2.0000 ) ) )

大概可以分解为

对应 Expr 的类型定义为

typedef struct pm_Expr { PM_FUNC func; struct pm_Expr *e1; struct pm_Expr *e2; float value; } pm_Expr;

而这里我定义了几类函数,日后可以按需扩充

typedef enum PM_FUNC { ADD = 10, SUB = 11, MUL = 20, DIV = 21, NEG = 30, POS = 31, POW = 40, SIN = 50, COS = 51, EXP = 52, PAR = 60, CONST = 61, } PM_FUNC;

每项的值都是 优先级 + 序号 的组合

例如 ADD 的值为 10,则,优先级为 1,对应优先级中序号为 0

函数原型

我将解析功能拆分成了一下几个函数来完成

extern pm_Expr *pm_parse(const char *orgExpr); extern pm_Expr *pm_number(const char *expr, size_t *bias); extern pm_Expr *pm_parentheses(const char *expr, size_t *bias); extern pm_Expr *pm_function(const char *expr, size_t *bias);

分别是

  • 对整个式子的解析
  • 对于单个数字的解析
  • 对于一组括号的解析
  • 对于函数调用的解析

函数主要实现

由于一些细节比较繁琐,这里只介绍主要部分的实现,详细可以 参考我的仓库

仓库链接已经失效,不过代码示例足够展示解析过程了

main

整个解析的部分就是不断根据当前字符来判断该用什么来解析

pm_Expr *pm_parse(const char *orgExpr) { // ignore all whitespace characters char *expr = pm_ignoreBlank(orgExpr); char *handle = expr; // store the result pm_Expr *parsedExpr = NULL; pm_Expr *tempExpr = NULL; // store the current state char curChar = *expr; // start to parse while (*expr != '\0') { // the offset size_t bias = 0; if (isdigit(curChar) || '.' == curChar) { // parse number tempExpr = pm_number(expr, &bias); expr += bias; } else if (pm_isOperator(curChar)) { // the operator // ... } else if ('(' == curChar) { // parse parentheses tempExpr = pm_parentheses(expr, &bias); expr += bias; } else if (isalpha(curChar)) { // parse function call tempExpr = pm_function(expr, &bias); expr += bias; } else { fprintf(stderr, "Error: wrong math expression syntax\n"); exit(EXIT_FAILURE); } // ... free(handle); return parsedExpr; }

首先调用 pm_ignoreBlank 将字符串中的空白字符给去掉,同时复制一份可以操作的字符串

使用 handle 存储首地址,在解析完毕后释放空间

parsedExprtempExpr 分别用于存储最终结果和临时解析结果

每得到一个临时结果都需要按照优先级规律插入到最终结果中

解析时,通过当前字符类型来判别调用函数

  • 如果是当前字符是数字,则使用 pm_number
  • 如果是一个左括号,则调用 pm_parentheses
  • 如果是字母,则可能是函数调用,使用 pm_function

如果是个符号,若符号是操作符,则需要按照规律插入到结果中

bool isPrefix = false; if (NULL == parsedExpr) { // E ::= sign(E) isPrefix = true; } // insert new operator PM_FUNC opSym = pm_getOperatorSymbol(curChar, isPrefix); // E ::= E o E if (NULL == parsedExpr || !pm_comparePriority(opSym, parsedExpr->func)) { pm_Expr *newExpr = malloc(sizeof(pm_Expr)); newExpr->func = opSym; newExpr->e1 = parsedExpr; newExpr->e2 = NULL; parsedExpr = newExpr; } else { pm_Expr *currExpr = parsedExpr; pm_Expr *nextExpr = NULL; while (NULL != currExpr->e1 || NULL != currExpr->e2) { size_t curType = pm_getFuncType(currExpr->func); if (1 == curType) { nextExpr = currExpr->e1; } else if (2 == curType) { nextExpr = currExpr->e2; } else { fprintf(stderr, "Error: wrong func type!\n"); exit(EXIT_FAILURE); } if (pm_comparePriority(opSym, nextExpr->func)) { currExpr = nextExpr; } else { pm_Expr *newExpr = malloc(sizeof(pm_Expr)); newExpr->func = opSym; newExpr->e1 = nextExpr; if (1 == curType) { currExpr->e1 = newExpr; } else if (2 == curType) { currExpr->e2 = newExpr; } break; } } // check if (NULL == nextExpr) { fprintf(stderr, "Error: wrong expression syntax with operator!\n"); exit(EXIT_FAILURE); } } expr++; curChar = *expr; continue;

具体操作我就不解释了,简而言之,就是在构建一棵树

number

解析数字,我们默认是 float,所以需要考虑小数的判别

pm_Expr *pm_number(const char *expr, size_t *bias) { if (NULL == expr) { fprintf(stderr, "Error: expression cannot be null!\n"); exit(EXIT_FAILURE); } // store state bool inFrac = false; char curChar = *expr; float fracCnt = 0; float number = 0.0f; // start to parse while ('\0' != curChar && (isdigit(curChar) || '.' == curChar)) { if (inFrac) { // fractional number part if ('.' == curChar) { fprintf(stderr, "Error: fraction do not have dot!\n"); exit(EXIT_FAILURE); } else { number += fracCnt * (curChar - '0'); fracCnt *= 0.1f; } } else { // whole number part if ('.' != curChar) { number *= 10; number += (curChar - '0'); } else { inFrac = true; fracCnt = 0.1; } } // move on expr++; *bias += 1; curChar = *expr; } // build expression pm_Expr *numExpr = malloc(sizeof(pm_Expr)); numExpr->e1 = NULL; numExpr->e2 = NULL; numExpr->func = CONST; numExpr->value = number; // return expression return numExpr; }

由于一开始我们就将空格滤掉了,所以我们就无须考虑空格之类的问题

数字解析整体过程比较粗暴,不过真的好用

parentheses

括号的解析关键在于找到对应的括号

pm_Expr *pm_parentheses(const char *expr, size_t *bias) { if (NULL == expr) { fprintf(stderr, "Error: expression cannot be null!\n"); exit(EXIT_FAILURE); } // store state int pCnt = 0; size_t insideCnt = 0; char curChar = *expr; // match all content inside parentheses do { if ('(' == curChar) { pCnt++; } else if (')' == curChar) { pCnt--; } insideCnt++; curChar = *(expr + insideCnt); *bias += 1; } while ('\0' != curChar && pCnt != 0); if (pCnt != 0) { fprintf(stderr, "Error: cannot match all parentheses!\n"); exit(EXIT_FAILURE); } // get the inside content char *insideContent = calloc(insideCnt - 1, sizeof(char)); insideContent = strncpy(insideContent, expr + 1, insideCnt - 2); // get the inside expression pm_Expr *insideExpr = pm_parse(insideContent); free(insideContent); pm_Expr *wrapExpr = malloc(sizeof(pm_Expr)); wrapExpr->func = PAR; wrapExpr->e1 = insideExpr; return wrapExpr; }

匹配出括号中的内容后可以直接使用 pm_parse 函数解析内容,而后使用 PAR 包裹

function

函数部分依赖括号的解析,总之,就是将参数部分当成括号解析,而后使用相应函数包裹

pm_Expr *pm_function(const char *expr, size_t *bias) { size_t funNameLen = 0; while (isalpha(*(expr + funNameLen))) { funNameLen++; } char *funName = calloc(funNameLen + 1, sizeof(char)); for (size_t i = 0; i < funNameLen; ++i) { funName[i] = expr[i]; } expr += funNameLen; pm_Expr *paramExpr = NULL; size_t paramBias = 0; if ('(' == *expr) { paramExpr = pm_parentheses(expr, &paramBias); } else { fprintf(stderr, "Error: wrong function call syntax!\n"); exit(EXIT_FAILURE); } *bias += funNameLen + paramBias; pm_Expr *funExpr = malloc(sizeof(pm_Expr)); funExpr->func = pm_getFuncSym(funName); funExpr->e1 = paramExpr; funExpr->e2 = NULL; return funExpr; }

求值

求值的时候可以通过 pm_Exprfunc 字段判断使用何种方式计算

float pm_evaluation(const pm_Expr *expr) { if (ADD == expr->func) { return pm_evaluation(expr->e1) + pm_evaluation(expr->e2); } else if (SUB == expr->func) { return pm_evaluation(expr->e1) - pm_evaluation(expr->e2); } else if (MUL == expr->func) { return pm_evaluation(expr->e1) * pm_evaluation(expr->e2); } else if (DIV == expr->func) { float d = pm_evaluation(expr->e2); if (fabsf(d) < 1e-4) { fprintf(stderr, "Error: cannot divide zero!\n"); exit(EXIT_FAILURE); } return pm_evaluation(expr->e1) / d; } else if (NEG == expr->func) { return -pm_evaluation(expr->e1); } else if (POW == expr->func) { return powf(pm_evaluation(expr->e1), pm_evaluation(expr->e2)); } else if (SIN == expr->func) { return sinf(pm_evaluation(expr->e1)); } else if (COS == expr->func) { return cosf(pm_evaluation(expr->e1)); } else if (EXP == expr->func) { return expf(pm_evaluation(expr->e1)); } else if (PAR == expr->func) { return pm_evaluation(expr->e1); } else if (CONST == expr->func) { return expr->value; } else { fprintf(stderr, "Error: wrong expression when evaluation!\n"); exit(EXIT_FAILURE); } return 0.0f; }

不断递归调用,最后求得最后结果


以上就是我这个解析器的实现大概,通过这次实践,大概算是知道如何写 Parser 了,多少还算有些收获吧