算法D11 | 栈和队列练习 | 20. 有效的括号 1047. 删除字符串中的所有相邻重复项 150. 逆波兰表达式求值

20. 有效的括号 

讲完了栈实现队列，队列实现栈，接下来就是栈的经典应用了。 

大家先自己思考一下 有哪些不匹配的场景，在看视频 我讲的都有哪些场景，落实到代码其实就容易很多了。题目链接/文章讲解/视频讲解。

由于括号匹配的问题，利用栈FILO的特点实现。

Python版本：

class Solution:
    def isValid(self, s: str) -> bool:
        p_dict = {')':'(', '}':'{', ']':'['}
        stk = []
        for k in s:
            if not k in p_dict.keys():
                stk.append(k)
            else:
                if len(stk)==0:
                    return False
                v = stk.pop()
                if p_dict[k] != v:
                    return False
        return len(stk)==0

C++版本：

class Solution {
public:
    bool isValid(string s) {
        if (s.size()%2!=0) return false;
        stack st;
        for (int i=0; i str:
        stk = []
        prev = None
        for cur in s:
            stk.append(cur)
            while len(stk)>=2 and stk[-1]==stk[-2]:
                stk = stk[:-2]
        return "".join(stk)

C++版本：

字符串可以直接作为栈。

class Solution {
public:
    string removeDuplicates(string s) {
        string result;
        for (int i=0; i int:
        op_set = set(['+', '-', '*', '/'])
        stk = []
        for cur in tokens:
            if cur in op_set:
                num2 = stk.pop()
                num1 = stk.pop()
                exp = num1 + cur + num2
                ans = int(eval(exp))
                stk.append(str(ans))
            else:
                stk.append(cur)
        return int(stk[0])

C++版本:

class Solution {
public:
    int evalRPN(vector& tokens) {
        stack st;
        for (int i=0; i