day11 - 栈与队列part02

zqh2023 / 2023-08-21 / 原文

20. 有效的括号

详解

class Solution {
public:
    bool isValid(string s) {
        //最里面一对是相邻闭合
        stack<char> stack_1;
        for(int i=0; i< s.length(); i++){
            if(s[i] == '(' || s[i] == '{' || s[i] == '['){
                stack_1.push(s[i]);
            }else{
                if(stack_1.empty())
                    return false;
                char tmp = stack_1.top();
                if( (s[i] == ')' && tmp == '(') || (s[i] == '}' && tmp == '{') || (s[i] == ']' && tmp == '[') ){
                    stack_1.pop();
                }else{
                    return false;
                }
            }
        }
        return empty(stack_1);
    }
};

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

class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> stack_1;
        for(int i=0; i<s.length(); i++){
            if(!empty(stack_1) && stack_1.top() == s[i]){
                stack_1.pop();
            }else{
                stack_1.push(s[i]);
            }
        }
        s.resize(stack_1.size());
        int i = stack_1.size() - 1;
        while(!stack_1.empty()){
            s[i--] = stack_1.top();
            stack_1.pop();
        }
        return s;
    }
};

150. 逆波兰表达式求值

//stoi 使用
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> stack_1;
        map<string, char> map_1;
        int result = 0;
        map_1["+"] = '+';
        map_1["-"] = '-';
        map_1["*"] = '*';
        map_1["/"] = '/';
        for(int i = 0; i < tokens.size(); i++){
            if(map_1[tokens[i]]){
                int num_2 = stack_1.top();
                stack_1.pop();
                int num_1 = stack_1.top();
                stack_1.pop();
                if(tokens[i] == "+") result = num_1 + num_2;
                else if(tokens[i] == "-") result = num_1 - num_2;
                else if(tokens[i] == "*") result = num_1 * num_2;
                else if(tokens[i] == "/") result = num_1 / num_2;
                cout << "push_result:" <<tokens[i]<<","<<num_2<<"="<< result << endl;
                stack_1.push(result);
            }else{
                cout << "push:" << stoi(tokens[i]) << endl;
                stack_1.push(stoi(tokens[i]));
            }
        }
        return stack_1.top();
    }
};