题目描述与示例
题目描述
已知火星人使用的运算符号为 # 、$
他们与地球人的等价公式如下：
x#y = 4*x+3*y+2x$y = 2*x+y+3
其中 x y 是无符号整数
地球人公式按照 C 语言规则进行计算
火星人公式中 # 符优先级高于 $
相同的运算符按从左到右的顺序运算
输入描述
火星人字符串表达式结尾不带回车换行
输入的字符串说明：
字符串为仅有无符号整数和操作符组成的计算表达式
- 用例保证字符串中操作数与操作符之间没有任何分隔符
- 用例保证操作数取值范围为
32位无符号整数 - 保证输入以及计算结果不会出现整型溢出
- 保证输入的字符串为合法的求值报文 例如:
123#45#7678 - 保证不会出现非法的求值报文
例如：
#4$5这种缺少操作数；4$5#这种缺少操作数；4#$5这种缺少操作数；4 $5有空格；3+4-5*6/7有其他操作符；12345678987654321$5432132 位整数溢出
输出描述
根据火星人字符串输出计算结果，结尾不带回车换行
示例
输入
7#6$5#12
输出
157
说明
7#65#12=(4*7+3*6+2)5#12
=485#12
=48(4*5+3*12+2)
=48$58
=2*48+58+3
=157
解题思路
这是一个非常典型的中缀表达式求值类的问题，类似于LC224. 基本计算器 但是更简单一些。
代码
Python
# 题目：【栈】2023C-火星文计算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 Scanner(System.in);
String s = sc.nextLine();
Stack<Integer> stack = new Stack<>();
boolean preSignWell = false;
int num = 0;
// 在字符串末尾加一个空格，用于处理最后一个数字的情况
s += " ";
for (char ch : s.toCharArray()) {
if (Character.isDigit(ch)) {
num = num * 10 + Character.getNumericValue(ch);
} else {
stack.push(num);
num = 0;
if (preSignWell) {
int y = stack.pop();
int x = stack.pop();
int res = calWell(x, y);
stack.push(res);
}
preSignWell = (ch == '#');
}
}
int ans = stack.get(0);
for (int i = 1; i < stack.size(); i++) {
int y = stack.get(i);
ans = calDollar(ans, y);
}
System.out.println(ans);
}
private static int calWell(int x, int y) {
return 4 * x + 3 * y + 2;
}
private static int calDollar(int x, int y) {
return 2 * x + y + 3;
}
}
C++
“`C++
#include <iostream>
#include <vector>
using namespace std;
int calWell(int x, int y) {
return 4 * x + 3 * y + 2;
}
int calDollar(int x, int y) {
return 2 * x + y + 3;
}
int main() {
string s;
getline(cin, s);
<pre><code>vector<int> vec;
bool preSignWell = false;
int num = 0;
// 在字符串末尾加一个空格，用于处理最后一个数字的情况
s += " ";
for (char ch : s) {
if (isdigit(ch)) {
num = num * 10 + (ch – '0');
} else {
vec.push_back(num);
num = 0;
if (preSignWell) {
int y = vec[vec.size() – 1];
vec.pop_back();
int x = vec[vec.size() – 1];
vec.pop_back();
int res = calWell(x, y);
vec.push_back(res);
}
preSignWell = (ch == '#');
}
}
int ans = vec[0];
for (int i = 1; i < vec.size(); i++) {
int y = vec[i];
ans = calDollar(ans, y);
}
cout << ans << endl;
return 0;
</code></pre>
}
“`
时空复杂度
时间复杂度：O(N)。需要一次遍历每一个字符
空间复杂度：O(N)。栈所需空间。
说明
华为OD机试有三道题⽬，第⼀道和第⼆道属于简单或中等题，分值为 100 分，第三道为中等或困难题，分值为 200分，总分为 400 分。
机试分数越⾼评级越⾼，⼯资也就越⾼。
关于华为 OD 机试更加详细的介绍可以查看这篇⽂章：华为OD机考须知
关于机考题目汇总可以看这篇文章：华为OD机试真题 2023 A+B+C+D卷 + 2024新卷（Python&Java&C++）⽬录汇总（每⽇更新）
