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

发布时间:2024年01月20日

栈 以下题目主要是利用栈先进先出的特性
注意事项:
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();
    }
};
文章来源:https://blog.csdn.net/heitong_fu/article/details/135720534
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。