基于二叉树的四则运算.zip

#include "BinaryTree.h" #include "stack.h" #include "LQueue.h" #include <stdio.h> #include <stdlib.h> #include <Windows.h> #include <conio.h> /** * @name : Status InitBiTree(BiTree T); * @description : 构造空二叉树T * @param : 二叉树根结点T */ Status InitBiTree(BiTree *T) { if ((*T) != NULL) { return ERROR; } (*T) = NULL; return SUCCESS; } /** * @name : Status DestroyBiTree(BiTree T); * @description : 摧毁二叉树T * @param : 二叉树根结点T */ Status DestroyBiTree(BiTree T) { if (T != NULL) { DestroyBiTree(T->lchild); DestroyBiTree(T->rchild); free(T); //后序遍历，先摧毁叶结点 T = NULL; return SUCCESS; } return ERROR; } /** * @name : Status CreateBiTree(BiTree T, char* definition); * @description : 构造二叉树T * @param : 二叉树根结点的指针的指针T, 二叉树先序遍历字符串definition,字符串的开始位置begin，字符串的结束位置end */ Status CreateBiTree(BiTree *T, char* definition, int begin, int end) { BiTree p = NULL; if (begin == end) //创建叶结点，停止递归 { p = (BiTree)malloc(sizeof(BiTNode)); p->data = definition[begin]; p->lchild = NULL; p->rchild = NULL; } else { int tag; tag = search(definition, begin, end); //搜索树根的下标 p = (BiTree)malloc(sizeof(BiTNode)); p->data = definition[tag]; if (definition[begin] == '(' && definition[end] == ')') { begin += 1; end -= 1; } CreateBiTree(&(p->lchild), definition, begin, tag - 1); //将字符串一分为二，左边 CreateBiTree(&(p->rchild), definition, tag + 1, end); //右边 } (*T) = p; //将根结点指向创建的表达式根 return SUCCESS; } /** * @name : int search(char a[], int begin, int end); * @description : 搜索字符串中的元素，以运算优先次序返回下标 * @param : 字符串str, 字符串的开始位置begin，字符串的结束位置end */ int search(char str[], int begin, int end) { int tag = -1; //初始化下标为-1 int isInBrackets = 0; //判断是否在括号之内 if (str[begin] == '(' && str[end] == ')') { begin += 1; end -= 1; } int amExist = 0; //用来判断根是否为+或者- int i; for (i = begin; i < end; i++) { if (str[i] == '(') //判断是否在括号内 isInBrackets++; if (str[i] == ')') isInBrackets--; if ((str[i] == '+' || str[i] == '-') && isInBrackets == 0) { tag = i; //记录下标 amExist = 1; } if ((str[i] == '*' || str[i] == '/') && isInBrackets == 0 && amExist == 0) { tag = i; //记录下标 } } return tag; } /** * @name : Status PreOrderTraverse(BiTree T, Status (*visit)(TElemType e)); * @description : 先序遍历二叉树T * @param : 二叉树根结点T, 对结点的操作函数visit */ Status PreOrderTraverse(BiTree T, Status(*visit)(TElemType e)) { if (!T) { return ERROR; } (*visit)(T->data); PreOrderTraverse(T->lchild, visit); PreOrderTraverse(T->rchild, visit); return SUCCESS; } /** * @name : Status InOrderTraverse(BiTree T, Status (*visit)(TElemType e)); * @description : 中序遍历二叉树T * @param : 二叉树根结点T, 对结点的操作函数visit */ Status InOrderTraverse(BiTree T, Status(*visit)(TElemType e)) { if (!T) { return ERROR; } InOrderTraverse(T->lchild, visit); (*visit)(T->data); InOrderTraverse(T->rchild, visit); return SUCCESS; } /** * @name : Status PostOrderTraverse(BiTree T, Status (*visit)(TElemType e))); * @description : 后序遍历二叉树T * @param : 二叉树根结点T, 对结点的操作函数visit */ Status PostOrderTraverse(BiTree T, Status(*visit)(TElemType e)) { if (!T) { return ERROR; } PostOrderTraverse(T->lchild, visit); PostOrderTraverse(T->rchild, visit); (*visit)(T->data); return SUCCESS; } /** * @name : Status LevelOrderTraverse(BiTree T, Status (*visit)(TElemType e)); * @description : 层序遍历二叉树T * @param : 二叉树根结点T, 对结点的操作函数visit */ Status LevelOrderTraverse(BiTree T, Status(*visit)(TElemType e)) { if (T != NULL) { LQueue LQ; InitLQueue(&LQ); EnLQueue(&LQ, T); //先将根节点入队 while (IsEmptyLQueue(&LQ) == FALSE) { BiTree front = GetHeadLQueue(&LQ); //出队保存队头并访问 (*visit)(front->data); DeLQueue(&LQ); if (front->lchild != NULL) { EnLQueue(&LQ, front->lchild); //将出队结点的左子树根入队 } if (front->rchild != NULL) { EnLQueue(&LQ, front->rchild); //将出队结点的右子树根入队 } } return SUCCESS; } return ERROR; } /** * @name : int Value(BiTree T); * @description : 对构造出的前缀表达式二叉树求值 * @param : 二叉树根结点T * @note : 可在结点结构体中设置个Tag值标志数字与操作符来构造二叉树， * 可根据需要自行增加操作. */ //暂时记录数字的temp_num，计算的和sum，第一次的求和标志sum-flag int temp_num = 0, sum = 0, sum_flag = 0; LinkStack LS; //用来记录计算的中间量的栈 int Value(BiTree T) { temp_num = 0, sum = 0, sum_flag = 0; //初始化三个全局变量，用于新的计算 calculate(T); return sum; } /** * @name : void calculate(BiTree root); * @description : 对构造出的前缀表达式二叉树求值 * @param : 二叉树根结点root * @note : none */ void calculate(BiTree root) { if (root != NULL) { calculate(root->lchild); calculate(root->rchild); switch (root->data) { case '0': temp_num = 0; pushLStack(&LS, temp_num); break; case '1': temp_num = 1; pushLStack(&LS, temp_num); break; case '2': temp_num = 2; pushLStack(&LS, temp_num); break; case '3': temp_num = 3; pushLStack(&LS, temp_num); break; case '4': temp_num = 4; pushLStack(&LS, temp_num); break; case '5': temp_num = 5; pushLStack(&LS, temp_num); break; case '6': temp_num = 6; pushLStack(&LS, temp_num); break; case '7': temp_num = 7; pushLStack(&LS, temp_num); break; case '8': temp_num = 8; pushLStack(&LS, temp_num); break; case '9': temp_num = 9; pushLStack(&LS, temp_num); break; case '+': if (sum == 0 && sum_flag == 0) { sum_flag = 1; popLStack(&LS, &sum); //出栈并保存 popLStack(&LS, &temp_num); //出栈并保存 sum = temp_num + sum; } else { popLStack(&LS, &temp_num); sum += temp_num; } break; case '-': if (sum == 0 && sum_flag == 0) { sum_flag = 1; popLStack(&LS, &sum); popLStack(&LS, &temp_num); sum = temp_num - sum; } else { popLStack(&LS, &temp_num); sum -= temp_num; } break; case '*': if (sum == 0 && sum_flag == 0) { sum_flag = 1; popLStack(&LS, &sum); popLStack(&LS, &temp_num); sum = temp_num * sum; } else { popLStack(&LS, &temp_num); sum *= temp_num; } break; case '/': if (sum == 0 && sum_flag == 0) { sum_flag = 1; popLStack(&LS, &sum); popLStack(&LS, &temp_num); sum = temp_num / sum; } else { popLStack(&LS, &temp_num); sum /= temp_num; } break; default: break; } } } /** * @name : Status (*visit)(TElemType e) * @description : 对结点进行打印 * @param : 数据e * @note : none */ Status visit(TElemType e) { printf("%-2c", e); return SUCCESS; }