基于二叉树的算术表达式计算与实现

最近做题时遇到一道很有意思的题，当时思考了很久没有思路，最后在借鉴下面这篇文章后做了出来：
基于二叉树的算术表达式计算与实现

题目如下

表达式树是二叉树的一种应用，叶子是操作数，其余结点为操作符。例如，下图表示的表达式树，用中序遍历得到中序表达式 (a+bc)+(（de+f）*g）

题目

就是这么一道题，想了好久没想出来(自己太菜了，以后要多多码代码了.jpg）,看了上面那篇文章之后，自己参考着写了些，现在总结一下思路：

首先我们看一下题上给的这个中缀表达式，和图片对应后我们可以发现最上面的根节点就是括号外面的那个节点，其中有这么几条规则：
1.如果括号外有有+或者-，那么一定是最后一个+或者-最后运算
例如:(2+5)x3-5/2,这里的减号一定是最后计算的；

2.如果括号外有x或者/而且没有+或者-，那么x或者/一定是最后计算的

所以，我们就可以利用这个来解决中缀表达式转换为对应后缀表达式二叉树的形式

toTree()函数：
-接收到一个字符串
-扫描字符串，寻找括号外面的符号，如果括号外面存在符号，按照上面的两个规则定义根节点，并递归定义左孩子节点和右孩子节点

-如果没有，说明这个算术表达式被括号包起来，那就去掉括号后继续递归

目前实现了以下功能

• 转换字母形式的中缀表达式，如(a-b)*c
• 转换多位数和单位整数形式的中缀表达式,如(29-23)*7/(2+3)
• 转换存在负数的中缀表达式，但是负数必须用()括起来，如：
  (-14x5)/2 必须表示为 ((-14)x5)/2才能够正常转换

PS:以上字母和括号、符号全部在英文输入法下输入终端

代码如下，有注释，应该不难懂：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define Max 200
#define notNumber 0x7fffffff  //最大的int类型，用于最为一个判断标志

struct Tree
{
    int flag; //标志段，0表示数字，1表示字符
    int data; //数据段
    char cha;
    Tree *lchild; //左孩子节点
    Tree *rchild; //右孩子节点
};

int check(char a[], int start, int end)
{ //判断是否只剩下了数字
    int number = 0;
    int flag = 1;  //正数和负数标志
    if (a[start] == '-')
    {
        flag = -1;
        start++;
    }
    for (int i = start; i < end; i++)
    {
        if (!isdigit(a[i]))
            return notNumber;
        number = number * 10 + (a[i] - '0');
    }
    return number * flag;
}

Tree *changeToTree(char a[], int start, int end)
{

    int number = check(a, start, end); //判断当前字符串内是不是只剩下了数字
    if (number != notNumber)
    { //如果字符串只有数字 
        Tree *root = (Tree *)malloc(sizeof(Tree));
        root->flag = 0;
        root->data = number;
        root->lchild = NULL;
        root->rchild = NULL;
        return root;
    }
    if(start==end-1){ //弥补上方的数字格式，用于输出字母表达式
        Tree *root = (Tree *)malloc(sizeof(Tree));
        root->flag = 1;
        root->cha = a[start];
        root->lchild = NULL;
        root->rchild = NULL;
        return root;

    }
    int posAddOrSub = -1; //最后一个+或者-运算符号的位置
    int posMulOrDiv = -1; //最后一个*或者/运算符号的位置
    int flags = 0;        //?????
    for (int i = start; i < end; i++)
    { //遍历字符串，寻找括号外的运算符
        if (a[i] == '(')
            flags++;
        else if (a[i] == ')')
            flags--;
        if (flags == 0)
        { //如果当前符号在括号外
            if (a[i] == '+' || a[i] == '-')
                posAddOrSub = i;
            else if (a[i] == '*' || a[i] == '/')
                posMulOrDiv = i;
        }
    }

    if (posAddOrSub > 0)
    { //存在+或者-，那么最后一个+或-符号就是根节点
        Tree *root = (Tree *)malloc(sizeof(Tree));
        root->flag = 1; //+?-????flag??1
        root->cha = a[posAddOrSub];
        root->lchild = changeToTree(a, start, posAddOrSub);
        root->rchild = changeToTree(a, posAddOrSub + 1, end);
        return root;
    }
    else if (posMulOrDiv > 0)
    { //如果括号外存在*或者/，那么最后一个运算符就是根节点
        Tree *root = (Tree *)malloc(sizeof(Tree));
        root->flag = 1; //*?/???
        root->cha = a[posMulOrDiv];
        root->lchild = changeToTree(a, start, posMulOrDiv);
        root->rchild = changeToTree(a, posMulOrDiv + 1, end);
        return root;
    }

    else if (posAddOrSub == -1 && posMulOrDiv == -1)
    { //如果括号外不存在运算符号，那么说明这个表达式被()包围，去掉括号递归转换
        return changeToTree(a, start + 1, end - 1);
    }
}

void showTree(Tree *root)
{
    if (root)
    {
        //后序遍历输出树
        showTree(root->lchild); //输出左孩子
        showTree(root->rchild); //输出右孩子
        if (root->flag == 0)    //输出当前节点
        {
            printf("%d", root->data);
        }
        else
        {
            printf("%c", root->cha);
        }
    }
}

int main()
{
    char a[Max];
    printf("Please enter the value of the arithmetic expression: (negative numbers are enclosed in parentheses):\n");
    scanf("%s", a);
    int start = 0;
    int end = 0;
    Tree *root = (Tree *)malloc(sizeof(Tree));
    while (a[end] != '\0')
    { //记录字符串的长度
        end++;
    }
    root = changeToTree(a, start, end);
    showTree(root);

    printf("\n---------------------------\n");
    printf("---------end---------------\n");
    system("pause");
    return 0;
}