表达式树

表达式树基础知识

表达式树是一类树，基本结构是所有的叶节点为操作树，非叶节点为操作符。如下图所示：

image.png

struct TreeNode
{
    char data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(char inData): data(inData), left(nullptr), right(nullptr) {}
};

//true-操作符,false-操作数
bool isOperator(char inCh)
{
    if (inCh >= 'a' && inCh <= 'z') {
        return false;   
    }
    return true;
}


TreeNode *BuildExpressionTree(const char *inExpression)
{
    if (inExpression == nullptr || *inExpression == '\0') {
        return nullptr;
    }
    const char *cycleIter = inExpression;
    stack<TreeNode *> treeStack;
    while (*cycleIter != '\0') {
        if (!isOperator(*cycleIter)) {
            TreeNode *newNode = new TreeNode(*cycleIter);
            treeStack.push(newNode);
        }
        else {
            TreeNode *newNode = new TreeNode(*cycleIter);
            newNode->right = treeStack.top(); treeStack.pop();
            newNode->left = treeStack.top(); treeStack.pop();
            treeStack.push(newNode);
        }
        ++cycleIter;
    }
    return treeStack.top();
}