面试题 16.26. 计算器【双栈 vs 直接求值】

╰半橙微兮° 2022-10-22 07:57 8阅读 0赞

**双栈法**

#define debug(x) cout<<#x<<": "<<(x)<<endl;
    
    class Solution { 
    public:
        int calculate(string s) { 
            
            int i=0;
            int len = s.size();
            
            auto isop = [&](char c){ 
                if(c == '+' ||c == '-' ||c == '*' ||c == '/' ){ 
                    return true;
                }
                return false;
            };
    
            auto isn = [&](char c){ 
                if(c >=  '0' && c <='9' ){ 
                    return true;
                }
                return false;
            };
    
            auto getn = [&](){ 
                int ret=0;
                while(i<len && s[i]==' ')i++;
                while(i<len && isn(s[i])){ 
                    ret *= 10;
                    ret += s[i]-'0';
                    i++;
                }
                while(i<len && s[i]==' ')i++;
                return ret;
            };
    
            
            auto getop = [&](){ 
                int ret=0;
                while(i<len && s[i]==' ')i++;
                if(i<len){ 
                    char c = s[i];
                    i++;
                    return c;
                }
                while(i<len && s[i]==' ')i++;
                return 'n';
            };
            
            auto getpri = [&](char c){ 
                if(c=='+' || c=='-'){ 
                    return 0;
                }
                return 1;
            };
                
            int a=0;
            int b=0;
    
            stack<int> stn;
            stack<char> stc;
            
            stn.push(getn());
            //debug(stn.top())
            while(i<len){ 
                
                char c = getop();
                while(!stc.empty() && getpri(c) <= getpri(stc.top())){ 
                    char op = stc.top();
                    stc.pop();
                    
                    
                    b = stn.top();
                    stn.pop();
                    a = stn.top();
                    
                    stn.pop();
                    
                    if(op == '+'){ 
                        a+=b;
                    }else if(op == '-'){ 
                        a-=b;
                    }else if(op=='*'){ 
                        a*=b;
                    }else{ 
                        a/=b;
                    }
                   // debug(a)
                    stn.push(a);
                }
                stc.push(c);
                stn.push(getn());
                //debug(stn.size())
                    //debug(stc.size())
                    
            }
            
            while(!stc.empty()){ 
                
                char c = stc.top();
                stc.pop();
                
                b = stn.top();
                stn.pop();
                a = stn.top();
                stn.pop();
               
                if(c == '+'){ 
                    a+=b;
                }else if(c == '-'){ 
                    a-=b;
                }else if(c=='*'){ 
                    a*=b;
                }else{ 
                    a/=b;
                }
                stn.push(a);
            }
            
            return stn.top();
        }
    };

**速度确实慢一些**  
![在这里插入图片描述][20210405210129758.png]

> 把表达式可以看成都是加（减法）法连接的，减法也是加法  
> 即都是a+b  
> 遇到乘除法的时候，先处理到b里面，然后再a+b就行了  
> 这里有特殊情况，就是只有一个数字的时候，为了配合a+b的形式，可以先给a赋值0  
> 这样就可以用0+b的情况来覆盖只有一个数字的情况了

#define debug(x) cout<<#x<<": "<<(x)<<endl;
    
    class Solution { 
    public:
        int calculate(string s) { 
            int i=0;
            int len = s.size();
            int a=0;
            int b=0;
    
            auto isop = [&](char c){ 
                if(c == '+' ||c == '-' ||c == '*' ||c == '/' ){ 
                    return true;
                }
                return false;
            };
    
            auto isn = [&](char c){ 
                if(c >=  '0' && c <='9' ){ 
                    return true;
                }
                return false;
            };
    
            auto getn = [&](){ 
                int ret=0;
                while(i<len && s[i]==' ')i++;
                while(i<len && isn(s[i])){ 
                    ret *= 10;
                    ret += s[i]-'0';
                    i++;
                }
                while(i<len && s[i]==' ')i++;
                return ret;
            };
    
            
            auto getop = [&](){ 
                int ret=0;
                while(i<len && s[i]==' ')i++;
                if(i<len){ 
                    char c = s[i];
                    i++;
                    return c;
                }
                while(i<len && s[i]==' ')i++;
                return 'n';
            };
    
            b = getn();
            
            while(i<len){ 
                // debug(i)
                char c = getop();
                int n = getn();
                if(c == '+'){ 
                    a+=b;
                    b = n;
                }else if(c == '-'){ 
                    a+=b;
                    b = -n;
                }else if(c=='*'){ 
                    b*=n;
                }else{ 
                    b/=n;
                }
                while(i<len && s[i]==' ')i++;
            }
            return a+b;
        }
    };

![在这里插入图片描述][20210405201928955.png]

[20210405210129758.png]: /images/20221022/66de0c9b1f8049f09b10dd0aa4a3291e.png
[20210405201928955.png]: /images/20221022/c0f78812f2e94b1091505b7e515012cf.png