1、可能在读这篇经验之前，大家肯能对表达式树没有一个清晰地概念。那么在第一步，将简单介绍一下表达式树。它是二叉树的一种，也就是说一个节点最多有两个子节点，每个节点用于存储操作数与操作符。拿中缀表达式3 + ((5+9)*2)举个例子，它的表达式树如下图所示。
2、【构建表达式树的算法】为了构建一个釉涑杵抑表达式树，我们将使用堆栈结构。扫描输入的后缀表达式每一个字符，对每一个字符做如下事情：（1）如果字符是一个操作数，那么我们就将该操作数存入树节点中，将节点压入（push）堆栈中。（2）如果字符是一个操作符，那么就从堆栈中压出(pop)两个树节点，构成当前操作符的树节点的左子树和右子树。然后将当前节点压入（push）进堆栈当中。扫描后缀表达式完毕之后，在堆栈中唯一的节点是表达式树的根节点，我们可以通过根节点遍历整个表达式树。拿后缀表达式a b + c d e + * *，解释一下具体步骤。
3、前两个字符是操作数a,b，我们构建两个单节点的树结构，并将这指向两个树结构的指针压入堆栈当中。
4、接下来的字符是操作符‘+’，将堆栈中指向树的两个指针压出，构建一个新的树，并将指向新树根节点的指针压入堆栈当中。
5、接下来字符是三个操作数'c'、'd'、'e'，将对应的单节点树的指针压入到堆栈当中。
6、与以上两步类似，进行操作。扫描输入的后缀表达式完毕之后，在堆栈中剩余的树就是我们所需要的表达式树。
7、在最后，我们提供该c++代码供各位读者参考。最后结果如下图。// C++ program for expression tree#in艘早祓胂clude<bits/stdc++.h>using namespace std;// An expression tree nodestruct et{char value;et* left, *right;};// A utility function to check if 'c'// is an operatorbool isOperator(char c){if (c == '+' || c == '-' ||c == '*' || c == '/' ||c == '^')return true;return false;}// Utility function to do inorder traversalvoid inorder(et *t){if(t){inorder(t->left);printf("%c ", t->value);inorder(t->right);}}// A utility function to create a new nodeet* newNode(int v){et *temp = new et;temp->left = temp->right = NULL;temp->value = v;return temp;};// Returns root of constructed tree for given// postfix expressionet* constructTree(char postfix[]){stack<et *> st;et *t, *t1, *t2;// Traverse through every character of// input expressionfor (int i=0; i<strlen(postfix); i++){// If operand, simply push into stackif (!isOperator(postfix[i])){t = newNode(postfix[i]);st.push(t);}else // operator{t = newNode(postfix[i]);// Pop two top nodest1 = st.top(); // Store topst.pop(); // Remove topt2 = st.top();st.pop();// make them childrent->right = t1;t->left = t2;// Add this subexpression to stackst.push(t);}}// only element will be root of expression// treet = st.top();st.pop();return t;}// Driver program to test aboveint main(){char postfix[] = "ab+ef*g*-";et* r = constructTree(postfix);printf("infix expression is \n");inorder(r);return 0;}
