用C语言写出程序"读入表达式树的先序遍历字符串,求其值。运算符只可能是加减乘除,保证输入的每个子表达式树的结果都是整数值且可以用C语言的int类型表达。"
时间: 2024-03-24 15:39:52 浏览: 58
以下是使用C语言实现读入表达式树的先序遍历字符串,求其值的程序:
```c
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
typedef struct TreeNode {
char data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 根据先序遍历字符串构建表达式树
TreeNode *buildExpressionTree(char *str) {
TreeNode *node = NULL;
if (*str == '+' || *str == '-' || *str == '*' || *str == '/') {
node = (TreeNode *)malloc(sizeof(TreeNode));
node->data = *str;
str++;
node->left = buildExpressionTree(str);
str++;
node->right = buildExpressionTree(str);
}
else {
node = (TreeNode *)malloc(sizeof(TreeNode));
node->data = *str;
node->left = NULL;
node->right = NULL;
}
return node;
}
// 计算表达式树的值
int evaluateExpressionTree(TreeNode *root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return root->data - '0';
}
int leftValue = evaluateExpressionTree(root->left);
int rightValue = evaluateExpressionTree(root->right);
switch (root->data) {
case '+':
return leftValue + rightValue;
case '-':
return leftValue - rightValue;
case '*':
return leftValue * rightValue;
case '/':
return leftValue / rightValue;
default:
return 0;
}
}
int main() {
char str[100];
printf("请输入表达式树的先序遍历字符串:");
scanf("%s", str);
TreeNode *root = buildExpressionTree(str);
int result = evaluateExpressionTree(root);
printf("表达式树的值为:%d\n", result);
return 0;
}
```
程序中使用了两个函数,`buildExpressionTree`函数用于构建表达式树,`evaluateExpressionTree`函数用于计算表达式树的值。程序首先读入表达式树的先序遍历字符串,然后调用`buildExpressionTree`函数构建表达式树,最后调用`evaluateExpressionTree`函数计算表达式树的值。
阅读全文