华为OD机试 - 符号运算 - 递归（Java 2024 C卷 100分）

àì夳堔傛蜴生んèń 2024-05-06 09:35 28阅读 0赞

![在这里插入图片描述][986dcebce006483fb6846cb29a3928a7.gif_pic_center]

> 华为OD机试 2024C卷题库疯狂收录中，刷题[**点这里**][Link 1]

### 专栏导读 ###

本专栏收录于[《华为OD机试（JAVA）真题（A卷+B卷+C卷）》][OD_JAVA_A_B_C]。

**刷的越多，抽中的概率越大**，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

### 一、题目描述 ###

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

表达式的限制如下：

1.  所有的输入数字皆为正整数(包括0)
2.  仅支持四则运算(±\*/)和括号
3.  结果为整数或分数, 分数必须化为最简格式(比如6, 3/4, 7/8, 90/7)
4.  除数可能为0，如果遇到这种情况，直接输出"ERROR"
5.  输入和最终计算结果中的数字都不会超出整型范围

用例的输入一定合法, 不会出现括号不匹配的情况

### 二、输入描述 ###

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

长度小于200个字符

### 三、输出描述 ###

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

#### 1、输入 ####

1 / (0-5)

#### 2、输出 ####

\-1/5

### 四、解题思路 ###

此问题需要处理一个包含四则运算和括号的数学表达式，并正确处理分数和除法。关键步骤如下：

1、解析和计算表达式：

使用递归或栈来处理括号和操作符的优先级。  
支持整数和分数的四则运算。

2、处理分数：

对于每次运算结果，若为分数，则需要化简（约分）。  
使用两个整数表示分数（分子和分母），并在每次运算后使用最大公约数（GCD）来约分。

3、错误处理：

当遇到除数为零的情况，立即返回"ERROR"。

4、表达式结果格式：

如果分母为1，则输出整数。  
如果不为1，则输出最简分数格式。  
确保分数的符号只出现在分子上。

### 五、Java算法源码 ###

通过递归函数 eval() 来计算和解析包含括号的表达式。它支持基本的四则运算，并正确处理分数和整数。当除数为零时，它会捕获ArithmeticException并返回"ERROR"。

public class OdTest01 {
        
        public static void main(String[] args) {
        
            Scanner sc = new Scanner(System.in);
            String expression = sc.nextLine();
            String result = evaluate(expression);
            System.out.println(result);
        }
    
        private static String evaluate(String expression) {
        
            try {
        
                // 清除表达式中的空格
                expression = expression.replaceAll(" ", "");
                // 计算表达式结果
                BigInteger[] result = eval(expression, 0, expression.length());
                // 处理并格式化结果输出
                if (result[1].equals(BigInteger.ZERO)) {
        
                    return "ERROR";  // 遇到除数为零
                } else if (result[1].equals(BigInteger.ONE)) {
        
                    return result[0].toString();  // 结果为整数
                } else {
        
                    return result[0] + "/" + result[1];  // 输出最简分数
                }
            } catch (ArithmeticException e) {
        
                return "ERROR";
            }
        }
    
