day11 栈与队列

20.有效的括号

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

150.逆波兰表达式求值

1 有效的括号

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

有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。
• 注意空字符串可被认为是有效字符串。

1.1 思路：

栈

3种错误情况：

1. 奇数次多余
2. 不匹配
3. 偶数次多余

1.2 代码：

    //4.有效的括号
    bool isValid(string s){
        //1. 情况1，字符串的字符个数为奇数
        if(s.size()/2 != 0){
            return false;
        }
        //2. 
        stack<char> st;
        for(int i = 0; i < s.size(); i++){
            if(s[i] == '('){
                st.push(')');
            }
            else if (s[i] == '[')
            {
                st.push(']');
            }
            else if(s[i] == '{'){
                st.push('}');
            }//后半段空了，说明对应不上；不同说明不匹配
            else if(st.empty() || st.top() != s[i]){
                return false;
            }
            else{
                st.pop();
            }

            return st.empty();
            
        }
    }

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

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

2.1 思路：

栈

字符串遍历，往栈中放，相同就弹出，不同就放入

2.2 代码：

    string removeSameStr(string s){
        stack<char> st;
        for(char a : s){//判断是不是相同字符
            if(st.empty() || s != st.top()){
                st.push(a);
            }
            else{
                st.pop();
            }
        }
        string result = "";
        while (!st.empty())
        {
            result += st.top();
            st.pop();
        }
        reverse(result.begin(), result.end());
        return result;
        
    }

3 逆波兰表达式求值

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

有效的运算符包括 + , - , * , / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

3.1 思路：

遇到运算符取2个值运算。

3.2 代码：

    int evalRPN(vector<string>& tokens) {
                stack<long long> st; 
        
        for (int i = 0; i < tokens.size(); i++) {
            //如果是运算符就弹出2个元素，并运算放入栈；否则把字符放入栈
            if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
                long long num1 = st.top();
                st.pop();
                long long num2 = st.top();
                st.pop();
                if (tokens[i] == "+") st.push(num2 + num1);
                if (tokens[i] == "-") st.push(num2 - num1);
                if (tokens[i] == "*") st.push(num2 * num1);
                if (tokens[i] == "/") st.push(num2 / num1);
            } else {
                st.push(stoll(tokens[i]));
            }
        }

        int result = st.top();
        st.pop(); 
        return result;

    }