C语言实现表达式求值函数：从理论到实践构建一个强大的数学表达式解析器343

在计算机科学领域，处理和评估数学表达式是一项基础而又复杂的工作。从简单的计算器应用到复杂的编译器、解释器，乃至各种脚本语言，对表达式的解析和求值能力都是其核心功能之一。在C语言中，虽然标准库并未提供一个名为“expression”的内置函数来直接完成这项任务，但作为一门强大且灵活的语言，C语言完全有能力让我们从零开始构建一个高效、自定义的表达式求值函数。本文将深入探讨如何在C语言中设计并实现一个这样的“表达式函数”，涵盖其背后的理论、关键算法以及实际实现细节。

理解“表达式函数”的本质与需求

首先，我们需要明确“C语言expression函数”这个标题所指的实际含义。它并非指C语言标准库中存在一个`expression()`这样的函数，而是指我们自己编写一个C函数，用于接收一个字符串形式的数学表达式（例如"2 + 3 * (4 - 1)"），并返回其计算结果。这种函数通常被称为“表达式求值器”或“表达式解析器”。

一个合格的表达式求值函数需要处理以下核心问题：
词法分析 (Lexical Analysis)：将输入的字符串表达式分解成有意义的“词素”或“标记”（Tokens），如数字、运算符、括号等。
语法分析 (Syntax Analysis)：理解这些标记的排列组合是否符合语法规则，并确定它们的运算顺序。
语义分析 (Semantic Analysis)：根据语法树或某种中间表示来实际执行计算。
错误处理：识别并报告无效的表达式，如括号不匹配、非法字符、除以零等。

最常见的表达式求值任务是处理算术表达式。一个健壮的表达式求值器通常需要能够处理：
整数和浮点数
加、减、乘、除等基本算术运算符
括号以改变运算优先级
运算符的优先级（例如乘除高于加减）
运算符的结合性（例如左结合性：`a - b - c` 等同于 `(a - b) - c`）

核心算法：从中缀表达式到逆波兰表达式（RPN）

人类习惯使用“中缀表达式” (Infix Notation)，即将运算符放在操作数之间，如 `2 + 3 * (4 - 1)`。然而，这种表示方式对于计算机直接求值来说并不方便，因为它需要处理复杂的优先级和括号规则。为了简化求值过程，我们通常会将其转换为“后缀表达式” (Postfix Notation) 或“逆波兰表达式” (Reverse Polish Notation, RPN)。在后缀表达式中，运算符放在其操作数之后，如 `2 3 4 1 - * +`。

RPN的优势在于：
无需括号：所有运算顺序由操作数和运算符的顺序决定。
易于求值：从左到右扫描表达式，遇到数字就入栈，遇到运算符就从栈顶取出相应数量的操作数进行运算，然后将结果入栈。

因此，构建表达式求值函数的核心步骤可以分为两步：
中缀表达式转后缀表达式：这通常通过“调度场算法”（Shunting-Yard Algorithm）来实现。
后缀表达式求值：这是一个相对简单的基于栈的操作。

1. 调度场算法（Shunting-Yard Algorithm）详解

调度场算法由Dijkstra提出，它的灵感来源于火车站的调度场，通过轨道（栈）对火车（标记）进行重新排序。该算法使用两个主要的数据结构：
输出队列 (Output Queue)：存储转换后的后缀表达式的标记。
运算符栈 (Operator Stack)：临时存储运算符和左括号。

算法步骤如下：
从左到右读取中缀表达式的标记。
如果标记是数字：将其直接放入输出队列。
如果标记是函数（此文暂不深入讨论函数）：将其推入运算符栈。
如果标记是运算符 (op1)：

当运算符栈不为空，且栈顶是运算符 (op2)，且满足以下条件之一时：

op1 是左结合性，且其优先级小于或等于 op2 的优先级。
op1 是右结合性，且其优先级小于 op2 的优先级。

将 op2 从运算符栈弹出，并放入输出队列。重复此步骤。
将 op1 推入运算符栈。


如果标记是左括号 "("：将其推入运算符栈。
如果标记是右括号 ")"：

不断将运算符栈顶的运算符弹出并放入输出队列，直到遇到左括号 "("。
将左括号从运算符栈弹出（但不要放入输出队列）。
如果弹出后栈顶是函数，也将其弹出并放入输出队列。
如果遍历完所有标记，但没有找到左括号，则表示括号不匹配，表达式错误。


所有标记读取完毕后：

将运算符栈中剩余的所有运算符依次弹出并放入输出队列。
如果栈中还存在任何括号，则表示括号不匹配，表达式错误。

示例：将 `3 + 4 * 2 / (1 - 5)` 转换为后缀表达式


读取标记
运算符栈
输出队列 (RPN)
说明



