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

20. 有效的括号

代码随想录链接

题目

LeetCode-20

给定一个只包含了()6种字符的字符串，判断该字符串中的括号是否满足左右匹配。

自己的想法

遇到左侧符号[({就进栈，遇到右侧符号])}就判断栈顶是否为对应的左侧符号，若是则将左侧符号弹出，若不匹配，则不满足条件。若遍历完成后，栈中仍有元素，则也不满足条件。

题解

class Solution {
private:
    stack<char> cs;
public:
    bool isPair(char a, char b) {               // 判断a是否为b的对应左侧符号
        if (a == '(' && b == ')') return true;
        if (a == '[' && b == ']') return true;
        if (a == '{' && b == '}') return true;
        return false;
    }

    bool isValid(string s) {
        for (char c : s) {                                      // 遍历字符串中的字符
            if (c == '(' || c == '{' || c == '[')  cs.push(c);  // 若为左侧字符，则入栈
            else {                                              // 若为右侧字符
                if (cs.empty()) return false;                   // 栈中没有内容，不匹配
                char topChar = cs.top();                        // 判断栈顶符号是否和当前的右侧符号匹配
                if (isPair(topChar, c)) cs.pop();
                else return false;
            }
        }
        if (!cs.empty()) return false;                          // 遍历完成后，栈若不为空，则仍不满足条件
        return true;
    }
};

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

代码随想录链接

题目

LeetCode-1047

去除字符串中所有的相同相邻字符。

自己的想法

遍历给定的字符串，设遍历获得的字符为c，若c和新的结果字符串末尾的字符相同，则将结果字符串的末尾字符取出；若不同，则将c拼接在新的字符串的结尾。实际上将字符串当做了一个栈。

题解

class Solution {
public:
    string removeDuplicates(string s) {
        string result;                                  // 初始化一个结果字符串
        for (char c : s) {                              // 遍历给定的字符串
            if (result.empty() || result.back() != c) { // 若字符串为空或者字符串末尾字符不等于当前遍历到的字符
                result.push_back(c);                    // 将该字符加入结果字符串
            } else {
                result.pop_back();                      // 否则就将结果字符串的末尾字符去除
            }
        }
        return result;
    }
};

150. 逆波兰表达式求值

代码随想录链接

题目

LeetCode-150

根据逆波兰表达式，求该表达式的值。

自己的想法

Yet Anther Problem Appeared in WANGDAO.

设两个栈，一个用于存储运算数，一个用于暂存运算符。遍历表达式，遇到运算数就将数据压栈，遇到运算符时，先查看运算符的栈栈顶的运算符，若当前运算符的顺序高于栈顶运算符时，则将运算符入栈，否则取运算数栈顶两个数字，使用当前运算符进行运算，并将结果压入运算数栈中。遍历完成后若运算符栈仍有运算符，继续取出做运算。最后返回运算数栈的栈顶数字即可。

题解

class Solution {
public:
    bool hasPriority(char a, char b) {                                              // 对比运算符优先级
        if ((a == '*' || a == '/') && (b == '+' || b == '-'))   return true;
        return false;
    }

    int evalRPN(vector<string>& tokens) {
        stack<int> nums;
        stack<char> ops;
        for (string s : tokens) {
            if (s != "+" && s != "-" && s != "*" && s != "/") nums.push(stoi(s));   // 将遇到的每个运算数入栈
            else {
                char c = s[0];
                if (ops.empty() || !hasPriority(s[0], ops.top())) {                 // 满足进行运算的条件
                    int a = nums.top();
                    nums.pop();
                    int b = nums.top();
                    nums.pop();
                    int num = 0;
                    if (c == '+') num = a + b;
                    else if (c == '-') num = b - a;
                    else if (c == '*') num = a * b;
                    else if (c == '/') num = b / a;
                    nums.push(num);
                } else {
                    ops.push(c);
                }
            }
        }
        return nums.top();
    }
};