从标准输入中读入一个整数算术运算表达式,如24 / ( 1 + 2 + 36 / 6 / 2 - 2) * ( 12 / 2 / 2 )= ,计算表达式结果,并输出。 要求: 1、表达式运算符只有+、-、*、/,表达式末尾的=字符表示表达式输入结束,表达式中可能会出现空格; 2、表达式中会出现圆括号,括号可能嵌套,不会出现错误的表达式; 3、出现除号/时,以整数相除进行运算,结果仍为整数,例如:5/3结果应为1。 4、要求采用表达式树来实现表达式计算。5.要求使用C语言,不可以使用C++语言
时间: 2023-07-14 09:11:48 浏览: 170
以下是使用C语言实现表达式树计算的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
/* 表达式树节点结构体 */
typedef struct node {
char op; // 运算符或操作数
struct node *left; // 左子节点
struct node *right; // 右子节点
} Node;
/* 创建节点 */
Node *createNode(char op) {
Node *node = (Node *)malloc(sizeof(Node));
node->op = op;
node->left = NULL;
node->right = NULL;
return node;
}
/* 销毁节点及其子节点 */
void destroyNode(Node *node) {
if (node == NULL) {
return;
}
destroyNode(node->left);
destroyNode(node->right);
free(node);
}
/* 构建表达式树 */
Node *buildExpressionTree(char *exp, int start, int end) {
Node *root = NULL;
Node *curNode = NULL;
Node *lastNode = NULL;
int i, j, k, level, minLevel;
/* 如何是一个数,则直接创建节点返回 */
if (exp[start] >= '0' && exp[start] <= '9') {
root = createNode(exp[start]);
return root;
}
/* 寻找运算符 */
level = 0;
minLevel = 10000;
for (i = start; i <= end; i++) {
if (exp[i] == '(') {
level++;
} else if (exp[i] == ')') {
level--;
} else if (level == 0 && (exp[i] == '+' || exp[i] == '-' || exp[i] == '*' || exp[i] == '/')) {
if (level <= minLevel) {
minLevel = level;
j = i; // 记录运算符位置
}
}
}
/* 如果没有找到运算符,则表达式应该被括号包含 */
if (j == 0) {
return buildExpressionTree(exp, start + 1, end - 1);
}
/* 创建根节点 */
root = createNode(exp[j]);
/* 递归构建左右子树 */
root->left = buildExpressionTree(exp, start, j - 1);
root->right = buildExpressionTree(exp, j + 1, end);
return root;
}
/* 计算表达式树 */
int evaluateExpressionTree(Node *root) {
int left, right;
if (root == NULL) {
return 0;
}
/* 如果是操作数,则直接返回该数值 */
if (root->op >= '0' && root->op <= '9') {
return root->op - '0';
}
/* 递归计算左右子树的值 */
left = evaluateExpressionTree(root->left);
right = evaluateExpressionTree(root->right);
/* 根据运算符计算表达式的值 */
switch (root->op) {
case '+':
return left + right;
case '-':
return left - right;
case '*':
return left * right;
case '/':
return left / right;
}
return 0;
}
int main() {
char exp[100];
Node *root = NULL;
int result;
/* 从标准输入中读入表达式 */
scanf("%[^\n]", exp);
/* 构建表达式树 */
root = buildExpressionTree(exp, 0, strlen(exp) - 1);
/* 计算表达式的值 */
result = evaluateExpressionTree(root);
/* 输出结果 */
printf("%d\n", result);
/* 销毁表达式树 */
destroyNode(root);
return 0;
}
```
注意,为了方便读入整个表达式,代码中使用了 `scanf()` 函数的 `%[^\n]` 格式化字符串,表示读入除换行符以外的所有字符。此外,代码中没有进行输入错误处理,实际应用中应该对输入进行检查。
阅读全文