算法随想Day10【栈与队列】| LC20-有效的括号、LC1047-删除字符串中的所有相邻重复项、LC150-逆波兰表达式求值

LC20. 有效的括号

做法和思路比较简单直接，没考虑代码的优化和简洁性

bool isValid(string s)
{
    int i;
    int size = s.size();
    stack<char> sta;
    for (i = 0; i < size; i++)
    {
        int ch = 0;
        if (sta.size() != 0)
        {
            ch = sta.top();
        }
        switch(s[i])
        {
            case '(':
                sta.push(s[i]);
                break;
            case '[':
                sta.push(s[i]);
                break;
            case '{':
                sta.push(s[i]);
                break;
            case ')':
                if (ch == '(')
                {
                    sta.pop();
                }
                else
                {
                    return false;
                }
                break;
            case ']':
                if (ch == '[')
                {
                    sta.pop();
                }
                else
                {
                    return false;
                }
                break;
            case '}':
                if (ch == '{')
                {
                    sta.pop();
                }
                else
                {
                    return false;
                }
                break;
        }
    }
    if (sta.size() == 0)
    {
        return true;
    }
    return false;      
}

官方解法，用map容器把左括号和右括号对应起来，遍历遇到右括号时不用再写冗长的代码

bool isValid(string s) {
    int n = s.size();
    if (n % 2 == 1) {
        return false;
    }

    unordered_map<char, char> pairs = {
        {')', '('},
        {']', '['},
        {'}', '{'}
    };
    stack<char> stk;
    for (char ch: s) {
        if (pairs.count(ch)) {
            if (stk.empty() || stk.top() != pairs[ch]) {
                return false;
            }
            stk.pop();
        }
        else {
            stk.push(ch);
        }
    }
    return stk.empty();
}

Carl哥的写法更加的巧妙。写代码前可以先考虑有哪些不匹配的情况，再下笔，避免编码时的各种小问题：

• 第一种情况，字符串里左方向的括号多余了 ，所以不匹配。
  • 遍历完了字符串，但是栈不为空，return false
• 第二种情况，括号没有多余，但是 括号的类型没有匹配上。
  • 遍历字符串匹配的过程中，发现栈里没有要匹配的字符，return false
• 第三种情况，字符串里右方向的括号多余了，所以不匹配。
  • 遍历字符串匹配的过程中，遇到右括号，而栈已经为空了，没有匹配的字符了吗，

bool isValid(string s) {
    if (s.size() % 2 != 0) return false; // 如果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(']');
        // 第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号 return false
        // 第二种情况：遍历字符串匹配的过程中，发现栈里没有我们要匹配的字符。所以return false
        else if (st.empty() || st.top() != s[i]) return false;
        else st.pop(); // st.top() 与 s[i]相等，栈弹出元素
    }
    // 第一种情况：此时我们已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false，否则就return true
    return st.empty();
}

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

string removeDuplicates(string s)
{
    stack<char> sta;
    for (char ch : s)
    {
        if (sta.size() > 0 && sta.top() == ch)
        {
            sta.pop();
        }
        else
        {
            sta.push(ch);
        }
    }
    string str(sta.size(), 0);
    for (int i = str.size() - 1; i >= 0; i--)
    {
        str[i] = sta.top();
        sta.pop();
    }
    return str;
}

LC150. 逆波兰表达式求值

了解逆波兰表达式RPN的数学原理，用栈实现。

RPN本身的生成过程和据此求值的过程都很值得推敲。

但在编码过程中还是碰到了各式各样的小问题：

• vector存储的是string类型，遍历vector，判断if (str[str.size() - 1] >= '0' && str[str.size() - 1] <= '9')，而不能判断str[0]，因为首个元素有可能是'-'。所以同时传入函数string2num()中要对可能的负号进行处理

• string装的元素是char类型，若要转为int型，需要减上一个'0'的ASCII值（48）

• 在遍历过程中，若遇到一个运算操作符，先pop出一个元素作为二元运算的右边值，用result暂存，然后在pop一个作为左边值，最后求解得结果要重新push进栈，保证在循环中统一性。

int string2num(string s)
{
    int i = 0;
    int result = 0, negative = 0;
    if (s[0] == '-')
    {
        negative = 1;
        i = 1;
    }
    for (; i < s.size(); i++)
    {
        result = 10 * result + (s[i] - 48);
    }
    result = negative ? -result : result;
    return result;
}

int evalRPN(vector<string>& tokens)
{
    int first_opera = 1;
    int result = 0;
    int temp = 0;
    stack<int> nums;
    //stack<char> opera;
    for (auto str : tokens)
    {
        if (str[str.size() - 1] >= '0' && str[str.size() - 1] <= '9')
        {
            nums.push(string2num(str));
        }
        else
        {
            result = nums.top();
            nums.pop();
            switch(str[0])
            {
                case '+':
                    result += nums.top();
                    break;
                case '-':
                    result = nums.top() - result;
                    break;
                case '*':
                    result *= nums.top();
                    break;
                case '/':
                    result = nums.top() / result;
                    break;
                default:
                    break;
            }
            nums.pop();
            nums.push(result);
        }
    }
    return nums.top();
}