python coding with ChatGPT 打卡第10天| 栈和队列：有效的括号 逆波兰表达式求值

相关推荐
python coding with ChatGPT 打卡第9天| 栈和队列：基础知识

有效的括号

Key Points

匹配问题都是栈的强项

相关题目

20. 有效的括号

视频讲解

栈的拿手好戏

重点分析

def isValid(s):
    str_dict = {'(':')', '{':'}', '[':']'}
    stack_record = []

    for char in s:
        if char in str_dict.keys():
            stack_record.append(str_dict[char])
        else:
            if stack_record:
                if char != stack_record.pop():
                    return False
            else:
                return False
    if len(stack_record) != 0:
        return False
    return True

def isValid(s):
    str_dict = {'(': ')', '{': '}', '[': ']'}
    stack_record = []

    for char in s:
        if char in str_dict:  # 优化点 1
            stack_record.append(char)
        else:
            if not stack_record or str_dict[stack_record.pop()] != char:  # 优化点 2
                return False

    return not stack_record  # 优化点 3

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

相关题目

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

视频讲解

栈的好戏还要继续

重点分析

def removeDuplicates(s):
    stack_record = []
    for char in s:
        if stack_record and char == stack_record[-1]:
            stack_record.pop()
        else:
            stack_record.append(char)
    res = ''
    length = len(stack_record)
    for _ in range(length):
        res = stack_record.pop() + res
    return res

逆波兰表达式

Key Points

向上取整：math.ceil()
向下取整：math.floor()、整除"//"
四舍五入：round()
向0取整：int()

相关题目

150. 逆波兰表达式

视频讲解

栈的最后表演

重点分析

def evalRPN(tokens):
    cal_set = {'+', '-', '*', '/'}
    stack_record = []
    for token in tokens:
        if token in cal_set:
            second_val = stack_record.pop()
            first_val = stack_record.pop()

            new_val = int(eval(first_val+token+second_val))
            stack_record.append(str(new_val))
        else:
            stack_record.append(token)

    return int(stack_record[-1])