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

20.有效的括号

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

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

有效字符串需满足：

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

文章讲解/视频讲解：https://programmercarl.com/0020.%E6%9C%89%E6%95%88%E7%9A%84%E6%8B%AC%E5%8F%B7.html

思路

设置一个stack，然后循环遍历字符串S，当遍历到左括号时，如’(', ‘[’, ‘{’, 将字符串push进stack中

当遍历到右括号时，判断stack栈顶的元素是否为该右括号对应的括号，如果是对应的，则将stack的栈顶pop出，

如果不是对应的，则说明字符串无效，返回false。

遍历完字符串之后，判断stack是否为空，如果不为空，说明还是无效，返回false，否则返回为true。

C++实现

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

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

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

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

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

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

文章讲解/视频讲解：https://programmercarl.com/1047.%E5%88%A0%E9%99%A4%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B8%AD%E7%9A%84%E6%89%80%E6%9C%89%E7%9B%B8%E9%82%BB%E9%87%8D%E5%A4%8D%E9%A1%B9.html

思路

设置一个stack，这个stack可以由一个string实现。

然后循环遍历字符串s，如果当前遍历的字符和stack的栈顶相等，则将stack的栈顶pop出，并跳过这个字符。

如果当前遍历的字符和stack的栈顶不相等或者栈为空，则将字符push进这个栈。

由于我们的栈直接由string实现的，因此可以直接返回这个stack。

C++实现

class Solution {
public:
    string removeDuplicates(string s) {
        string out_s;
        for(int i = 0;i<s.size();i++){
            if(out_s.empty()) out_s.push_back(s[i]);
            else{
                char tmp = out_s.back();
                if(s[i] == tmp) out_s.pop_back();
                else out_s.push_back(s[i]);
            }
        }
        return out_s;
    }
};

150. 逆波兰表达式求值

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

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

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

注意：

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

文章讲解/视频讲解：https://programmercarl.com/0150.%E9%80%86%E6%B3%A2%E5%85%B0%E8%A1%A8%E8%BE%BE%E5%BC%8F%E6%B1%82%E5%80%BC.html

思路

构建一个stack，用来存储数字。

遍历tokens数组，当遇到数字时，将其存入stack，当遇到计算符号时，从stack中取出两个数字分别为num2, num1

将num1与num2做运算，再存入stack中。

最终stack中剩余的一个数字，就是逆波兰表达式的结果。

C++实现

class Solution {
public:
    int calculate(int num1, int num2, string op){
        if(op == "+"){
            return num1 + num2;
        }
        else if(op == "-"){
            return num1 - num2;
        }
        else if(op == "*"){
            return num1 * num2;
        }
        else if(op == "/"){
            return num1 / num2;
        }
        else{
            return num1 + num2;
        }
    }

    int evalRPN(vector<string>& tokens) {
        stack<int> nums;
        for(int i = 0;i<tokens.size();i++){
            if(tokens[i] != "+" && tokens[i] != "-" && tokens[i] != "*" && tokens[i] != "/"){
                nums.push(stoi(tokens[i]));
            }
            else{
                int num2 = nums.top();
                nums.pop();
                int num1 = nums.top();
                nums.pop();
                int res = calculate(num1, num2, tokens[i]);
                nums.push(res);
            }
        }
        return nums.top();
    }
};