02.02.03-Exercises.md

02.02.03 练习题目（第 06 天）

1. 0150. 逆波兰表达式求值

1.1 题目大意

描述：给定一个字符串数组 tokens，表示「逆波兰表达式」。

要求：求解表达式的值。

说明：

• 逆波兰表达式：也称为后缀表达式。

  • 中缀表达式 ( 1 + 2 ) * ( 3 + 4 ) ，对应的逆波兰表达式为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

• $1 \le tokens.length \le 10^4$。

• tokens[i] 是一个算符（+、-、* 或 /），或是在范围 $[-200, 200]$ 内的一个整数。

示例：

输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6


输入：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

2. 0394. 字符串解码

2.1 题目大意

描述：给定一个经过编码的字符串 s。

要求：返回 s 经过解码之后的字符串。

说明：

• 编码规则：k[encoded_string]。encoded_string 为字符串，k 为整数。表示字符串 encoded_string 重复 k 次。
• $1 \le s.length \le 30$。
• s 由小写英文字母、数字和方括号 [] 组成。
• s 保证是一个有效的输入。
• s 中所有整数的取值范围为 $[1, 300]$。

示例：

输入：s = "3[a]2[bc]"
输出："aaabcbc"


输入：s = "3[a2[c]]"
输出："accaccacc"

3. 0946. 验证栈序列

3.1 题目大意

描述：给定两个整数序列 pushed 和 popped，每个序列中的值都不重复。

要求：如果第一个序列为空栈的压入顺序，而第二个序列 popped 为该栈的压出序列，则返回 True，否则返回 False。

说明：

• $1 \le pushed.length \le 1000$。
• $0 \le pushed[i] \le 1000$。
• $pushed$ 的所有元素互不相同。
• $popped.length == pushed.length$。
• $popped$ 是 $pushed$ 的一个排列。

示例：

输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1


输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。

习题解析

1. 「0150. 逆波兰表达式求值」习题解析：网页链接、Github 链接
2. 「0394. 字符串解码」习题解析：网页链接、Github 链接
3. 「0946. 验证栈序列」习题解析：网页链接、Github 链接