在c++语言如何利用后缀表达式构建表达式树
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
#include<bits/stdc++.h>
using namespace std;
// An expression tree node
struct et
{
char value;
et* left, *right;
};
// A utility function to check if 'c'
// is an operator
bool isOperator(char c)
{
if (c == '+' || c == '-' ||
c == '*' || c == '/' ||
c == '^')
return true;
return false;
}
// Utility function to do inorder traversal
void inorder(et *t)
{
if(t)
{
inorder(t->left);
printf("%c ", t->value);
inorder(t->right);
}
}
// A utility function to create a new node
et* 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 expression
et* constructTree(char postfix[])
{
stack<et *> st;
et *t, *t1, *t2;
// Traverse through every character of
// input expression
for (int i=0; i<strlen(postfix); i++)
{
// If operand, simply push into stack
if (!isOperator(postfix[i]))
{
t = newNode(postfix[i]);
st.push(t);
}
else // operator
{
t = newNode(postfix[i]);
// Pop two top nodes
t1 = st.top(); // Store top
st.pop(); // Remove top
t2 = st.top();
st.pop();
// make them children
t->right = t1;
t->left = t2;
// Add this subexpression to stack
st.push(t);
}
}
// only element will be root of expression
// tree
t = st.top();
st.pop();
return t;
}
// Driver program to test above
int main()
{
char postfix[] = "ab+ef*g*-";
et* r = constructTree(postfix);
printf("infix expression is \n");
inorder(r);
return 0;
}
