二叉树的应用：求解四则运算

#include "stdio.h"
#include 
using namespace std;

template 
struct BTreeNode
{
    T key;
    BTreeNode *left;
    BTreeNode *right;
    BTreeNode *parent;
};

struct Operator
{
    char *cOperatorVal;
    int nPriority;
};

static Operator OPERATOR[] = {{"+", 1},{"-", 1},{"*", 2},{"/", 2}};
#define NUM_PRIORITY 10    // 自定义数字的优先级

template 
class BTree
{
public:
    explicit BTree() : m_pTree(NULL),m_pCurrentNode(NULL)
    {

    }
    ~BTree()
    {
        DestroyTree(m_pTree);
        m_pTree = NULL;
        m_pCurrentNode = NULL;
    }

    bool IsOperator(T key)
    {
        for (int i = 0; i <sizeof(OPERATOR)/sizeof(OPERATOR[0]); i ++)
        {
            if (0 == strcmp(key, OPERATOR[i].cOperatorVal))
            {
                return true;
            }
        }

        return false;
    }

    // 根据操作符得到其优先级
    int GetPriority(T key)  
    {
        for (int i = 0; i <sizeof(OPERATOR)/sizeof(OPERATOR[0]); i ++)
        {
            if (strcmp(key, OPERATOR[i].cOperatorVal) == 0)
            {
                return OPERATOR[i].nPriority;
            }
        }

        return NUM_PRIORITY;
    }

    BTreeNode* AddNode(T key)
    {
        BTreeNode *pNode = (BTreeNode *)malloc(sizeof(BTreeNode));
        pNode->key = key;
        pNode->parent = NULL;
        pNode->left = NULL;
        pNode->right = NULL;
        
        if (m_pTree == NULL)
        {
            m_pTree = pNode;
            m_pCurrentNode = pNode;
            return m_pTree;
        }

        // 若是数字，添加到上个结点的左边，若左边已有，则加右边
        // 若是运算符，首先比较和头结点云算法的优先级
        // (1)若为同优先级则当前运算符为新头结点，之前的为其左子树
        // (2)若为高优先级则为当前非符号的父节点，之前的为其左子树
        if (IsOperator(key))
        {
            if (GetPriority(key) <= GetPriority(m_pTree->key))
            {
                pNode->left = m_pTree;
                m_pTree->parent = pNode;
                m_pTree = pNode;
            }
            else
            {
                // 若操作符优先级很高
                pNode->parent = m_pCurrentNode->parent;
                if (m_pCurrentNode == m_pCurrentNode->parent->left)
                {
                    m_pCurrentNode->parent->left = pNode;
                }
                else
                {
                    m_pCurrentNode->parent->right = pNode;
                }

                pNode->left = m_pCurrentNode;
                m_pCurrentNode->parent = pNode;
            }
        }
        else
        {
            if (m_pCurrentNode->left == NULL)
            {
                m_pCurrentNode->left = pNode;
            }
            else
            {
                m_pCurrentNode->right = pNode;
            }

            pNode->parent = m_pCurrentNode;
        }
        m_pCurrentNode = pNode;
        return m_pTree;
    }

    void PreOrder(BTreeNode * pNode)
    {
        if (pNode != NULL)
        {
            cout <key <<" ";
            PreOrder(pNode->left);
            PreOrder(pNode->right);
        }
    }

    void MidOrder(BTreeNode * pNode)
    {
        if (pNode != NULL)
        {
            MidOrder(pNode->left);
            cout <key <<" ";
            MidOrder(pNode->right);
        }
    }

    void DestroyTree(BTreeNode * pNode)
    {
        if (pNode != NULL)
        {
            DestroyTree(pNode->left);
            DestroyTree(pNode->right);
            free(pNode);
        }
    }
    
    // 计算
    int PreOrderCalc(BTreeNode * pNode)
    {
        int num1, num2, result;
        if (IsOperator(pNode->key))
        {
            // 递归先序遍历计算num1
            num1 = PreOrderCalc(pNode->left);
            // 递归先序遍历计算num2
            num2 = PreOrderCalc(pNode->right);
            char optr = *(char *)pNode->key;

            switch (optr)
            {
            case '+':
                result = num1 + num2;
                break;
            case '-':
                result = num1 - num2;
                break;
            case '*':
                result = num1 * num2;
                break;
            case '/':
                if (num2 == 0)
                {
                    cout <<"除数不能为0！" << endl;
                }
                result = num1 / num2;
                break;
            }

            return result;
        }
        result = atoi(pNode->key);
        return result;

    }

private:
    BTreeNode *m_pTree;
    BTreeNode *m_pCurrentNode;
};
void main()
{
    BTree<char *> tree;
    tree.AddNode("3");
    tree.AddNode("+");
    tree.AddNode("2");
    tree.AddNode("*");
    tree.AddNode("9");
    tree.AddNode("-");
    tree.AddNode("16");
    tree.AddNode("/");
    BTreeNode<char *> *pNode = tree.AddNode("4");
    
    cout <<"前序遍历：";
    tree.PreOrder(pNode);
    cout << endl;

    cout <<"中序遍历为表达式：";
    tree.MidOrder(pNode);
    cout << endl;

    int a = tree.PreOrderCalc(pNode);
    cout <<"计算结果为：" <endl;

    return;
}