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

栈 以下题目主要是利用栈先进先出的特性
注意事项：
1、要确定栈非空才能访问栈顶元素，否则越界

20. 有效的括号

思路：
用栈来保存符号。遍历数组，遇到左括号（“(“、”{“、”[”）直接入栈，遇到右括号则判断是否与栈顶元素对应。对应则弹出栈顶元素，否则判定括号无效。
特殊情况：
1、遍历过程中栈为空时遇到右括号，则说明该右括号一定无对应的左括号，判定括号无效
2、遍历完成后栈是否为空，若不为空，说明存在左括号无对应的右括号，判定括号无效

代码实现

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

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

思路：
用栈来保存符号。遍历字符串，判断是否与栈顶元素相同，相同则弹出栈顶元素，否则入栈。
特殊情况：
1、遍历过程中栈为空时直接将当前元素入栈

class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> cSt;
        for(char c : s){
            if(cSt.empty()){
                cSt.push(c);
                continue;
            }
            
            if(c == cSt.top()){
                cSt.pop();
            }
            else{
                cSt.push(c);
            }
        }

        string newS = "";
        while(!cSt.empty())
        {
            newS = cSt.top() + newS;
            cSt.pop();
        }
        return newS;
    }
};

150. 逆波兰表达式求值

思路：
用栈来保存符号。遍历数组，遇到数字直接入栈，而遇到运算符则连续弹出栈顶元素num2、num1，进行计算（num1 运算符 num2），将计算结果入栈。
最后栈中只有一个元素，即表达式求得的值。
注意事项：
计算时要注意两数字的前后关系（num1 运算符 num2）

双指针法代码实现

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> sSt;
        int num1, num2;
        int temp;
        for(string s : tokens){
            if(s == "+" || s == "-" || s == "*" || s == "/"){
                num2 = sSt.top();  sSt.pop();
                num1 = sSt.top();  sSt.pop();
                if(s == "+"){
                    temp = num1 + num2;
                }
                else if(s == "-"){
                    temp = num1 - num2;
                }
                else if(s == "*"){
                    temp = num1 * num2;
                }
                else{
                    temp = num1 / num2;
                }
                sSt.push(temp);
            }
            else{
                sSt.push(stoi(s));
            }
        }
        return sSt.top();
    }
};