1. 构建简单的表达式求值器

任务说明

实现一个支持加、减、乘、除和括号的表达式解析器，输入为字符串形式的算术表达式，输出为浮点数求值结果。例如输入 "(2+3)*4-6/2"，输出 17.0。

实现方案

采用递归下降解析法，构建如下语法层次：

expression := term { ('+' | '-') term }
term       := factor { ('*' | '/') factor }
factor     := number | '(' expression ')' | '-' factor

解析过程中直接求值，不生成抽象语法树，以最小代码量完成任务。

完整代码

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>

typedef struct {
    const char* p;
    int error;
} Parser;

static double expression(Parser* ps);

static void skip_space(Parser* ps) {
    while (isspace((unsigned char)*ps->p)) ps->p++;
}

static double parse_number(Parser* ps) {
    skip_space(ps);
    char* end;
    double val = strtod(ps->p, &end);
    if (end == ps->p) { ps->error = 1; return 0; }
    ps->p = end;
    return val;
}

static double factor(Parser* ps) {
    skip_space(ps);
    if (*ps->p == '(') {
        ps->p++;
        double val = expression(ps);
        skip_space(ps);
        if (*ps->p != ')') { ps->error = 1; return 0; }
        ps->p++;
        return val;
    }
    if (*ps->p == '-') {
        ps->p++;
        return -factor(ps);
    }
    return parse_number(ps);
}

static double term(Parser* ps) {
    double val = factor(ps);
    while (!ps->error) {
        skip_space(ps);
        char op = *ps->p;
        if (op != '*' && op != '/') break;
        ps->p++;
        double rhs = factor(ps);
        if (op == '*') val *= rhs;
        else {
            if (fabs(rhs) < 1e-12) { ps->error = 1; return 0; }
            val /= rhs;
        }
    }
    return val;
}

static double expression(Parser* ps) {
    double val = term(ps);
    while (!ps->error) {
        skip_space(ps);
        char op = *ps->p;
        if (op != '+' && op != '-') break;
        ps->p++;
        double rhs = term(ps);
        if (op == '+') val += rhs;
        else val -= rhs;
    }
    return val;
}

double evaluate(const char* expr, int* ok) {
    Parser ps = { expr, 0 };
    double val = expression(&ps);
    skip_space(&ps);
    if (ps.error || *ps.p != '\0') {
        *ok = 0;
        return 0;
    }
    *ok = 1;
    return val;
}

int main() {
    const char* tests[] = {
        "2+3*4",
        "(2+3)*4-6/2",
        "10-2*3+8/4",
        "((1+2)*3-4)/5",
        "7/0",
        "2+",
        NULL
    };
    for (int i = 0; tests[i] != NULL; i++) {
        int ok;
        double result = evaluate(tests[i], &ok);
        if (ok) printf("%s = %.6f\n", tests[i], result);
        else    printf("%s = ERROR\n", tests[i]);
    }
    return 0;
}

编译与运行

gcc -o evaluator evaluator.c -lm
./evaluator

预期输出

2+3*4 = 14.000000
(2+3)*4-6/2 = 17.000000
10-2*3+8/4 = 6.000000
((1+2)*3-4)/5 = 1.000000
7/0 = ERROR
2+ = ERROR

验证说明

测试用例覆盖了四则运算、括号嵌套、优先级、除零错误和非法输入。程序对除零和语法错误均返回 ERROR，对合法表达式输出精确到6位小数的浮点结果。所有输出与手工计算结果一致，表明解析器正确实现了加减乘除和括号的优先级规则。