算法训练day11 栈与队列 02 LeetCode20.1047.150

20.有效的括号：

题目：

20. 有效的括号 - 力扣（LeetCode）

题解：

代码随想录 (programmercarl.com)

class Solution
{
public:
    bool isValid(string s)
    {
        stack<char> str;
        if (s.size() % 2 == 1)
            return false;
        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] == '(' || s[i] == '[' || s[i] == '{')
            {
                str.push(s[i]);
            }
            else if (s[i] == ')' || s[i] == ']' || s[i] == '}')
            {
                if (str.empty())
                {
                    return false;
                }
                if (s[i] == ')' && str.top() == '(')
                    str.pop();
                else if (s[i] == ']' && str.top() == '[')
                    str.pop();
                else if (s[i] == '}' && str.top() == '{')
                    str.pop();
                else
                    return false;
            }
        }
        return str.empty();
    }
};

字符串长度是否奇数遇左括号进栈，遇右括号则判断栈顶是否为对应的左括号，不适则返回false，循环结束判断栈是否为空
卡哥解法：

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

补充了栈中没有匹配的括号的情况。

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

题目：

1047. 删除字符串中的所有相邻重复项 - 力扣（LeetCode）

题解：

代码随想录 (programmercarl.com)

class Solution
{
public:
    string removeDuplicates(string s)
    {
        stack<char> st;
        for (char S : s)
        {
            if (st.empty() || st.top() != S)
            {
                st.push(S);
            }
            else
                st.pop();
        }
        string result = "";
        while (!st.empty())
        {
            result += st.top();
            st.pop();
        }
        reverse(result.begin(), result.end());
        return result;
    }
};

150.逆波兰表达式求值

题目：

150. 逆波兰表达式求值 - 力扣（LeetCode）

题解：

代码随想录 (programmercarl.com)

class Solution
{
public:
    int evalRPN(vector<string> &tokens)
    {
        stack<long long> st;
        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;
    }
};