[栈的应用]有效的括号|删除字符串中的所有相邻重复项|逆波兰式求值

一、有效的括号

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

有效字符串需满足：

1.左括号必须用相同类型的右括号闭合。

2.左括号必须以正确的顺序闭合。

3.每个右括号都有一个对应的相同类型的左括号

class Solution {
public:
    bool isValid(string s) {
        stack<char> p;
        p.push('#');//防止非法访问栈顶元素
        for (int i = 0; i < s.size(); i++) {
            if ((s[i] == ')' && p.top() == '(') ||
                (s[i] == ']' && p.top() == '[') ||
                (s[i] == '}') && p.top() == '{') {   
                p.pop();   //if匹配成功入栈
            } else {
                p.push(s[i]);//没匹配成功入栈
            }
        }
        return p.top() == '#';
    }
};

?思路：每次和栈顶元素比较，匹配的话栈顶出栈，不匹配的话，压栈。最后栈只剩#代表是有效的括号。加入#的目的是因为为了防止最开始，无法和栈顶元素比较。

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

输入："abbaca" 输出："ca"

class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> p;
        string q="";
        p.push('#');
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == p.top())
                p.pop();
            else
                p.push(s[i]);
        }
        int i=0;
        while(p.top()!='#')
        {
             q.push_back(p.top());
             p.pop();
        }
        reverse(q.begin(),q.end());
        return  q;
    }
};

思路：此题和上面有效的括号异曲同工

三、输入：tokens = ["2","1","+","3","*"] 输出：9

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> p;
        for (int i = 0; i < tokens.size(); i++) {
            string s = tokens[i];
            if (s != "+" && s != "-" && s != "*" && s != "/")
                p.push(atoi(s.c_str()));
            else {
                int num1 = p.top();
                p.pop();
                int num2 = p.top();
                p.pop();
                if (s == "+") {
                    p.push(num2 + num1);
                }
                if (s == "-") {
                    p.push(num2 - num1);
                }
                if (s == "*") {
                    p.push(num2 * num1);
                }
                if (s == "/") {
                    p.push(num2 / num1);
                }
            }
        }
        return p.top();
    }
};