【算法训练营day11】LeetCode20. 有效的括号 LeetCode1047. 删除字符串中的所有相邻重复项 LeetCode150. 逆波兰表达式求值

LeetCode20. 有效的括号

题目链接：20. 有效的括号

初次尝试

遍历字符串，遇见左括号进栈，遇见右括号且栈不为空出栈，出栈后判断是不是一对括号，感觉写的有点复杂了，还可以优化。

class Solution {
public:
    bool isValid(string s) {
        stack<int> st;
        int temp;

        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') st.push(1);
            else if (s[i] == '[') st.push(2);
            else if (s[i] == '{') st.push(3);
            else if (s[i] == ')' && !st.empty()) {
                temp = st.top();
                if (temp != 1) return false;
                st.pop();
            }
            else if (s[i] == ']' && !st.empty()) {
                temp = st.top();
                if (temp != 2) return false;
                st.pop();
            }
            else if (s[i] == '}' && !st.empty()) {
                temp = st.top();
                if (temp != 3) return false;
                st.pop();
            }
            else return false;
        }

        if (st.empty()) return true;
        else return false;
    }
};

看完代码随想录后的想法

可以在遇见左括号时，直接入栈右括号，这样后面也不需要讨论右括号的种类，只需要判断s[i]和st.top()的元素是否相等就可以了，省去了很多代码。

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;

        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') st.push(')');
            else if (s[i] == '[') st.push(']');
            else if (s[i] == '{') st.push('}');
            else if (!st.empty() && s[i] == st.top()) st.pop();
            else return false;
        }

        return st.empty();
    }
};

LeetCode1047. 删除字符串中的所有相邻重复项

题目链接：1047. 删除字符串中的所有相邻重复项

初次尝试

有点类似消消乐的思路，遍历字符串，判断指向的字符是否等于栈顶字符，如果相等就出栈，不相等就把指向的字符入栈，最后从栈中输出剩下的字符串。

class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> st;

        for (int i = 0; i < s.size(); i++) {
            if (!st.empty() && s[i] == st.top()) {
                st.pop();
            }
            else {
                st.push(s[i]);
            }
        }

        string ans = "";
        while (!st.empty()) {
            ans += st.top();
            st.pop();
        }
        reverse(ans.begin(), ans.end());

        return ans;
    }
};

看完代码随想录后的想法

一样的思路。

LeetCode150. 逆波兰表达式求值

题目链接：150. 逆波兰表达式求值

初次尝试

题目中这句话已经指明了这道题的思路，按照这个思路写代码就行。

适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<long int> st;

        for (int i = 0; i < tokens.size(); i ++) {
            if (tokens[i] == "+") {
                long int a = st.top();
                st.pop();
                long int b = st.top();
                st.pop();
                st.push(b + a);
            }
            else if (tokens[i] == "-") {
                long int a = st.top();
                st.pop();
                long int b = st.top();
                st.pop();
                st.push(b - a);                
            }
            else if (tokens[i] == "*") {
                long int a = st.top();
                st.pop();
                long int b = st.top();
                st.pop();
                st.push(b * a);                  
            }
            else if (tokens[i] == "/") {
                long int a = st.top();
                st.pop();
                long int b = st.top();
                st.pop();
                st.push(b / a);    
            }
            else {
                st.push(stoi(tokens[i]));
            }
        }

        return st.top();
    }
};

看完代码随想录后的想法

思路一样，代码还有可以优化的地方：

1. long long比long int更好，而且后面stoi()这个函数也应该相应修改为stoll()。
2. 多个if有重复的部分可以合并一下，减少代码量。

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
<<<<<<< HEAD
        stack<long long> st;
=======
        // 力扣修改了后台测试数据，需要用longlong
        stack<long long> st; 
>>>>>>> 28f3b52a82e3cc650290fb02030a53900e122f43
        for (int i = 0; i < tokens.size(); i++) {
            if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
                long long num1 = st.top();
                st.pop();
                long long num2 = st.top();
                st.pop();
                if (tokens[i] == "+") st.push(num2 + num1);
                if (tokens[i] == "-") st.push(num2 - num1);
                if (tokens[i] == "*") st.push(num2 * num1);
                if (tokens[i] == "/") st.push(num2 / num1);
            } else {
                st.push(stoll(tokens[i]));
            }
        }

        int result = st.top();
        st.pop(); // 把栈里最后一个元素弹出（其实不弹出也没事）
        return result;
    }
};

原文地址：http://www.cnblogs.com/BarcelonaTong/p/16815901.html