C ++程序为给定的前缀表达式构造一个表达式树
表达式树基本上是用于表示表达式的二叉树。在表达式树中，内部节点对应于运算符，每个叶节点对应于操作数。这是一个C++程序，用于按顺序，前顺序和后顺序遍历为前缀Expression构造一个表达式树。
算法
Begin
class ExpressionTree which has following functions:
function push() to push nodes into the tree:
If stack is null
then push the node as first element
Else
push the node and make it top
function pop() to pop out nodes from the tree:
If stack is null
then print underflow
Else
Pop out the node and update top
function insert() to insert characters:
If it is digit
then push it.
Else if it is operator
Then pop it.
Else
Print “invalid Expression”
function postOrder() for postorder traversal:
If tree is not empty
postOrder(ptr->l)
postOrder(ptr->r)
Print root as ptr->d
function inOrder() for inorder traversal:
If tree is not empty
inOrder(ptr->l)
Print root as ptr->d
inOrder(ptr->r)
function preOrder() for preorder traversal:
If tree is not empty
Print root as ptr->d
preOrder(ptr->l)
preOrder(ptr->r)
End范例程式码
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;
class TreeN//node declaration {
public: char d;
TreeN *l, *r;
TreeN(char d) {
this->d = d;
this->l = NULL;
this->r = NULL;
}
};
class StackNod// stack declaration {
public: TreeN *treeN;
StackNod *n;
StackNod(TreeN*treeN)//constructor {
this->treeN = treeN;
n = NULL;
}
};
class ExpressionTree {
private: StackNod *top;
public: ExpressionTree() {
top = NULL;
}
void clear() {
top = NULL;
}
void push(TreeN *ptr) {
if (top == NULL)
top = new StackNod(ptr);
else {
StackNod *nptr = new StackNod(ptr);
nptr->n = top;
top = nptr;
}
}
TreeN *pop() {
if (top == NULL) {
cout<<"Underflow"<<endl;
} else {
TreeN *ptr = top->treeN;
top = top->n;
return ptr;
}
}
TreeN *peek() {
return top->treeN;
}
void insert(char val) {
if (isDigit(val)) {
TreeN *nptr = new TreeN(val);
push(nptr);
} else if (isOperator(val)) {
TreeN *nptr = new TreeN(val);
nptr->l = pop();
nptr->r= pop();
push(nptr);
} else {
cout<<"Invalid Expression"<<endl;
return;
}
}
bool isDigit(char ch) {
return ch >= '0' && ch <= '9';
}
bool isOperator(char ch) {
return ch == '+' || ch == '-' || ch == '*' || ch == '/';
}
int toDigit(char ch) {
return ch - '0';
}
void buildTree(string eqn) {
for (int i = eqn.length() - 1; i >= 0; i--)
insert(eqn[i]);
}
void postfix() {
postOrder(peek());
}
void postOrder(TreeN*ptr) {
if (ptr != NULL) {
postOrder(ptr->l);
postOrder(ptr->r);
cout<<ptr->d;
}
}
void infix() {
inOrder(peek());
}
void inOrder(TreeN *ptr) {
if (ptr != NULL) {
inOrder(ptr->l);
cout<<ptr->d;
inOrder(ptr->r);
}
}
void prefix() {
preOrder(peek());
}
void preOrder(TreeN *ptr) {
if (ptr != NULL) {
cout<<ptr->d;
preOrder(ptr->l);
preOrder(ptr->r);
}
}
};
int main() {
string s;
ExpressionTree et;
cout<<"\nEnter equation in Prefix form: ";
cin>>s;
et.buildTree(s);
cout<<"\nPrefix : ";
et.prefix();
cout<<"\n\nInfix : ";
et.infix();
cout<<"\n\nPostfix : ";
et.postfix();
}输出结果
Enter equation in Prefix form: ++7*626 Prefix : ++7*626 Infix : 7+6*2+6 Postfix : 762*+6+