通过c语言写出使用二叉链表根据字符串代表的表达式,构造出对 应的二叉树,并计算出表达式,代码标明注释
时间: 2024-02-17 16:02:14 浏览: 62
好的,下面是使用C语言实现的代码,注释已经标明:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 定义树节点
typedef struct TreeNode {
char data; // 节点数据
struct TreeNode *left; // 左子树
struct TreeNode *right; // 右子树
} TreeNode;
// 定义栈节点
typedef struct StackNode {
TreeNode *data; // 节点指针
struct StackNode *next; // 下一个节点指针
} StackNode;
// 定义栈
typedef struct Stack {
StackNode *top; // 栈顶指针
} Stack;
// 初始化栈
void initStack(Stack *stack) {
stack->top = NULL;
}
// 判断栈是否为空
int isEmpty(Stack *stack) {
return stack->top == NULL;
}
// 入栈
void push(Stack *stack, TreeNode *data) {
StackNode *node = (StackNode*)malloc(sizeof(StackNode));
node->data = data;
node->next = stack->top;
stack->top = node;
}
// 出栈
TreeNode* pop(Stack *stack) {
if(isEmpty(stack)) {
return NULL;
}
TreeNode *data = stack->top->data;
StackNode *node = stack->top;
stack->top = stack->top->next;
free(node);
return data;
}
// 获取栈顶元素
TreeNode* getTop(Stack *stack) {
if(isEmpty(stack)) {
return NULL;
}
return stack->top->data;
}
// 判断是否是运算符
int isOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/';
}
// 判断优先级
int getPriority(char c) {
if(c == '*' || c == '/') {
return 2;
} else if(c == '+' || c == '-') {
return 1;
} else {
return 0;
}
}
// 中缀表达式转后缀表达式
void infixToPostfix(char *infix, char *postfix) {
Stack stack;
initStack(&stack);
int i, j = 0;
for(i = 0; infix[i] != '\0'; i++) {
if(infix[i] >= '0' && infix[i] <= '9') {
postfix[j++] = infix[i];
} else if(isOperator(infix[i])) {
while(!isEmpty(&stack) && isOperator(getTop(&stack)->data) && getPriority(getTop(&stack)->data) >= getPriority(infix[i])) {
postfix[j++] = pop(&stack)->data;
}
push(&stack, (TreeNode*)infix[i]);
} else if(infix[i] == '(') {
push(&stack, (TreeNode*)infix[i]);
} else if(infix[i] == ')') {
while(!isEmpty(&stack) && getTop(&stack)->data != '(') {
postfix[j++] = pop(&stack)->data;
}
pop(&stack);
}
}
while(!isEmpty(&stack)) {
postfix[j++] = pop(&stack)->data;
}
postfix[j] = '\0';
}
// 构造二叉树
TreeNode* constructTree(char *postfix) {
Stack stack;
initStack(&stack);
int i;
for(i = 0; postfix[i] != '\0'; i++) {
if(postfix[i] >= '0' && postfix[i] <= '9') {
TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
node->data = postfix[i];
node->left = NULL;
node->right = NULL;
push(&stack, node);
} else if(isOperator(postfix[i])) {
TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
node->data = postfix[i];
node->right = pop(&stack);
node->left = pop(&stack);
push(&stack, node);
}
}
return pop(&stack);
}
// 计算表达式的值
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 infix[100], postfix[100];
printf("请输入中缀表达式:");
scanf("%s", infix);
infixToPostfix(infix, postfix);
printf("后缀表达式为:%s\n", postfix);
TreeNode* root = constructTree(postfix);
int result = evaluate(root);
printf("表达式的值为:%d\n", result);
return 0;
}
```
以上代码实现了字符串代表的表达式构造对应的二叉树,并计算出表达式的值。
阅读全文