Algorithms & Data Structures : Stack Problems

Problem

LeetCode : 1249. Minimum Remove to Make Valid Parentheses
[string][stack]

LeetCode : 726. Number of Atoms
[string][stack]

LeetCode : 439. Ternary Expression Parser
[stack][string]

LeetCode : 1944. Number of Visible People in a Queue
[monotonic stack][hard]

LeetCode : 1249. Minimum Remove to Make Valid Parentheses

使用 stack 來驗證 ‘(’, ‘)’ 是否正確，在不正確的位置上標記記號，最後再將正確的字串拼湊出來。

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        string ans;
        vector<int> index_stack;
        vector<bool> m = vector<bool>(s.size(), false);
        
        for(int i = 0;i < s.size();i++) {
            if(s[i] == '(') {
                index_stack.push_back(i);
            } else if(s[i] == ')') {
                if(index_stack.size() > 0) {
                    index_stack.pop_back();
                } else {
                    m[i] = true;
                }
            }
        }
        
        for(int i = 0;i < index_stack.size();i++) {
            m[index_stack[i]] = true;
        }
        
        for(int i = 0;i < s.size();i++) {
            if(!m[i]) {
                ans += s[i];
            }
        }
        
        return ans;
    }
};

LeetCode : 726. Number of Atoms

使用 stack 去記錄，每當遇到 ‘)’ 時，先偷看後面一個 index 是否為數字。
處理完後，不停 pop 直到遇到 '(' ， 並把剛剛 pop 出來的節點，通通乘上剛剛處理好的數字後再倒回原本的 stack 內。

typedef struct Node Node;
struct Node {
    string atom;
    int num;
};
class Solution {
public:
    string countOfAtoms(string formula) {
        string res;
        
        int stat = 0;
        string tmp;
        vector<Node> ns;
        for(int i = 0;i < formula.size();i++) {
            if(formula[i] >= 'A' && formula[i] <= 'Z') {
                if(0 != tmp.size()) {
                    ns.push_back({tmp, 1});
                    tmp.clear();
                }
                tmp += formula[i];    
            } else if(formula[i] >= 'a' && formula[i] <= 'z') {
                tmp += formula[i];
            } else if(formula[i] == '(') {
                if(0 != tmp.size()) {
                    ns.push_back({tmp, 1});
                    tmp.clear();
                }
                ns.push_back({"(", 0});
            } else if(formula[i] == ')') {
                if(0 != tmp.size()) {
                    ns.push_back({tmp, 1});
                    tmp.clear();
                }
                
                int localNum = 1;
                vector<Node> tmpNodes;
                if(i + 1 < formula.size()) {
                    if(formula[i + 1] >= '0' && formula[i + 1] <= '9') {
                        string sn;
                        i++;
                        while(formula[i] >= '0' && formula[i] <= '9' && i < formula.size()) {
                            sn += formula[i];
                            i++;
                        }
                        i--;
                        localNum = atoi(sn.c_str());
                    }
                }
                while("(" != ns.back().atom) {
                    tmpNodes.push_back(ns.back());
                    ns.pop_back();
                }
                ns.pop_back();
                while(0 != tmpNodes.size()) {
                    ns.push_back({tmpNodes.back().atom, tmpNodes.back().num * localNum});
                    tmpNodes.pop_back();
                }
            } else if(formula[i] >= '0' && formula[i] <= '9') {
                int localNum = 1;
                string sn;
                while(formula[i] >= '0' && formula[i] <= '9' && i < formula.size()) {
                    sn += formula[i];
                    i++;
                }
                i--;
                
                localNum = atoi(sn.c_str());
                
                ns.push_back({tmp, localNum});
                tmp.clear();
            }
        }
        
        if(0 != tmp.size()) {
            ns.push_back({tmp, 1});
        }
        
        map<string, int> m;
        for(int i = 0;i < ns.size();i++) {
            m[ns[i].atom] += ns[i].num;
        }
        
        for(auto it : m) {
            res += it.first;
            if(1 != it.second) {
                res += to_string(it.second);
            }
        }
        
        return res;
    }
};

LeetCode : 439. Ternary Expression Parser

class Solution {
public:
    string parseTernary(string expression) {
        string res;
        string st;
        
        for(int i = expression.size() - 1;i >= 0;i--) {
            if(':' != expression[i]) {
                st.push_back(expression[i]);
            }
            
            if(st.size() >= 4 && '?' == st[st.size() - 2]) {
                char a = st.back();
                char b = st[st.size() - 3];
                char c = st[st.size() - 4];
                st.pop_back();
                st.pop_back();
                st.pop_back();
                st.pop_back();
                
                if('F' == a) {
                    st.push_back(c);
                } else {
                    st.push_back(b);
                }
            }
        }
        
        res.push_back(st.back());
        
        return res;
    }
};

LeetCode : 1944. Number of Visible People in a Queue

// TODO : 效能太差了
/*
  monotonic stack 

  這次的解題也是先想出明顯會 TLE 的暴力解
  再基於暴力解的想法，想出 monotonic stack 的解法
 */
class Solution {
public:
    vector<int> canSeePersonsCount(vector<int>& heights) {
        vector<int> rec = vector<int>(heights.size(), 0);
        vector<vector<int>> moto;
        for(int i = 0;i < heights.size();i++) {
            if(!moto.empty()) {
                while(!moto.empty() && 
                      moto.back()[0] < heights[i]) {
                    rec[moto.back()[1]]++;
                    moto.pop_back();
                }
            }
            if (moto.size() > 0) {
                rec[moto.back()[1]]++;
            }
            moto.push_back({heights[i], i});
        }
        return rec;
    }
};