Sword finger offer special assault edition day 12

The finger of the sword Offer II 036. Postfix expression
The title directly gives the suffix expression , Just count it directly . If you give infixes, you need to convert suffixes to calculate （ The result can be obtained directly through calculation in the process of conversion , If you don't calculate directly in the process of transferring suffixes, you can directly push the symbols onto the stack , Then the final sequence string from the bottom of the stack to the top of the stack is the suffix expression ）

class Solution {
    
public:
    void cmp(stack<int> &nums, string op) {
    
        int a = nums.top(); nums.pop();
        int b = nums.top(); nums.pop();
        if(op == "+") nums.push(b+a);
        else if(op == "-") nums.push(b-a);
        else if(op == "*") nums.push(b*a);
        else nums.push(b/a);
    }
    int evalRPN(vector<string>& tokens) {
    
        stack<int> nums;
        for(string str: tokens) {
    
            if(str == "+" || str == "-" || str == "*" || str == "/") {
    
                cmp(nums,str);
            } else nums.push(stoi(str));
        }
        return nums.top();
    }
};

---

The finger of the sword Offer II 037. Asteroid collision

Stack simulation , Only the left side is positive , Only when the right side is negative can there be a collision .

class Solution {
    
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
    
        vector<int> stk;
        for(auto num: asteroids) {
    
            bool flag = true;
            while(flag && num < 0 && !stk.empty() && stk.back() > 0) {
    
                if(stk.back() > -num) flag = false;
                else if(stk.back() == -num) {
     // Both disappear at the same time 
                    stk.pop_back();
                    flag = false;
                } else stk.pop_back();
            }
            if(flag) stk.push_back(num);
        }
        return stk;
    }
};

---

The finger of the sword Offer II 038. Daily temperature

Monotone stack optimization

class Solution {
    
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
    
        int n = temperatures.size();
        vector<int> res(n);
        stack<int> sk;
        for(int i = 0; i < n; i++) {
    
            while(sk.size() && temperatures[sk.top()] < temperatures[i]) {
    
                res[sk.top()] = i-sk.top();
                sk.pop();
            }
            sk.push(i);
        }
        return res;
    }
};