[复试机试]已知中序表达式，求先序表达式

  1 #include<iostream>
  2 #include<stack>
  3 #include<string>
  4 using namespace std;
  5 typedef struct no
  6 {
  7     char data;
  8     struct no *lchild,*rchild;
  9 }*node;
 10 int getpr(char a)
 11 {
 12     if(a==‘+‘||a==‘-‘) return 1;
 13     if(a==‘*‘||a==‘/‘)return 2;
 14     if(a==‘(‘||a==‘)‘)return 0;
 15 }
 16 string res(string in){///转为后缀表达式，即后续遍历
 17     stack<char> st;
 18     string post="";
 19     for(int i=0; i<in.length(); i++){
 20         if(in[i]==‘+‘||in[i]==‘-‘||in[i]==‘*‘||in[i]==‘/‘){
 21             if(!st.empty()){
 22                 if(getpr(in[i])>getpr(st.top()))///根据符号的优先级
 23                     st.push(in[i]);
 24                 else{
 25                     while(getpr(in[i]) <= getpr(st.top())){
 26                         if(getpr(in[i])>getpr(st.top()))
 27                             break;
 28                         post += st.top();
 29                         st.pop();
 30                         if(st.empty())
 31                             break;
 32                     }
 33                     st.push(in[i]);
 34                 }
 35             }
 36             if(st.empty())
 37                 st.push(in[i]);
 38         }
 39         if(in[i]==‘(‘)
 40             st.push(in[i]);
 41         if(in[i]==‘)‘){
 42             while(st.top()!=‘(‘){
 43                 if(st.top()==‘(‘)break;
 44                 post+=st.top();
 45                 st.pop();
 46             }
 47             st.pop();
 48         }
 49         if(in[i]!=‘+‘&&in[i]!=‘-‘&&in[i]!=‘/‘&&in[i]!=‘*‘&&in[i]!=‘(‘&&in[i]!=‘)‘)
 50             post+=in[i];///不是符号，则直接提取
 51     }
 52     while(!st.empty()){
 53         post+=st.top();
 54         st.pop();
 55     }
 56     return post;
 57 }
 58 node create(string sa )///根据后序遍历，建树
 59 {
 60     node ss;
 61     stack<node>st;
 62     for(int i=0; i<sa.length(); i++){
 63         if(sa[i]!=‘+‘&&sa[i]!=‘-‘&&sa[i]!=‘/‘&&sa[i]!=‘*‘){///一定是叶子结点
 64             ss=new no();
 65             ss->data=sa[i];
 66             ss->lchild=ss->rchild=NULL;
 67         }
 68         else{///非叶子结点，赋值其左右子孩子
 69             ss=new no();
 70             ss->data=sa[i];
 71             ss->rchild=st.top();
 72             st.pop();
 73             ss->lchild=st.top();
 74             st.pop();
 75         }
 76         st.push(ss);
 77     }
 78     return st.top();
 79 }
 80 void pre(node sa)
 81 {
 82     if(sa!=NULL){
 83         cout<<sa->data;
 84         pre(sa->lchild);
 85         pre(sa->rchild);
 86     }
 87 }
 88 int main()
 89 {
 90     cout<<"请输入中缀表达式："<<endl;
 91     string in,post;
 92     node head;
 93     head=new no();
 94     cin>>in;
 95     cout<<"转换为后缀表达式为："<<endl;
 96     post=res(in);
 97     cout<<post<<endl;
 98     cout<<"构建表达式树"<<endl;
 99     head=create(post);
100     cout<<"这颗表达式树的前缀表达式为："<<endl;
101     pre(head);
102     cout<<endl;
103 }