用二叉树实现中缀表达式转换成后缀表达式

#include<iostream> #include<stack> #include<string> #include<iomanip> using namespace std; class Tree_Node { public: char oper; Tree_Node *left; Tree_Node *right; Tree_Node(char op){ left=right=NULL; oper=op; } }; inline void free_Tree(Tree_Node *p) { if(p->left!=NULL){ free_Tree(p->left); } if(p->right!=NULL){ free_Tree(p->right); } delete(p); } int prioritySX(char op) { switch(op){ case '(': return 1; case '+': case '-': return 2; case '*': case '/': return 3; case '^': return 4; default: return 0; } } bool judge(char op) { char opera[]={'(',')','+','-','*','/','^'}; for(int i=0;i<sizeof(opera);i++){ if(op==opera[i]){ return true; } } return false; } void post_order(Tree_Node *p) { if(p){ post_order(p->left); post_order(p->right); cout<<p->oper; } } void draw_Tree(int index,Tree_Node *p) { if(p){ draw_Tree(index+8,p->right); cout<<setw(index)<<p->oper<<endl; draw_Tree(index+8,p->left); } } void build_Tree(Tree_Node *&p, string a) { char ch,c; int index=0; stack<char> sk1; stack<Tree_Node*> sk2; ch=a[index++]; while(sk1.size()!=0 || ch!='\0'){ if(ch!='\0' && !judge(ch)){ p=new Tree_Node(ch); sk2.push(p); ch=a[index++]; } else{ switch(ch){ case '(': sk1.push('('); ch=a[index++]; break; case ')': while(true){ c=sk1.top(); sk1.pop(); if(c=='(') break; p=new Tree_Node(c); if(sk2.size()){ p->right=sk2.top(); sk2.pop(); } if(sk2.size()){ p->left=sk2.top(); sk2.pop(); } sk2.push(p); } ch=a[index++]; break; default: if(sk1.size()==0 || (ch!='\0' && prioritySX(sk1.top())< prioritySX(ch))){ sk1.push(ch); ch=a[index++]; } else{ p=new Tree_Node(sk1.top()); if(sk2.size()){ p->right=sk2.top(); sk2.pop(); } if(sk2.size()){ p->left=sk2.top(); sk2.pop(); } sk2.push(p); sk1.pop(); } break; } } } p=sk2.top(); sk2.pop(); } int main() { int test; string s; Tree_Node *tree; cout<<"【请输入需要转换的表达式个数:】"<<endl; cin>>test; while(test--){ cout<<"\n【请输入一个中缀表达式:】"<<endl;; cin>>s; build_Tree(tree,s); cout<<"\n【建好的表达式树:】"<<endl; draw_Tree(0,tree); cout<<"\n【转换之后的后缀表达式为:】"<<endl; post_order(tree); cout<<endl; free_Tree(tree); cout<<endl; } return 0; }