用C语言写一个语法树例子
时间: 2023-12-29 15:44:05 浏览: 36
以下是一个使用C语言实现的简单的表达式语法树:
```c
#include <stdio.h>
#include <stdlib.h>
// 表达式节点类型
typedef struct ExprNode {
char op; // 运算符或操作数
struct ExprNode *left; // 左子节点
struct ExprNode *right; // 右子节点
} ExprNode;
// 创建表达式节点
ExprNode *createExprNode(char op, ExprNode *left, ExprNode *right) {
ExprNode *node = (ExprNode*) malloc(sizeof(ExprNode));
node->op = op;
node->left = left;
node->right = right;
return node;
}
// 释放表达式树
void freeExprTree(ExprNode *root) {
if (root == NULL) return;
freeExprTree(root->left);
freeExprTree(root->right);
free(root);
}
// 计算表达式树的值
int evalExprTree(ExprNode *root) {
if (root == NULL) return 0;
if (root->op >= '0' && root->op <= '9') { // 操作数
return root->op - '0';
} else { // 运算符
int leftVal = evalExprTree(root->left);
int rightVal = evalExprTree(root->right);
switch (root->op) {
case '+':
return leftVal + rightVal;
case '-':
return leftVal - rightVal;
case '*':
return leftVal * rightVal;
case '/':
return leftVal / rightVal;
default:
printf("Invalid operator: %c\n", root->op);
return 0;
}
}
}
int main() {
// 构建表达式树
ExprNode *root = createExprNode('+',
createExprNode('*',
createExprNode('2', NULL, NULL),
createExprNode('3', NULL, NULL)),
createExprNode('-',
createExprNode('5', NULL, NULL),
createExprNode('1', NULL, NULL)));
// 计算表达式树的值
int result = evalExprTree(root);
// 输出结果
printf("Result: %d\n", result);
// 释放表达式树
freeExprTree(root);
return 0;
}
```
该程序使用递归的方式构建表达式树,并提供了计算表达式树的值的函数和释放表达式树的函数。在 main 函数中,我们构建了一个简单的表达式树,计算其值并输出结果。最后释放表达式树的内存。