c++数据结构与算法

以中缀表达式创建表达式二叉树(递归算法)，以后根次序遍历计算表达式值。
采用类和对象，不使用结构体
操作环境：vs2022

#include <bits/stdc++.h>
#include <string>
#include <cmath>
using namespace std;
/*---------------------------二叉树的链式存储-----------------------*/
typedef struct BiTNode
{
    char data;    //结点数据域（符号）
    string combine_data;    //结点数据域（数值，可大于9）
    BiTNode *lchild, *rchild;    //左右孩子指针
}*BiTree;
/*------------------------------链式堆栈---------------------------*/
typedef struct StackNode
{
    BiTree data_tree;    //存储的是二叉树
    char data_op;    //存储的是符号
    StackNode *next;
}*LinkStack;
//栈的初始化
int InitStack(LinkStack &S)
{
    S = NULL;
    return 1;
}
//二叉树入栈
int Push_tree(LinkStack &S, BiTree e)
{
    LinkStack p = new StackNode;
    p->data_tree = e;
    p->next = S;
    S = p;
    return 1;
}
//字符（运算符号）入栈
int Push_op(LinkStack &S, char e)
{
    LinkStack p = new StackNode;
    p->data_op = e;
    p->next = S;
    S = p;
    return 1;
}
//二叉树出栈
int Pop_tree(LinkStack &S, BiTree &T1)
{
    if (S == NULL)    return 0;
    LinkStack p = S;
    T1 = p->data_tree;
    S = S->next;
    delete p;
    return 1;
}
//字符（运算符号）出栈
int Pop_op(LinkStack &S, char &ch)
{
    if (S == NULL)    return 0;
    LinkStack p = S;
    ch = p->data_op;
    S = S->next;
    delete p;
    return 1;
}

//取栈顶元素
char GetTop_op(LinkStack S)
{
    if (S != NULL)    return S->data_op;
    else return ' ';
}
BiTree GetTop_tree(LinkStack S)
{
    if (S != NULL)    return S->data_tree;
    else return NULL;
}
/*------------------------------表达式树的创建算法------------------------------*/
//创建以T为根结点的二叉树（存储符号）
void CreateExpTree(BiTree &T, BiTree a, BiTree b, char theta)//a是左孩子，b是右孩子,theta是数据域
{
    BiTree L = new BiTNode;
    L->data = theta;
    L->lchild = a;
    L->rchild = b;
    T = L;
}
//创建以T为根结点的二叉树（存储数值，可大于9）
//a是左孩子，b是右孩子,theta是数据域
void CreateExpTree_str(BiTree &T, BiTree a, BiTree b, string theta)
{
    BiTree L = new BiTNode;
    L->combine_data = theta;
    L->lchild = a;
    L->rchild = b;
    T = L;
}
//比较运算符的优先级
//top是栈顶元素，ch是需要比较的元素
char Precede(char top, char ch)
{
    if (ch == ')'&&top == '(')    return '=';
    else if (ch == ')')    return '>';
    if (top == ' ' || top == '(' || ch == '(') return '<';
    if (ch == '#')    return '>';
    if (top == '+' || top == '-') {
        if (ch == '+' || ch == '-')    return '>';
        else if (ch == '/' || ch == '*')    return '<';
    }
    else if (top == '*' || top == '/')    return '>';
}
//创建表达式树
//expt栈(根结点)，optr栈(运算符)
void InitExpTree(char ep[], LinkStack &expt, LinkStack &optr)
{
    int n = strlen(ep);
    int i = 0;
    BiTree T = NULL;    //树根
    BiTree T1 = NULL;    //左子树
    BiTree T2 = NULL;    //右子树
    char ch = ' ';    //弹出的符号
    string combine_str = "";    //存储数值，可大于9
    while (i != n)
    {
        if (ep[i] >= '0' && ep[i] <= '9') {        //数值（二叉树），进入expt栈中
            combine_str += ep[i];
            if (ep[i + 1] >= '0' && ep[i + 1] <= '9') {    //下一位仍是数字，需连接
                i++;
                continue;
            }
            CreateExpTree_str(T, NULL, NULL, combine_str);
            combine_str = "";    //建完数值的二叉树后string要置空
            Push_tree(expt, T);
            i++;
        }
        else {
            switch (Precede(GetTop_op(optr),ep[i]))        //比较优先级
            {
            case '<':
                Push_op(optr, ep[i]);
                i++;
                break;
            case '>':
                Pop_op(optr, ch);    //弹出上一个字符
                Pop_tree(expt, T1);    //弹出上两个数值（二叉树）
                Pop_tree(expt, T2);
                CreateExpTree(T, T2, T1, ch);    //以data_tree为根，连接T1和T2两颗子树
                Push_tree(expt, T);        //最后把T放进expt栈中
                break;
            case '=':
                Pop_op(optr, ch);
                i++;
                break;
            default:
                break;
            }
        }
    }
}
//表达式树的后序遍历
void PostOrder(BiTree T)
{
    if (T)
    {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        if (T->lchild == NULL&&T->rchild == NULL) {
            cout << T->combine_data << " ";
        }
        else cout << T->data << " ";
    }
}
/*-----------------------------表达式树的求值-------------------------------*/
//根据当前结点运算符的例子那个进行相应运算
double GetValue(char data, double lvalue, double rvalue)
{
    switch (data)
    {
    case '+':
        return lvalue + rvalue;
        break;
    case '-':
        return lvalue - rvalue;
        break;
    case '*':
        return lvalue * rvalue;
        break;
    case '/':
        return lvalue / rvalue;
        break;
    default:
        break;
    }
}
//把string字符转换成数值
double change(string str)
{
    int n = str.length(), m = str.length();
    double sum = 0;
    for (int i = 0; i < n; i++)
    {
        sum += (str[i] - '0') * pow(10, m - 1);
        m--;
    }
    return sum;
}
//遍历表达式树求表达式的值
double EvaluateExpTree(BiTree T)
{
    double lvalue =0, rvalue = 0;    //存放叶子结点的数据域初始为0
    if (T->lchild == NULL&&T->rchild == NULL)
        return change(T->combine_data);    //return T->data - '0';
    else {
        lvalue = EvaluateExpTree(T->lchild);    //相当于后序遍历二叉树
        rvalue = EvaluateExpTree(T->rchild);
        return GetValue(T->data, lvalue, rvalue);
    }
}
int main()
{
    LinkStack expt;
    InitStack(expt);    //初始化expt栈(根结点)
    LinkStack optr;
    InitStack(optr);    //初始化optr栈(运算符)

    char ep[] = "3+4*(6-1)-8/2#";    //"(18-2)*(13-7)+4/2#";

    InitExpTree(ep, expt, optr);    //构建表达式树
    BiTree T = NULL;
    Pop_tree(expt, T);    //获取最后建好的二叉树

    cout << "初始的中缀表达式: " << ep << endl;     //初始中缀表达式

    cout << "后序遍历: ";
    PostOrder(T);        //后序遍历结果
    cout << endl;

    cout << "表达式求值后的结果: " << EvaluateExpTree(T) << endl;    //表达式树求值结果

    return 0;
}

一楼的回答很OK