【华为OD机试】-(C卷+D卷)-2024最新真题目录

题目描述

给定一个表达式，求其分数计算结果。

表达式的限制如下：

• 所有的输入数字皆为正整数（包括0）
• 仅支持四则运算（+-*,/）和括号
• 结果为整数或分数，分数必须化为最简格式（比如6，3/4，7/8，90/7）
• 除数可能为0，如果遇到这种情况，直接输出"ERROR"
• 输入和最终计算结果中的数字都不会超出整型范围
• 用例输入一定合法，不会出现括号匹配的情况

输入描述

字符串格式的表达式，仅支持+-*,/，数字可能超过两位，可能带有空格，没有负数

长度小于200个字符

输出描述

表达式结果，以最简格式表达

• 如果结果为整数，那么直接输出整数
• 如果结果为负数，那么分子分母不可再约分，可以为假分数，不可表达为带分数
• 结果可能是负数，符号放在前面

用例1

输入

1 + 5 * 7 / 8

输出

43/8

说明

无

用例2

输入

1 / (0 - 5)

输出

-1/5

说明

符号需要提到最前面

用例3

输入

1 * (3*4/(8-(7+0)))

输出

12

说明

注意括号可以多重嵌套

解题思路

关于符号运算的题目，需要用到两个栈，一个栈用来存符号op_stack，另一个栈用来存数值num_stack；

解题过程是，遍历算式的每一个字符，如果是字符为数字，则暂时存入一个缓存数字

的栈str_stack，防止整数是多位的情况。

如果遍历到字符为+-*/，需要进行两个操作：

1.将str_stack中的字符拿出，组成整数，存入num_stack；

2.比较当前符号和op_stack栈顶符号的优先级，如果op_stack不为空，且op_stack栈顶符号优先级>=当前符号，则先令栈顶符号出栈，再从num_stack中出栈两个数，与栈顶符号计算出结果后，放入num_stack中。否则，将操作符入栈。

如果遍历到(时，直接将符号放入op_stack栈中，之后遇到除)之外的字符，和前面的操作步骤一样，当遇到)时，要将op_stack栈中的符号出栈，进行计算，直至遇到（时结束，将(出栈；

本题存在分数&