33数字直接输出
++3运算符入栈
4+3 4数字直接输出
*+ *3 4`*` 优先级高于 `+`，`*` 入栈
2+ *3 4 2数字直接输出
/+ /3 4 2 *`*` 优先级高于或等于 `/`，`*` 出栈；`+` 优先级低于 `/`，`/` 入栈
(+ / (3 4 2 *左括号入栈
1+ / (3 4 2 * 1数字直接输出
-+ / ( -3 4 2 * 1`-` 入栈
5+ / ( -3 4 2 * 1 5数字直接输出
)+ /3 4 2 * 1 5 -遇到 `)`，`-` 出栈；弹出 `(`
结束3 4 2 * 1 5 - / +栈中剩余运算符依次出栈：`/` -> `+`

最终的后缀表达式为：`3 4 2 * 1 5 - / +`。

2. 后缀表达式求值算法

后缀表达式求值相对简单，只需要一个栈：
从左到右读取后缀表达式的标记。
如果标记是数字：将其推入栈。
如果标记是运算符：

从栈顶弹出两个操作数（operand2, operand1）。注意顺序，先弹出的是右操作数。
执行运算 `operand1 运算符 operand2`。
将运算结果推入栈。


所有标记读取完毕后，栈中唯一剩下的元素即为表达式的最终结果。

示例：求值 `3 4 2 * 1 5 - / +`


读取标记
操作数栈
说明



3[3]数字入栈
4[3, 4]数字入栈
2[3, 4, 2]数字入栈
*[3, 8]弹出 2, 4；计算 4 * 2 = 8；结果入栈
1[3, 8, 1]数字入栈
5[3, 8, 1, 5]数字入栈
-[3, 8, -4]弹出 5, 1；计算 1 - 5 = -4；结果入栈
/[3, -2]弹出 -4, 8；计算 8 / (-4) = -2；结果入栈
+[1]弹出 -2, 3；计算 3 + (-2) = 1；结果入栈
结束[1]栈顶即为结果

最终结果为：`1`。

C语言实现细节与数据结构

要在C语言中实现上述算法，我们需要定义一些关键的数据结构和辅助函数。

1. 标记 (Token) 数据结构

为了表示表达式中的不同元素，我们可以定义一个 `Token` 结构体：typedef enum {
TOKEN_NUMBER,
TOKEN_OPERATOR,
TOKEN_LPAREN, // 左括号 '('
TOKEN_RPAREN, // 右括号 ')'
TOKEN_END, // 表达式结束
TOKEN_ERROR
} TokenType;
typedef struct {
TokenType type;
union {
double value; // 如果是数字
char op; // 如果是运算符或括号
} data;
} Token;

2. 栈 (Stack) 数据结构

调度场算法和后缀表达式求值都需要栈。我们可以使用数组或链表实现栈。对于固定大小的简单表达式，数组实现可能更直接：#define MAX_STACK_SIZE 100
typedef struct {
Token items[MAX_STACK_SIZE];
int top;
} TokenStack;
typedef struct {
double items[MAX_STACK_SIZE];
int top;
} ValueStack;
// 栈操作函数 (push, pop, peek, is_empty, is_full)
void token_stack_push(TokenStack *s, Token t);
Token token_stack_pop(TokenStack *s);
Token token_stack_peek(TokenStack *s);
// ... value_stack_push, value_stack_pop, etc.

3. 辅助函数

`is_digit(char c)`: 判断字符是否为数字。
`is_operator(char c)`: 判断字符是否为运算符。
`get_precedence(char op)`: 获取运算符的优先级。例如，`+`, `-` 为 1，`*`, `/` 为 2。
`is_left_associative(char op)`: 判断运算符是否为左结合性。

4. 核心功能函数

a. `tokenize(const char* expr_str, Token* tokens_output)`

这是词法分析阶段，负责将输入的字符串表达式转换为 `Token` 数组。它需要遍历字符串，识别数字、运算符、括号，并填充 `tokens_output` 数组。// 示例骨架
int tokenize(const char* expr_str, Token* tokens_output) {
int i = 0; // 表达式字符串索引
int token_idx = 0; // token数组索引
while (expr_str[i] != '\0') {
char c = expr_str[i];
if (isspace(c)) {
i++;
continue;
}
if (isdigit(c) || c == '.') {
// 解析数字（支持浮点数）
char* endptr;
tokens_output[token_idx].type = TOKEN_NUMBER;
tokens_output[token_idx]. = strtod(&expr_str[i], &endptr);
i = endptr - expr_str;
} else if (is_operator(c)) {
tokens_output[token_idx].type = TOKEN_OPERATOR;
tokens_output[token_idx]. = c;
i++;
} else if (c == '(') {
tokens_output[token_idx].type = TOKEN_LPAREN;
tokens_output[token_idx]. = c;
i++;
} else if (c == ')') {
tokens_output[token_idx].type = TOKEN_RPAREN;
tokens_output[token_idx]. = c;
i++;
} else {
// 错误：非法字符
tokens_output[token_idx].type = TOKEN_ERROR;
return -1; // 表示出错
}
token_idx++;
if (token_idx >= MAX_STACK_SIZE) { /* 错误：token数量超出限制 */ return -1; }
}
tokens_output[token_idx].type = TOKEN_END; // 标记表达式结束
return token_idx; // 返回token数量
}

b. `infix_to_postfix(const Token* infix_tokens, Token* postfix_tokens)`

实现调度场算法，将中缀标记数组转换为后缀标记数组。// 示例骨架
int infix_to_postfix(const Token* infix_tokens, Token* postfix_tokens) {
TokenStack operator_stack;
init_token_stack(&operator_stack); // 初始化栈
int postfix_idx = 0;
for (int i = 0; infix_tokens[i].type != TOKEN_END; i++) {
Token current = infix_tokens[i];
switch () {
case TOKEN_NUMBER:
postfix_tokens[postfix_idx++] = current;
break;
case TOKEN_OPERATOR:
while (!is_token_stack_empty(&operator_stack) &&
operator_stack_peek(&operator_stack).type == TOKEN_OPERATOR &&
((is_left_associative() &&
get_precedence()

2025-11-17

---

上一篇：C语言数组元素交换深度解析：从基础到高级技巧与应用实践

下一篇：C语言信号集操作详解：从sigset_t到sigprocmask的实践指南