20. 有效的括号

题目：

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

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

输入：s = "()"
输出：true

解题思路：

不匹配会有三种情况：

1. 字符串里左方向的括号多余了，所以不匹配。
   已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false

2. 括号没有多余，但是括号的类型没有匹配上。
   遍历字符串匹配的过程中，发现栈里没有要匹配的字符。所以return false

3. 字符串里右方向的括号多余了，所以不匹配。
   遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号return false
   注意 2、3 在 JavaScript 里面可以统一成一步。

var isValid = function (s) {
    const stack = [];
    for (let i = 0; i < s.length; i++) {
        let c = s[i];
        switch (c) {
            case '(':
                stack.push(')');
                break;
            case '[':
                stack.push(']');
                break;
            case '{':
                stack.push('}');
                break;
            default:
                if (c !== stack.pop()) {
                    return false;
                }
        }
    }
    return stack.length === 0;
};

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

题目：

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例：

输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

解题思路：

用栈遇到相同元素就消去。

var removeDuplicates = function (s) {
    const result = [];
    for (const i of s) {
        if (i === result[result.length - 1]) {
            result.pop();
        } else {
            result.push(i);
        }
    }
    return result.join("");
};

150. 逆波兰表达式求值

题目：

给你一个字符串数组 tokens ，表示一个根据逆波兰表示法表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意：

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

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

解题思路：

后缀表达式求和用栈来解决就好了，遇到数字则入栈；遇到运算符则取出栈顶两个数字进行计算，并将结果压入栈中。

var evalRPN = function (tokens) {
    const helperStack = [];
    const operatorMap = new Map([
        ['+', (a, b) => a + b],
        ['-', (a, b) => a - b],
        ['/', (a, b) => Math.trunc(a / b)],
        ['*', (a, b) => a * b],
    ]);
    for (let t of tokens) {
        if (operatorMap.has(t)) {
            let b = helperStack.pop();
            let a = helperStack.pop();
            helperStack.push(operatorMap.get(t)(a, b));
        } else {
            helperStack.push(Number(t));
        }
    }
    return helperStack.pop();
};