继续今天的算法学习，学习几道栈相关的算法题。
- 1、LeetCode 20、有效的括号
- 2、LeetCode 1614、括号的最大嵌套深度
- 3、LeetCode 150、逆波兰表达式求值
一、LeetCode 20、有效的括号
题目描述
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 1、左括号必须用相同类型的右括号闭合。
- 2、左括号必须以正确的顺序闭合。
题目解析
有效的括号满足以下几个条件：
- 1、字符串的长度一定是偶数。
- 2、括号的匹配遵循右括号和最近的一个左括号进行匹配，它们匹配成功才有可能是有效的括号
在这个问题中，主要涉及到栈这一数据结构。栈是一种先进后出（LIFO）的数据结构，只允许在一端进行插入和删除操作。
算法考察点
- 栈的应用：使用栈来处理括号匹配问题。
- 字符串遍历：遍历字符串并进行判断。
- 括号匹配：利用栈来验证括号的有效性。
算法思路
- 初始化一个空栈。
- 遍历字符串的每个字符：
- 如果是左括号，则将其入栈。
- 如果是右括号，则判断栈是否为空，为空则返回 False；不为空则将栈顶元素出栈并与当前右括号匹配，若不匹配则返回 False。
- 遍历完字符串后，若栈为空，则括号匹配有效，返回 True；否则返回 False。
代码解析
代码语言：javascript复制# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# // 有效的括号（ LeetCode 20 ）:https://leetcode-cn.com/problems/valid-parentheses
class Solution:
def isValid(self, s: str) -> bool:
# 当字符串长度为奇数的时候，属于无效情况，直接返回 False
if len(s) % 2 == 1:
# 无效情况，返回 False
return False
# 构建一个栈，用来存储括号
stack = list()
# 遍历字符串数组中的所有元素
for c in s :
# 如果字符为左括号 ( ，那么就在栈中添加对左括号 （
if c == '(' :
# 添加对左括号 （
stack.append('(')
# 如果字符为左括号 [ ，那么就在栈中添加对左括号 [
elif c == '[' :
# 添加对应的右括号 ]
stack.append('[')
# 如果字符为左括号 { ，那么就在栈中添加对左括号 {
elif c == '{' :
# 添加对应的右括号 }
stack.append('{')
# 否则的话，说明此时 c 是 ）] } 这三种符号中的一种
else :
# 如果栈已经为空，而现在遍历的字符 c 是 ）] } 这三种符号中的一种
# 找不到可以匹配的括号，返回 False
# 比如这种情况 }{，直接从右括号开始，此时栈为空
if not stack :
return False
# 如果栈不为空，获取栈顶元素
top = stack[-1]
# 将栈顶元素和此时的元素 c 进行比较，如果相同，则将栈顶元素移除
if (top == '(' and c == ')' ) or (top == '[' and c == ']' ) or (top == '{' and c == '}') :
# 移除栈顶元素
stack.pop()
else :
# 如果不相同，说明不匹配，返回 False
return False
# 遍历完整个字符数组，判断栈是否为空
# 如果栈为空，说明字符数组中的所有括号都是闭合的
# 如果栈不为空，说明有未闭合的括号
return not stack
这段代码通过遍历字符串中的每个字符，并利用栈来验证括号的有效性。如果遇到左括号，则入栈；如果遇到右括号，则与栈顶元素匹配，若匹配则出栈，若不匹配则返回 False。遍历完字符串后，若栈为空，则括号匹配有效，返回 True；否则返回 False。
算法的优势
- 算法通过栈来实现括号的匹配验证，逻辑清晰，代码简洁。
- 时间复杂度为 O(n)，遍历一次字符串，空间复杂度为 O(n)，使用了额外的栈空间。
易错点
- 在处理右括号时，需要判断栈是否为空，避免空栈出栈操作导致错误。
- 在判断括号匹配时，需要注意栈顶元素与当前字符的匹配关系。
二、LeetCode 1614、括号的最大嵌套深度
题目描述
如果字符串满足以下条件之一，则可以称之为 有效括号字符串（valid parentheses string，可以简写为 VPS）：
- 字符串是一个空字符串
""，或者是一个不为"("或")"的单字符。 - 字符串可以写为
AB（A与B字符串连接），其中A和B都是 有效括号字符串 。 - 字符串可以写为
(A)，其中A是一个 有效括号字符串 。
类似地，可以定义任何有效括号字符串 S 的 嵌套深度 depth(S)：
depth("") = 0depth(C) = 0，其中C是单个字符的字符串，且该字符不是"("或者")"depth(A B) = max(depth(A), depth(B))，其中A和B都是 有效括号字符串depth("(" A ")") = 1 depth(A)，其中A是一个 有效括号字符串
例如：""、"()()"、"()(()())" 都是 有效括号字符串（嵌套深度分别为 0、1、2），而 ")(" 、"(()" 都不是 有效括号字符串 。
给你一个 有效括号字符串 s，返回该字符串的 s 嵌套深度 。
示例 1：
输入：s = "(1 (2*3) ((8)/4)) 1" 输出：3 解释：数字 8 在嵌套的 3 层括号中。
示例 2：
输入：s = "(1) ((2)) (((3)))" 输出：3
提示：
1 <= s.length <= 100s由数字0-9和字符' '、'-'、'*'、'/'、'('、')'组成- 题目数据保证括号表达式
s是 有效的括号表达式
题目解析
算法考察点
- 栈的应用：使用栈来处理括号匹配问题。
- 字符串遍历：遍历字符串并进行处理。
- 括号匹配：利用栈来验证括号的有效性。
算法思路
- 初始化两个变量
ans和size，分别表示最大嵌套深度和当前栈的大小，初始值均为 0。 - 遍历字符串 s 中的每个字符：
- 如果当前字符是左括号 '('，则将其入栈，同时更新栈的大小
size。 - 如果当前字符是右括号 ')'，则将栈顶的左括号出栈，同时更新栈的大小
size。
- 如果当前字符是左括号 '('，则将其入栈，同时更新栈的大小
- 在遍历过程中，不断更新最大嵌套深度
ans，即取ans和size的较大值。 - 遍历完成后，
ans即为所求的最大嵌套深度。
代码解析
代码语言：javascript复制class Solution:
def maxDepth(self, s: str) -> int:
# size 表示栈的大小
# ans 表示 size 的最大值，也就是最终的结果值
ans, size = 0, 0
# 遍历字符串 s
for ch in s:
# 如果遇到了一个左括号，将其入栈
if ch == '(':
# 栈中元素的个数加 1
size = 1
# 更新深度的值
ans = max(ans, size)
# 如果遇到了一个右括号，弹出栈顶的左括号
elif ch == ')':
# 栈中元素的个数减 1
size -= 1
# 返回最大值
return ans
这段代码通过遍历字符串 s 中的每个字符，并利用栈来验证括号的有效性。遍历过程中，通过记录栈的大小 size 并不断更新最大嵌套深度 ans，最终返回 ans 作为结果。
算法的优势
- 算法通过栈来实现括号的匹配验证，逻辑清晰，代码简洁。
- 时间复杂度为 O(n)，遍历一次字符串，空间复杂度为 O(1)，只使用了常量级的额外空间。
易错点
- 在处理右括号时，需要确保栈中有左括号，避免空栈出栈操作导致错误。
- 在更新最大嵌套深度时，需要取当前栈的大小和历史最大值的较大值。
三、LeetCode 150、逆波兰表达式求值
题目描述
根据 逆波兰表示法，求表达式的值。
有效的算符包括 、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
注意 两个整数之间的除法只保留整数部分。
可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1：
输入：tokens = ["2","1"," ","3","*"] 输出：9 解释：该算式转化为常见的中缀算术表达式为：((2 1) * 3) = 9
示例 2：
输入：tokens = ["4","13","5","/"," "] 输出：6 解释：该算式转化为常见的中缀算术表达式为：(4 (13 / 5)) = 6
示例 3：
输入：tokens = ["10","6","9","3"," ","-11","","/","","17"," ","5"," "] 输出：22 解释：该算式转化为常见的中缀算术表达式为： ((10 * (6 / ((9 3) * -11))) 17) 5 = ((10 * (6 / (12 * -11))) 17) 5 = ((10 * (6 / -132)) 17) 5 = ((10 * 0) 17) 5 = (0 17) 5 = 17 5 = 22
提示：
1 <= tokens.length <= 10^4tokens[i]是一个算符（" "、"-"、"*"或"/"），或是在范围[-200, 200]内的一个整数
逆波兰表达式：
逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
- 平常使用的算式则是一种中缀表达式，如
( 1 2 ) * ( 3 4 )。 - 该算式的逆波兰表达式写法为
( ( 1 2 ) ( 3 4 ) * )。
逆波兰表达式主要有以下两个优点：
- 去掉括号后表达式无歧义，上式即便写成
1 2 3 4 *也可以依据次序计算出正确结果。 - 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中
题目解析
算法考察点
- 栈的应用：使用栈来实现逆波兰表达式的计算。
- 字符串处理：对逆波兰表达式进行遍历和操作数的转换。
- 运算符的处理：对运算符进行操作，并进行计算。
算法思路
- 初始化一个空列表
result作为栈，用于存储操作数。 - 遍历逆波兰表达式中的每个元素 token
- 如果
token是运算符，则从栈中弹出两个操作数，进行相应的计算，并将结果压入栈中。 - 如果
token是操作数，则将其转换为整数，并压入栈中。
- 如果
- 遍历完整个表达式后，栈顶元素即为计算结果。
代码解析
代码语言：javascript复制class Solution:
def evalRPN(self, tokens: List[str]) -> int:
result = [] # 初始化一个列表作为栈，存储操作数
# 遍历字符串数组
for token in tokens:
if token in " -*/": # 如果是运算符
rightNum = result.pop() # 先出栈的是右操作数
leftNum = result.pop() # 后出栈的是左操作数
# 根据运算符进行计算
if token == " ":
ans = leftNum rightNum
elif token == "-":
ans = leftNum - rightNum
elif token == "*":
ans = leftNum * rightNum
elif token == "/":
ans = int(leftNum / rightNum) # 注意整除
else:
ans = int(token) # 如果是数字，转换为整数
result.append(ans) # 将计算结果压入栈中
return result[-1] # 返回栈顶元素
算法的优势
- 通过栈来实现逆波兰表达式的计算，逻辑清晰，代码简洁。
- 时间复杂度为 O(n)，遍历一次表达式，空间复杂度为 O(n)，使用了额外的栈空间。
易错点
- 在处理除法运算时，需要注意整除和浮点数除法的区别，避免计算错误。
- 在处理运算符时，需要确保栈中有足够的操作数，避免空栈出栈操作导致错误。
