大家好，我是吴师兄。
2024 年 8 月开始，华为 OD 笔试从 2024D 卷改为2024E 卷。
E 卷里 70% 左右的题目都是以前 A/B/C/D 卷复用的旧题。如果之前的题目刷了不少，那么很大概率都能遇到原题。所以刷过往的题目也是非常有效果的。
相比起 D 卷，E 卷的题目难度平均了很多，删去了很多有争议的难题、偏题、错题。
D卷里面的：
-
难题【最短路问题】2024D-快递员的烦恼、【回溯】2024D-田忌赛马、【最小生成树】2024D-5G网络建设
-
偏题【模拟】2024D-学生重新排队、【模拟】2024D-移动元素获得最大数组和、【模拟】2024D-攀登者2
-
错题【DP】2024D-抢7游戏、【贪心】2024D-小朋友来自多少小区、【双指针】2024D-提取字符串中最长数学表达式
都删掉了。
E 卷中难度为困难的题目少了很多，难度为简单的题目也少了很多，超过 50% 的题目（无论分值）都属于中等难度的题目。
这样的难度调整对认真学习、打牢基础的同学是更有利的，能够有效避免因为运气原因遇到太难或描述有问题的题目而考不到理想分数的情况。
截止目前，
我们已经直播讲解了 151 道 E 卷的题目
，每一道题目都有详细的答题思路、视频讲解、搭配三到六种代码和逐行的中文注释、答疑，同时每周都会迭代和新增三到五题。
题目描述
已知火星人使用的运算符号为
#
、
$
他们与地球人的等价公式如下：
其中
x
y
是无符号整数
地球人公式按照 C 语言规则进行计算
火星人公式中
#
符优先级高于
$
相同的运算符按从左到右的顺序运算
输入描述
火星人字符串表达式结尾不带回车换行
输入的字符串说明
：
字符串为仅有无符号整数和操作符组成的计算表达式
-
-
-
-
保证输入的字符串为合法的求值报文 例如:
123#4$5#76$78
-
例如：
-
-
-
-
-
-
12345678987654321$54321
32 位整数溢出
输出描述
根据火星人字符串输出计算结果，结尾不带回车换行
示例
输入
7#6$5#12
输出
157
说明
7#6$5#12=(4*7+3*6+2)$5#12
=48$5#12
=48$(4*5+3*12+2)
=48$58
=2*48+58+3
=157
解题思路
这是一个非常典型的
中缀表达式求值类
的问题，类似于LC224. 基本计算器，LeetCode227. 基本计算器II。
对于这类表达式求值相关的栈题，我们通常需要考虑以下问题：
-
-
-
-
-
问题1：
遇到数字应该如何处理？
数字显然应该暂存在栈中，等待后续出栈进行运算。
由于需要处理
数字不止一位数
的情况，我们可以通过构建一个初始值为
0
的变量
num
，通过
num = num * 10 + int(ch)
的方式来更新数字。
这个技巧在很多类似题目都多次出现。
问题2：
遇到运算符应该如何处理？
题目告知，两种运算符中，
#
的优先级高于
$
。
思考小学数学的四则运算，
*
的优先级高于
+
。
我们在做数学四则运算的时候，总是会先处理乘除，再处理加减。
如果这道题的
#
是
*
，
$
是
+
，那么我们可以这样处理：
遇到
+
直接跳过（符号不入栈），把所有
*
运算处理完毕后，将栈中的所有元素进行
求和
即可。
（因为除了
*
，剩下的
+
，可以直接求和）
因此这道题也是类似，我们必须把
#
都处理了，再处理
$
。
遇到
$
直接跳过（符号不入栈），把所有
#
运算处理完毕后，在考虑最终的栈中情况（问题5）
问题3：
何时进行入栈操作？
在前一点中其实已经提到，遇到符号的时候是不进行入栈的。
但是，遇到符号的时候意味着一个数字已经完全取得了。
因此，数字的入栈时机是在遇到一个符号的时候，我们必须把之前得到的
num
入栈，同时重置数字
num = 0
问题4：
何时进行出栈以及运算操作？
出栈意味着运算。
考虑中缀表达式
12#34$56#78
如果我们想要计算
12#34
的结果，其实是不能在遍历到
#
的时候来计算的，因为这个时候我们并不知道
#
后面紧跟着的数字是什么。
也不能在遍历到数字
3
或
4
的时候来做计算，因为此时我们并不知道这个数字的位数是多少，无法确定当前得到的数字
num
就是我们想要的数字。
因此，进行出栈和计算的时机，一定是当遍历到一个新的符号的时候，也就是遍历到
$
的时候，才需要进行计算。
又结合上述的问题2，我们在第一次遍历的过程中，只需要计算
#
，所以我们可以使用一个布尔型变量
pre_sign_well
来标记
上一个运算符
是否为
#
。
该变量初始化为
False
，表示在遇到第一个数字的时候，肯定是不用进行出栈操作和运算的。
只有在遇到一个运算符，且发现上一个运算符是
#
的时候，也就是
pre_sign_well = True
的时候，才需要进行出栈和运算，且需要把运算结果重新压回栈中。
然后我们还需要根据新遇到的运算符，修改
pre_sign_well
的值。
另外根据问题3和4，原式子中的最后一个字符是数字，如果想要正确地取出最后一个数字并进行运算，我们可以
在原式子末尾增加一个非数字字符
，或者在循环过程中
判断是否已经遍历到最后一个字符
。
问题5：
退出循环后如何处理栈中内容？
退出循环后，原式子中的所有
#
运算符都已经处理完毕，栈中剩余元素都需要进行
$
运算。
和简单的
+
不同，我们不能够直接求和，我们再次对栈中所有元素进行循环，依次进行
$
运算即可。
代码
Python
# 题目：【栈】2024E-火星文计算2
# 分值：100
# 作者：许老师-闭着眼睛学数理化
# 算法：栈
# 代码看不懂的地方，请直接在群上提问
# 根据"#"进行计算
def cal_well(x, y):
return 4 * x + 3 * y + 2
# 根据"$"进行计算
def cal_dollar(x, y):
return 2 * x + y + 3
s = input()
stack = list()
# 一个标记，用于表示上一个计算符号是否是"#"
# 初始化为False
pre_sign_well = False
# 初始化遍历过程中储存的数字
num = 0
# 由于s的最后一个元素必定是数字
# 而运算是在遍历到非数字字符的时候才进行的
# 因此在遍历到最后的数字的时候
# 无法正确地对这个数字进行运算
# 因此在s的末尾加上一个空格
# 用于处理最后一个数字的情况
s += " "
# 遍历ch中的所有字符s
for ch in s:
# 如果ch是数字，则更新num
if ch.isdigit():
num = num * 10 + int(ch)
# 如果ch是字符，即"#"或"$"或空格" "
else:
# 则将num加入栈中，且重置num的值为0
stack.append(num)
num = 0
# 如果在这个符号之前的上一个符号是"#"
# 根据计算的优先级，需要对栈顶的两个元素进行计算
if pre_sign_well:
y = stack.pop()
x = stack.pop()
res = cal_well(x, y)
stack.append(res)
# 如果当前符号ch是"#"，则设置pre_sign_well为True
# 下次遇到非数字字符时，进行计算
pre_sign_well = (ch == "#")
# 退出循环后，栈中剩余若干元素，这些元素得进行"$"号的计算
# 对栈中所有的元素进行cal_dollar()函数的计算
ans = stack[0]
for y in stack[1:]:
ans = cal_dollar(ans, y)
print(ans)
Java
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Scanner sc = new
