表达式树基础知识
表达式树是一类树，基本结构是所有的叶节点为操作树，非叶节点为操作符。如下图所示：
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();
}
