OD统一考试（C卷）
分值： 100分
题解： Java / Python / C++
题目描述
已知火星人使用的运算符号为 #和$
其与地球人的等价公式如下
x#y=2*x+3*y+4
x$y=3*x+y+2
- x y是无符号整数。
- 地球人公式按照c语言规则进行计算。
- 火星人公式中，# 号的优先级高于 $ ,相同的运算符，按从左往右的顺序计算
现有一段火星人的字符串报文，请你来翻译并计算结果
输入描述
火星人的字符串表达式（结尾不带回车换行）
输入的字符串说明：字符串为仅无符号整数和操作符（#、$）组成的计算表达式，例如：123#4$5#67$78
用例保证字符串中，操作数与操作符之间没有任何分隔符
用例保证操作数取值范围为 3232 为无符号整数
保证输入以及计算结果不会出现int整数溢出
保证输入的字符串为合法的求值报文，例如：123#4$5#67$78
保证不会出现非法的求值报文，例如类似这样字符串:
#4$5 //缺少操作数 4$5# //缺少操作数 4#$5 //缺少操作数 4 $5 //有空格 3+4-5*6/7 //有其他操作符 1234567897654321$54321 //32位整数计算溢出
输出描述
根据输入的火星人字符串输出计算结果（结尾不带回车换行）
示例1
输入：
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
题解
解题思路：
- 题目要求对火星人的字符串表达式进行翻译并计算结果，其中火星人的运算符为
#和$，并给出了等价的地球人公式。- 使用栈来模拟计算过程，遍历字符串，遇到数字则累积，遇到运算符则进行相应的计算。
- 定义优先级，按照规定的优先级顺序进行计算。
- 最终栈中的结果即为计算结果。
代码大致描述：
- 使用栈
nums存储数字，栈ops存储运算符，变量t用于临时存储数字。- 定义操作符的优先级
priority。- 定义一个计算的函数
calc，用于出栈计算，并根据运算符进行相应的计算。- 遍历字符串，遇到数字则累积到
t中，遇到运算符则将t压入nums，并根据优先级进行出栈计算。- 遍历结束后，将
t压入nums。- 最后，根据运算符的优先级，进行出栈计算直到操作符栈为空，返回栈顶元素作为最终结果。
Java
import java.util.*;
/**
* @author code5bug
*/
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String input = scanner.nextLine();
System.out.print(solve(input));
}
public static int solve(String s) {
// 数据栈， 操作符栈， 数字临时变量
Stack<Integer> nums = new Stack<>();
Stack<Character> ops = new Stack<>();
int t = 0;
// 操作符优先级
HashMap<Character, Integer> priority = new HashMap<>();
priority.put('#', 2);
priority.put('$', 1);
// 进行出栈计算
Runnable calc = () -> {
int y = nums.pop(), x = nums.pop();
char op = ops.pop();
if (op == '#') {
nums.push(4 * x + 3 * y + 2);
} else {
nums.push(2 * x + y + 3);
}
};
for (char c : s.toCharArray()) {
if (Character.isDigit(c)) {
t = t * 10 + Character.getNumericValue(c);
continue;
}
nums.push(t);
// 相同优先级或之前优先级高则出栈计算
while (!ops.isEmpty() && priority.get(ops.peek()) >= priority.get(c)) {
calc.run();
}
ops.push(c);
t = 0;
}
nums.push(t);
// 出栈计算， 直到操作符栈为空
while (!ops.isEmpty()) {
calc.run();
}
return nums.peek();
}
}
Python
def solve(s: str) -> int:
# 数据栈， 操作符栈， 数字临时变量
nums, ops, t = [], [], 0
# 操作符优先级
priority = {
'#': 2, '$': 1}
def calc(): # 进行出栈计算
y, x = nums.pop(), nums.pop()
op = ops.pop()
if op == '#':
nums.append(4 * x + 3 * y + 2)
else:
nums.append(2 * x + y + 3)
for c in s:
if c.isdigit():
t = t * 10 + int(c)
continue
nums.append(t)
# 相同优先级或之前优先级高则出栈计算
while ops and priority[ops[-1]] >= priority[c]:
calc()
ops.append(c)
t = 0
nums.append(t)
# 出栈计算， 直到操作符栈为空
while ops:
calc()
return nums[-1]
print(solve(input()))
C++
#include <iostream>
#include <stack>
#include <unordered_map>
using namespace std;
int solve(string s) {
// 数据栈， 操作符栈， 数字临时变量
stack<int> nums;
stack<char> ops;
int t = 0;
// 操作符优先级
unordered_map<char, int> priority;
priority['#'] = 2;
priority['$'] = 1;
// 进行出栈计算
auto calc = [&]() {
int y = nums.top(); nums.pop();
int x = nums.top(); nums.pop();
char op = ops.top(); ops.pop();
if (op == '#') {
nums.push(4 * x + 3 * y + 2);
} else {
nums.push(2 * x + y + 3);
}
};
for (char c : s) {
if (isdigit(c)) {
t = t * 10 + (c - '0');
continue;
}
nums.push(t);
// 相同优先级或之前优先级高则出栈计算
while (!ops.empty() && priority[ops.top()] >= priority[c]) {
calc();
}
ops.push(c);
t = 0;
}
nums.push(t);
// 出栈计算， 直到操作符栈为空
while (!ops.empty()) {
calc();
}
return nums.top();
}
int main() {
string input;
getline(cin, input);
cout << solve(input);
return 0;
}
相关练习题
| 题号 | 题目 | 难易 |
|---|---|---|
| LeetCode 227 | 227. 基本计算器 II | 中等 |
| LeetCode 224 | 224. 基本计算器 | 困难 |
❤️华为OD机试面试交流群（每日真题分享）： 加V时备注“华为od加群”
🙏整理题解不易， 如果有帮助到您，请给点个赞 ❤️ 和收藏 ⭐，让更多的人看到。🙏🙏🙏
