算法训练营第十一天 | LeetCode 20 有效的括号、LeetCode 1047 删除字符串中的所有相邻重复项

LeetCode 20 有效的括号

这题其实有点麻烦，在我看来是这样子，因为某些情况下比较难分类，最后踩了两个坑，才过的。一个是最后循环结束后要判断栈内存是否为空，一个是出栈时要判断栈是否为空，总的来说是考验对于栈内存空间的掌控吧。代码如下：

class Solution {
private:
    stack<int> mystack;
public:
    bool isValid(string s) {
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '(' || s[i] == '[' || s[i] == '{') mystack.push(s[i]);
            else {
                if (s[i] == ')' && !mystack.empty() && mystack.top() == '(') mystack.pop();
                else if (s[i] == ']' && !mystack.empty() && mystack.top() == '[') mystack.pop();
                else if (s[i] == '}' && !mystack.empty() && mystack.top() == '{') mystack.pop();
                else return false; 
            }
        }
        return mystack.empty();
    }
};

LeetCode 1047 删除字符串中的所有相邻重复项

这一题考栈的性质，相邻字符用未进栈的元素和进栈的元素进行模拟即可，相同且栈不为空即出栈，否则进栈，之后将栈内元素全部导入一个字符串，还要注意要写一个反转函数翻转下即可。

代码如下：

class Solution {
    stack<int> mystack;
    void swap(string& s, int l, int r) {
        while (l < r) {
            char c = s[l];
            s[l] = s[r];
            s[r] = c;
            l++; r--;
        }
    }
public:
    string removeDuplicates(string s) {
        string res = "";
        for (int i = 0; i < s.size(); i++) {
            if (!mystack.empty()) {
                if (s[i] == mystack.top()) mystack.pop();
                else mystack.push(s[i]);
            } else mystack.push(s[i]);
        }
        while (!mystack.empty()) {
            res += mystack.top();
            mystack.pop();
        }
        swap(res, 0, res.size() - 1);
        return res;
    }
};

LeetCode 150 逆波兰表达式求值

这题其实也不难，只是细节要多一些。注意用的是字符串数组作为输入，而我们要用int型进行计算，这时候就要用到一个string转int类型的库函数stoi函数，aoti是字符数组转int类型。其他一样判断不是符号就入栈，否则取出元素进行计算。

代码如下：

class Solution {
private:
    stack<int> mystack;
public:
    int evalRPN(vector<string>& tokens) {
        for (int i = 0; i < tokens.size(); i++) {
            if (tokens[i] != "+" && tokens[i] != "-" && tokens[i] != "*" && tokens[i] != "/") {
                mystack.push(stoi(tokens[i]));
            } else if (tokens[i] == "+") {
                int a = mystack.top();
                mystack.pop();
                int b = mystack.top();
                mystack.pop();
                mystack.push(a+b);
            } else if (tokens[i] == "-") {
                int a = mystack.top();
                mystack.pop();
                int b = mystack.top();
                mystack.pop();
                mystack.push(b-a);
            } else if (tokens[i] == "*") {
                int a = mystack.top();
                mystack.pop();
                int b = mystack.top();
                mystack.pop();
                mystack.push(a*b);
            } else if (tokens[i] == "/") {
                int a = mystack.top();
                mystack.pop();
                int b = mystack.top();
                mystack.pop();
                mystack.push(b/a);
            }
        }
        return mystack.top();
    }
};

简化后如下：

class Solution {
private:
    stack<int> mystack;
    string opera[4] = {"+","-","*","/"};
public:
    int evalRPN(vector<string>& tokens) {
        for (int i = 0; i < tokens.size(); i++) {
            if (tokens[i] != opera[0] && tokens[i] != opera[1] && tokens[i] != opera[2] && tokens[i] != opera[3]) {
                mystack.push(stoi(tokens[i]));
            } else {
                int a = mystack.top();
                mystack.pop();
                int b = mystack.top();
                mystack.pop();
                if (tokens[i] == opera[0])
                    mystack.push(a+b);
                if (tokens[i] == opera[1])
                    mystack.push(b-a);
                if (tokens[i] == opera[2])
                    mystack.push(a*b);
                if (tokens[i] == opera[3])
                    mystack.push(b/a);
            }
        }
        return mystack.top();
    }
};