输入简单算术表达式,利用二叉树来表示,并在创建表达式树后求表达式的值。 用二叉树每个结点代表一个运算符或运算数,简单数学表达式中只包含"+、-、*、/"和一位正整数且格式正确。 根据形如“1+2*3-4/5”的字 符串代表的表达式,构造出对应的二叉树 并计算出表达式的值。 可用二叉链表表示,通过遍历实现。用c语言实现,每一行的代码加上注释。
时间: 2024-01-22 22:19:27 浏览: 157
以下是用C语言实现的代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结构体
struct TreeNode {
char val; // 存储运算符或运算数
struct TreeNode* left; // 左子树
struct TreeNode* right; // 右子树
};
// 创建新节点
struct TreeNode* createNewNode(char val) {
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
// 构建表达式树
struct TreeNode* buildExpressionTree(char* expression) {
int len = strlen(expression);
struct TreeNode* root = createNewNode(expression[0]); // 根节点为第一个字符
struct TreeNode* curr = root; // 当前节点初始化为根节点
// 遍历表达式,构建表达式树
for (int i = 1; i < len; i += 2) {
struct TreeNode* node = createNewNode(expression[i+1]); // 创建新节点
if (expression[i] == '+') {
curr->left = node; // 当前节点的左子树为新创建的节点
curr = curr->left; // 当前节点移动到左子树
}
else if (expression[i] == '-') {
curr->left = node; // 当前节点的左子树为新创建的节点
curr = curr->left; // 当前节点移动到左子树
}
else if (expression[i] == '*') {
curr->right = node; // 当前节点的右子树为新创建的节点
curr = curr->right; // 当前节点移动到右子树
}
else if (expression[i] == '/') {
curr->right = node; // 当前节点的右子树为新创建的节点
curr = curr->right; // 当前节点移动到右子树
}
else {
printf("Invalid input!\n");
return NULL;
}
}
return root;
}
// 求表达式的值
int evaluateExpressionTree(struct TreeNode* root) {
if (root == NULL) return 0;
if (root->left == NULL && root->right == NULL) return (root->val - '0'); // 叶节点为数字
int leftVal = evaluateExpressionTree(root->left); // 左子树的值
int rightVal = evaluateExpressionTree(root->right); // 右子树的值
switch (root->val) { // 根据运算符计算结果
case '+': return leftVal + rightVal;
case '-': return leftVal - rightVal;
case '*': return leftVal * rightVal;
case '/': return leftVal / rightVal;
default: return 0;
}
}
int main() {
char expression[] = "1+2*3-4/5";
struct TreeNode* root = buildExpressionTree(expression);
printf("The value of expression is: %d\n", evaluateExpressionTree(root));
return 0;
}
```
这段代码中,我们首先定义了一个二叉树结构体`TreeNode`,表示二叉树的节点。其中,`val`表示存储的运算符或运算数,`left`表示左子树,`right`表示右子树。
接下来,我们定义了一个函数`createNewNode`,用于创建新节点。该函数接受一个参数`val`,表示要存储的值,返回一个指针,指向新创建的节点。
然后,我们定义了一个函数`buildExpressionTree`,用于构建表达式树。该函数接受一个参数`expression`,表示要构建表达式树的表达式字符串。首先,我们计算字符串的长度,并创建一个根节点,值为字符串的第一个字符。然后,我们遍历字符串,每次取出两个字符,一个表示运算符,一个表示运算数,创建一个新节点,并将其插入到树中。如果运算符为`+`或`-`,则将新节点插入到当前节点的左子树中,否则插入到右子树中。最后,返回根节点。
最后,我们定义了一个函数`evaluateExpressionTree`,用于求表达式树的值。该函数接受一个二叉树的指针`root`,表示要求值的表达式树。如果当前节点是叶节点,则直接返回该节点存储的数字。否则,我们递归调用该函数,分别求左子树和右子树的值,并根据当前节点的运算符,计算左右子树的结果。最后,返回计算结果。
在`main`函数中,我们首先定义了一个表达式字符串`expression`,并调用`buildExpressionTree`函数构建表达式树。然后,我们调用`evaluateExpressionTree`函数求出表达式的值,并输出该值。
以上就是用C语言实现简单数学表达式的二叉树表示及求值的过程。
阅读全文