2017-06-27 19:19:18

第一步需要将中缀表达式转为后缀表达式。这步的转化可以说是本题的核心。

主要的转化手段是利用栈，有如下几个规则：

• 数字直接输出
• "("直接进栈
• ")"将栈中元素出栈直到遇到"("
• 其他运算符需要和栈顶元素比较优先级，如果栈顶元素的优先级小于等于待操作的运算符的，则需要出栈并输出。直到栈顶元素的优先级大于待处理元素
• 最后需要将栈中元素清空，全部输出

int toint(string in){    int rst;    stringstream ss;    ss<
     
      >rst;    return rst;}int priority(char a){    switch(a)    {    case '*': return 2;    case '/': return 2;    case '+': return 1;    case '-': return 1;    case '(': return 3;    case ')': return 3;    }}bool isdig(char a){    if(a>='0'&&a<='9') return true;    else return false;}//保证每次入栈的符号的优先级都比当前的栈顶元素要高，若此时栈顶的优先级比入栈元素低或者等于的话，则需要出栈//知道遇到比当前需要入栈元素优先级高的为止void midtopost(string in,vector
      
       & vec){     stack
       
         s;     string rst="";     int i=0;     while(true)     {              if(i>=in.length()) break;         if(isdig(in[i]))         {             string num="";             while(isdig(in[i])) num+=in[i++];             vec.push_back(num);         }         else         {             if(s.empty()) s.push(in[i++]);             else             {                 if(in[i]=='(') {s.push(in[i]);}                 else if(in[i]==')')                 {                     while(s.top()!='(')                      {                         string temp="";                         temp+=s.top();                         vec.push_back(temp);                         s.pop();                     }                     s.pop();                 }                 else                 {                     if(priority(in[i])>priority(s.top())||s.top()=='(') s.push(in[i]);                     else                     {                         //判断是否为空必须写在前面，符合短路原则                         while(!s.empty()&&(priority(in[i])<=priority(s.top())))                         {                             string temp="";                             temp+=s.top();                             vec.push_back(temp);                             s.pop();                         }                         s.push(in[i]);                     }                 }                 ++i;             }         }     }     //清空栈     while(!s.empty())     {         string temp="";         temp+=s.top();         vec.push_back(temp);         s.pop();     }}//后缀表达式的计算，数字进栈，符号将栈顶两个元素出栈，运算后进栈int calc(vector
        
         & vec){    stack
         
           s;    for(int i=0;i
          
            vec; midtopost(in,vec); cout<
           
            <