火星符号运算 - 华为OD统一考试(C卷)
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);
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
2024华为OD机试真题题解 文章被收录于专栏
华为OD机考(C卷、D卷)算法题库(绝对都是原题),帮助你上岸华为(已经不少小伙伴成功上岸)。提供Java、Python、C++ 三种语言的解法。每篇文章都有详细的解题步骤、代码注释详细及相关知识点的练习题。有问题,随时解答。 从 2024年4月24开始,考的都是华为OD统一考试(D卷),据已经参加D卷考试的同学反馈D卷和C卷是一样的,如果发现新题会及时更新。