在c++语言如何利用后缀表达式构建表达式树

1、可能在读这篇经验之前，大家肯能对表达式树没有一个清晰地概念。那么在第一步，将简单介绍一下表达式树。它是二叉树的一种，也就是说一个节点最多有两个子节点，每个节点用于存储操作数与操作符。拿中缀表达式3 + ((5+9)*2)举个例子，它的表达式树如下图所示。

3、前两个字符是操作数a,b，我们构建两个单节点的树结构，并将这指向两个树结构的指针压入堆栈当中。

5、接下来字符是三个操作数'c'、'd'、'e'，将对应的单节点树的指针压入到堆栈当中。

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;}