表达式求值常用的三个方法

1. 表达式树
2. 中缀转前缀，后缀表达式利用（数字，运算符）栈来求值
3. 中缀表达式嵌套递归（我比较常用）

---

嵌套递归方法主结构

pair<int,int> fac(int begin){

deque<int> nums;

deque<char> opers;

int cur = 0;

while(begin<str.length()&&str[begin]!=')'){
    
    if(str[begin]>='0'&&str[begin]<='9'){
        
        cur = cur*10+str[begin]-'0';
        
    }
    if(str[begin]=='+'||str[begin]=='-'||str[begin]=='*'||str[begin]=='/'||str[begin]=='^'){
        
      
        mypush(nums, opers, str[begin], cur);
        
        
         cur=0;
    }
    
    if(str[begin]=='('){
        
        pair<int,int> res = fac(begin+1);
        
        cur = res.second;
        
        begin = res.first;
    }
    
    begin++;
    
}

mypush(nums, opers, '+', cur);

opers.pop_back();

int res = cal(nums, opers);


return {begin,res};

}

数字和运算符入栈方法

void mypush(deque<int> &nums,deque<char> &opers,char oper,int cur){
    
         if(oper=='^'){
                  
                  if(!opers.empty()&&opers.back()=='^'){
                      
                      opers.pop_back();
                      
                      int back = nums.back();
                      
                      nums.pop_back();
                      
                      nums.push_back((int)pow(back,cur));
                      
                      opers.push_back(oper);
                      
                     
                    }
                  
                  else{
                      
                      nums.push_back(cur);
                      
                      opers.push_back(oper);
                      
                      
                  }
                  
                  
              }
              else{
                  
                  if(!opers.empty()&&opers.back()=='^'){
                      
                      opers.pop_back();
                      
                      int back = nums.back();
                      
                      nums.pop_back();
                      
                      int temp = (int)pow(back,cur);
                      
                      if(!opers.empty()&&opers.back()=='*'){
                          
                          opers.pop_back();
                          
                          int b1 = nums.back()*temp;
                          
                          nums.pop_back();
                          
                          nums.push_back(b1);
                          
                          opers.push_back(oper);
                          
                      }
                      else if(!opers.empty()&&opers.back()=='/'){
                          
                          opers.pop_back();
                          
                          int b2 = nums.back()/temp;
                          
                          nums.pop_back();
                          
                          nums.push_back(b2);
                          
                          opers.push_back(oper);
                          
                          
                      }
                      else{
                          
                          nums.push_back(temp);
                          
                          opers.push_back(oper);
                          
                          
                      }
                      
                  }
                  else{
                      
                      if(!opers.empty()&&opers.back()=='*'){
                          
                          opers.pop_back();
                          
                          int c1 =  nums.back()*cur;
                          
                          nums.pop_back();
                          
                          nums.push_back(c1);
                          
                          opers.push_back(oper);
                          
                      }
                      else if(!opers.empty()&&opers.back()=='/'){
                          
                          opers.pop_back();
                                               
                          int c2 =  nums.back()/cur;
                                               
                          nums.pop_back();
                                               
                          nums.push_back(c2);
                          
                          opers.push_back(oper);
                          
                          
                      }
                      else{
                          
                          nums.push_back(cur);
                          
                          opers.push_back(oper);
                          
                          
                      }
                      
                      
                  }
                  
                  
                  
              }
              
    }

---

计算结果方法

int cal(deque<int> &nums,deque<char> &opers){
    
    
    while(nums.size()>1){
        
        int left = nums.front();
        
        nums.pop_front();
        
        int right = nums.front();
        
        nums.pop_front();
        
        char oper = opers.front();
        
        opers.pop_front();
        
        if(oper=='+'){
            
            
            nums.push_front(left+right);
            
            
        }
        
        if(oper=='-'){
            
            nums.push_front(left-right);
            
            
        }
        
    }
    
    
    int ans = nums.front();
    
    return ans;
    
}

---