        // 解析并计算表达式
        private static BigInteger[] eval(String s, int start, int end) {
        
            // 分子和分母
            BigInteger numerator = BigInteger.ZERO;
            BigInteger denominator = BigInteger.ONE;
    
            BigInteger currentNumerator = BigInteger.ZERO;
            BigInteger currentDenominator = BigInteger.ONE;
    
            char lastOp = '+';
    
            for (int i = start; i < end; i++) {
        
                char ch = s.charAt(i);
    
                if (ch >= '0' && ch <= '9') {
        
                    // 数字的处理
                    int j = i;
                    while (j < end && Character.isDigit(s.charAt(j))) j++;
                    currentNumerator = new BigInteger(s.substring(i, j));
                    currentDenominator = BigInteger.ONE;
                    i = j - 1;
                } else if (ch == '(') {
        
                    // 括号的处理
                    int count = 1;
                    int j = i + 1;
                    while (j < end && count != 0) {
        
                        if (s.charAt(j) == '(') count++;
                        if (s.charAt(j) == ')') count--;
                        j++;
                    }
                    BigInteger[] res = eval(s, i + 1, j - 1);
                    currentNumerator = res[0];
                    currentDenominator = res[1];
                    i = j - 1;
                } else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
        
                    // 运算符的处理
                    if (lastOp == '+') {
        
                        numerator = numerator.multiply(currentDenominator).add(currentNumerator.multiply(denominator));
                        denominator = denominator.multiply(currentDenominator);
                    } else if (lastOp == '-') {
        
                        numerator = numerator.multiply(currentDenominator).subtract(currentNumerator.multiply(denominator));
                        denominator = denominator.multiply(currentDenominator);
                    } else if (lastOp == '*') {
        
                        numerator = numerator.multiply(currentNumerator);
                        denominator = denominator.multiply(currentDenominator);
                    } else if (lastOp == '/') {
        
                        numerator = numerator.multiply(currentDenominator);
                        denominator = denominator.multiply(currentNumerator);
                    }
                    // 约分
                    BigInteger gcd = numerator.gcd(denominator);
                    numerator = numerator.divide(gcd);
                    denominator = denominator.divide(gcd);
    
                    // 更新最后的操作符
                    lastOp = ch;
                    currentNumerator = BigInteger.ZERO;
                    currentDenominator = BigInteger.ONE;
                }
            }
    
            // 处理最后的运算符
            if (lastOp == '+') {
        
                numerator = numerator.multiply(currentDenominator).add(currentNumerator.multiply(denominator));
                denominator = denominator.multiply(currentDenominator);
            } else if (lastOp == '-') {
        
                numerator = numerator.multiply(currentDenominator).subtract(currentNumerator.multiply(denominator));
                denominator = denominator.multiply(currentDenominator);
            } else if (lastOp == '*') {
        
                numerator = numerator.multiply(currentNumerator);
                denominator = denominator.multiply(currentDenominator);
            } else if (lastOp == '/') {
        
                numerator = numerator.multiply(currentDenominator);
                denominator = denominator.multiply(currentNumerator);
            }
    
            // 约分
            BigInteger gcd = numerator.gcd(denominator);
            numerator = numerator.divide(gcd);
            denominator = denominator.divide(gcd);
    
            // 确保分母总是正数
            if (denominator.compareTo(BigInteger.ZERO) < 0) {
        
                denominator = denominator.negate();
                numerator = numerator.negate();
            }
    
            return new BigInteger[] {
        numerator, denominator};
        }
    }

### 六、效果展示 ###

#### 1、输入 ####

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

#### 2、输出 ####

#### 3、说明 ####

![在这里插入图片描述][8542c3e75b11440f8ab68ea7fcd2b55b.png_pic_center]

?下一篇：[华为OD机试 - 简易内存池 - 逻辑分析（Java 2024 C卷 200分）][OD_ - _ - _Java 2024 C_ 200]

?本文收录于，[华为OD机试（JAVA）真题（A卷+B卷+C卷）][OD_JAVA_A_B_C]

**刷的越多，抽中的概率越大**，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

![在这里插入图片描述][8dbe8dd8723c4636af5926ccf1c511b0.gif_pic_center]

[986dcebce006483fb6846cb29a3928a7.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/06/bde5a71816284bc9bd3bb109cf4ad2ff.gif
[Link 1]: https://blog.csdn.net/guorui_java/article/details/132683473
[OD_JAVA_A_B_C]: https://blog.csdn.net/guorui_java/category_12293298.html
[8542c3e75b11440f8ab68ea7fcd2b55b.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/06/1bc1813a20ae4a48b49fad708864b9b3.png
[OD_ - _ - _Java 2024 C_ 200]: https://blog.csdn.net/guorui_java/article/details/132197477
[8dbe8dd8723c4636af5926ccf1c511b0.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/06/bbfe141f6d614e2cbdaa8b3b3c77f8ee.gif