代码随想录算法训练营第十一天| 20. 有效的括号 1047. 删除字符串中的所有相邻重复项 150. 逆波兰表达式求值

20. 有效的括号  

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

题目链接:20. 有效的括号 - 力扣（LeetCode）

思路：只是简单的模拟堆栈操作，我的做法并没有什么新意，评论区没有看到什么比较高效的写法，倒是有个用map容器解决的，看着还行。

class Solution {
public:
    bool isValid(string s) {
    stack<char> st;
    for(char &ch:s){
        if(ch=='('||ch=='{'||ch=='['){
            st.push(ch);
        }
        else{
            if(st.empty())
            return false;
            else if(ch-st.top()>2||ch-st.top()<0){
                return false;
            }
            else 
            st.pop();
        }
    }
    if(st.empty())
    return true;
    else
    return false;

    }
};

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

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

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

思路：代码也很简单，每次入队都检查是否与前一项相同，如果相同就出栈并继续循环。最后用两个栈相互倒腾一下改变字符串顺序。

class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> st;
        stack<char> st1;
        for(char &ch:s){
            if(st.empty()||ch!=st.top()){
                st.push(ch);
            }
            else{
                st.pop();
            }
        }
        while(!st.empty()){
            st1.push(st.top());
            st.pop();
        }
        string s1;
        while(!st1.empty()){
            s1+=st1.top();
            st1.pop();
        }
        return s1;
    }
};

竟然可以不用栈！

class Solution {
public:
    string removeDuplicates(string s) {
        string stk;
        for (char ch : s) {
            if (!stk.empty() && stk.back() == ch) {
                stk.pop_back();
            } else {
                stk.push_back(ch);
            }
        }
        return stk;
    }
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/solutions/643955/shan-chu-zi-fu-chuan-zhong-de-suo-you-xi-4ohr/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

150. 逆波兰表达式求值

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

• 有效的算符为 '+'、'-'、'*' 和 '/' 。
• 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
• 两个整数之间的除法总是 向零截断 。
• 表达式中不含除零运算。
• 输入是一个根据逆波兰表示法表示的算术表达式。
• 答案及所有中间计算结果可以用 32 位 整数表示。

题目链接：150. 逆波兰表达式求值 - 力扣（LeetCode）

思路：主要卡在了不知道怎么把string转换成操作符，原来只是一个if判断。

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for (int i = 0; i < tokens.size(); i++) {
            if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
                int num1 = st.top();
                st.pop();
                int 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(stoi(tokens[i]));
            }
        }
        int result = st.top();
        st.pop(); // 把栈里最后一个元素弹出（其实不弹出也没事）
        return result;
    }
};

作者：代码随想录
链接：https://leetcode.cn/problems/evaluate-reverse-polish-notation/solutions/1752027/by-carlsun-2-a0vh/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。