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

20.有效的括号

思路
使用栈，当遇到’)‘，’}‘，’]‘时，元素出栈，判断是否为对应的’(‘，’{‘，’[’
代码

#  !/usr/bin/env  python
#  -*- coding:utf-8 -*-
# @Time   :  2022.11
# @Author :  hello algorithm!
# @Note   :  https://leetcode.cn/problems/valid-parentheses/
class Solution:
    """
    给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
    1. 使用栈，当遇到')'，'}'，']'时，元素出栈，判断是否为对应的'('，'{'，'['
    """

    def isValid(self, s: str) -> bool:
        stack = []
        for ele in s:
            if ele in ('(', '{', '['):
                stack.append(ele)
            if not stack:
                return False
            if ele == ')':
                s_str = stack.pop()
                if s_str != '(':
                    return False
            elif ele == '}':
                s_str = stack.pop()
                if s_str != '{':
                    return False
            elif ele == ']':
                s_str = stack.pop()
                if s_str != '[':
                    return False
        if stack:
            return False
        return True


if __name__ == '__main__':
    ss = "(]"
    s = Solution()
    print(s.isValid(ss))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

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

思路
使用栈
1. 当栈为空时，append元素
2. 当栈非空时，判断元素和栈顶元素是否相同，如果不相同，则入栈，如果相同，则出栈
3. 最终将栈转为字符串返回

代码

#  !/usr/bin/env  python
#  -*- coding:utf-8 -*-
# @Time   :  2022.11
# @Author :  hello algorithm!
# @Note   :  https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/
class Solution:
    """
    使用栈
    1. 当栈为空时，append元素
    2. 当栈非空时，判断元素和栈顶元素是否相同，如果不相同，则入栈，如果相同，则出栈
    3. 最终将栈转为字符串返回
    """

    def removeDuplicates(self, s: str) -> str:
        stack = []
        for ele in s:
            if not stack:
                stack.append(ele)
                continue
            s_str = stack[-1]
            if s_str == ele:
                stack.pop()
            else:
                stack.append(ele)
        return ''.join(stack)


if __name__ == '__main__':
    pass

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

150.逆波兰表达式求值

思路
使用栈
1. 入栈规则:元素非"+“、”-“、”" 或 “/”,元素入栈
2. 出栈规则:元素为非"+“、”-“、”" 或 “/”，则pop出两个元素，此处注意顺序哦！进行运算，将运算结果入栈
3. 将栈中元素返回
代码

#  !/usr/bin/env  python
#  -*- coding:utf-8 -*-
# @Time   :  2022.11
# @Author :  hello algorithm!
# @Note   :  https://leetcode.cn/problems/evaluate-reverse-polish-notation/
from typing import List


class Solution:
    """
    使用栈
    1. 入栈规则:元素非"+"、"-"、"*" 或 "/",元素入栈
    2. 出栈规则:元素为非"+"、"-"、"*" 或 "/"，则pop出两个元素，此处注意顺序哦！进行运算，将运算结果入栈
    3. 将栈中元素返回
    """

    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for ele in tokens:
            if ele == '+':
                b, a = stack.pop(), stack.pop()
                stack.append(a + b)
            elif ele == '-':
                b, a = stack.pop(), stack.pop()
                stack.append(a - b)
            elif ele == '*':
                b, a = stack.pop(), stack.pop()
                stack.append(a * b)
            elif ele == '/':
                b, a = stack.pop(), stack.pop()
                stack.append(int(a / b))
            else:
                stack.append(int(ele))
        return stack.pop()


if __name__ == '__main__':
    tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
    s = Solution()
    print(s.evalRPN(tokens))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41