上述代码不用栈的情况代码
时间: 2023-07-03 20:23:59 浏览: 41
如果不使用栈,也可以使用递归的方式实现中序表达式创建二叉树和求值,下面是相应的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
// 定义二叉树节点结构体
typedef struct TreeNode {
char data; // 节点值
struct TreeNode* left; // 左子树指针
struct TreeNode* right; // 右子树指针
} TreeNode;
// 创建节点
TreeNode* createNode(char data) {
TreeNode* node = (TreeNode*) malloc(sizeof(TreeNode));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
// 递归创建二叉树
TreeNode* createBinaryTree(char* expression, int start, int end) {
if (start > end) {
return NULL;
}
TreeNode* root = NULL;
int i;
int flag = 0; // 用于判断括号是否匹配
for (i = start; i <= end; i++) {
if (expression[i] == '(') {
flag++;
} else if (expression[i] == ')') {
flag--;
} else if (flag == 0 && (expression[i] == '+' || expression[i] == '-' || expression[i] == '*' || expression[i] == '/')) {
root = createNode(expression[i]);
break;
}
}
if (root == NULL) {
for (i = start; i <= end; i++) {
if (isdigit(expression[i])) {
root = createNode(expression[i]);
break;
}
}
}
root->left = createBinaryTree(expression, start, i - 1);
root->right = createBinaryTree(expression, i + 1, end);
return root;
}
// 计算表达式的值
int evaluate(TreeNode* root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) { // 如果是叶子节点,返回节点值
return root->data - '0'; // 将字符转换为数字
}
int leftValue = evaluate(root->left); // 计算左子树的值
int rightValue = evaluate(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 expression[100];
printf("请输入中序表达式:");
scanf("%s", expression);
TreeNode* root = createBinaryTree(expression, 0, strlen(expression) - 1); // 创建二叉树
int result = evaluate(root); // 计算表达式的值
printf("表达式的值为:%d\n", result);
return 0;
}
```
这个递归实现方式需要注意括号是否匹配,而且表达式中不能有空格。