栈数据结构详解与算法应用实例

栈最大的特点是先进后出。利用这个特点应用于我们的日常生活会有很大的便利。下面我们一起来看看吧。

1. 表达式求值

class Solution {
public:
    int calculate(string s) {
        //用数组来模拟栈
        vector<int> st;
        int i=0,n=s.size();
        char op='+';
        while(i<n){
            if(s[i]==' ') i++;
            else if(s[i]>='0'&&s[i]<='9'){
                int tmp=0;
                while(i<n&&s[i]>='0'&&s[i]<='9')
                tmp=tmp*10+(s[i++]-'0');
                if(op=='+') st.push_back(tmp);
                else if(op=='-') st.push_back(-tmp);
                else if(op=='*') st.back()*=tmp;
                else st.back()/=tmp;
            }else{
                op=s[i];
                i++;
            }
        }
        int sum=0;
        for(auto e: st){
            sum+=e;
        }
         sum;
    }
};