完整代码

#include <bits/stdc++.h>
using namespace std;

string str;


void mypush(deque<int> &nums,deque<char> &opers,char oper,int cur){
    
         if(oper=='^'){
                  
                  if(!opers.empty()&&opers.back()=='^'){
                      
                      opers.pop_back();
                      
                      int back = nums.back();
                      
                      nums.pop_back();
                      
                      nums.push_back((int)pow(back,cur));
                      
                      opers.push_back(oper);
                      
                     
                    }
                  
                  else{
                      
                      nums.push_back(cur);
                      
                      opers.push_back(oper);
                      
                      
                  }
                  
                  
              }
              else{
                  
                  if(!opers.empty()&&opers.back()=='^'){
                      
                      opers.pop_back();
                      
                      int back = nums.back();
                      
                      nums.pop_back();
                      
                      int temp = (int)pow(back,cur);
                      
                      if(!opers.empty()&&opers.back()=='*'){
                          
                          opers.pop_back();
                          
                          int b1 = nums.back()*temp;
                          
                          nums.pop_back();
                          
                          nums.push_back(b1);
                          
                          opers.push_back(oper);
                          
                      }
                      else if(!opers.empty()&&opers.back()=='/'){
                          
                          opers.pop_back();
                          
                          int b2 = nums.back()/temp;
                          
                          nums.pop_back();
                          
                          nums.push_back(b2);
                          
                          opers.push_back(oper);
                          
                          
                      }
                      else{
                          
                          nums.push_back(temp);
                          
                          opers.push_back(oper);
                          
                          
                      }
                      
                  }
                  else{
                      
                      if(!opers.empty()&&opers.back()=='*'){
                          
                          opers.pop_back();
                          
                          int c1 =  nums.back()*cur;
                          
                          nums.pop_back();
                          
                          nums.push_back(c1);
                          
                          opers.push_back(oper);
                          
                      }
                      else if(!opers.empty()&&opers.back()=='/'){
                          
                          opers.pop_back();
                                               
                          int c2 =  nums.back()/cur;
                                               
                          nums.pop_back();
                                               
                          nums.push_back(c2);
                          
                          opers.push_back(oper);
                          
                          
                      }
                      else{
                          
                          nums.push_back(cur);
                          
                          opers.push_back(oper);
                          
                          
                      }
                      
                      
                  }
                  
                  
                  
              }
              
    }



int cal(deque<int> &nums,deque<char> &opers){
    
    
    while(nums.size()>1){
        
        int left = nums.front();
        
        nums.pop_front();
        
        int right = nums.front();
        
        nums.pop_front();
        
        char oper = opers.front();
        
        opers.pop_front();
        
        if(oper=='+'){
            
            
            nums.push_front(left+right);
            
            
        }
        
        if(oper=='-'){
            
            nums.push_front(left-right);
            
            
        }
        
    }
    
    
    int ans = nums.front();
    
    return ans;
    
}



pair<int,int> fac(int begin){
    
    deque<int> nums;
    
    deque<char> opers;
    
    int cur = 0;
    
    while(begin<str.length()&&str[begin]!=')'){
        
        if(str[begin]>='0'&&str[begin]<='9'){
            
            cur = cur*10+str[begin]-'0';
            
        }
        if(str[begin]=='+'||str[begin]=='-'||str[begin]=='*'||str[begin]=='/'||str[begin]=='^'){
            
          
            mypush(nums, opers, str[begin], cur);
            
            
             cur=0;
        }
        
        if(str[begin]=='('){
            
            pair<int,int> res = fac(begin+1);
            
            cur = res.second;
            
            begin = res.first;
        }
        
        begin++;
        
    }
    
    mypush(nums, opers, '+', cur);
    
    opers.pop_back();
    
    int res = cal(nums, opers);
    
    
    return {begin,res};
    
}



int main(){
    
    cin>>str;
    
    pair<int,int> res = fac(0);
    
    cout<<res.second<<endl;
    
    return 0;
}