华为OD统一考试 - 符号运算

题目描述

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

表达式的限制如下：

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

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

输入描述

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

长度小于200个字符

输出描述

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

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

用例

题目解析

本题是经典的中缀表达式计算问题。

双栈实现中缀表达式计算

关于中缀表达式计算，通常是定义两个栈结构：

• 一个栈用于记录操作数：假设为oper_num_stack
• 一个栈用于记录操作符：假设为oper_sign_stack

下面我们通过几个例子来说明两个栈的工作原理：

通过上面流程，我们可以发现，每次出栈oper_sign_stack一个运算符，那么就要出栈oper_num_stack两个操作数。

那么如果存在下面这种情况，是否支持这样的出栈运算逻辑呢？

上面运算出错的问题就在于，当+入栈oper_sign_stack前，我们应该比较要入栈的'+'运算，和栈顶的'*'运算，哪个优先级更高，如果栈顶运算符优先级更高，此时我们应该先将栈顶运算符出栈运算，即如下：

另外，对于运算符入栈时，对比oper_sign_stack栈顶的运算符，如果二者优先级一样，则也需要将oper_sign_stack栈顶运算先出栈运算。

且只要oper_sign_stack栈顶的运算符 的优先级>= 需要入栈的运算符，则oper_sign_stack就需要不停的出栈运算。

因此，总结一下就是，如果扫描到了运算符，此时需要和oper_sign_stack栈顶的运算符比较优先级，如果栈顶运算符优先级 >= 当前扫描运算符，则栈顶运算符需要出栈运算，直到oper_sign_stack栈顶运算符优先级小于当前扫描运算符。

另外，本题表达式中还可能出现()，那么遇到括号该怎么处理呢？

也就是说：

'(' 对于 +-*/ 运算的入栈oper_sign_stack的逻辑不产生影响，仅用于扫描到')'时oper_sign_stack的出栈结束界定。

需要注意的时，()内的+-*/运算依旧按照之前的逻辑入栈oper_sign_stack。

以上就是中缀表达式的基于双栈的解题思路。更具体的逻辑，请看代码实现。

分数的四则运算

本题还对中缀表达式计算做了一些改动，即要求的除法不是整除，而是保留最简分数结果。

比如 1 / 2 + 3 / 4 的结果不是0，而是 5 / 4。

解决方案很简单，我们之前在 oper_num_stack 中记录的都是整数操作数，现在我们只要改为分数操作数即可。

但是编程语言中并不支持分数，因此我们可以将分数拆分为分子和分母两部分，进行记录。即可以定义一个类，有如下属性：

{

    ch:, // 分子

    fa:, // 分母

}

分数的分子和分母必然是整数。

如果入栈的元素是一个整数num，则将其转化为如下分数后入栈oper_num_stack

{

    ch: num, 

    fa: 1, 

}

当我们需要进行出栈运算时，取出的oper_num_stack栈顶的两个操作数，假设分别为a,b，则：

对于加法运算的结果为：

{

    ch: a.ch * b.fa + b.ch * a.fa,

    fa: a.fa * b.fa,

}

比如 a = 1 / 3， b = 3 / 4，进行加法运算时，我们应该将他们的分母变为一样，即同时转为 3 * 4

则 a = (1 * 4) / (3 * 4)， b = （3 * 3）/  (4 * 3)

按照此逻辑，减法运算结果为：

{

    ch: a.ch * b.fa - b.ch * a.fa,

    fa: a.fa * b.fa,

}

而乘法运算结果：

{

    ch: a.ch * b.ch,

    fa: a.fa * b.fa,

}

除法运算结果为：

{

    ch: a.ch * b.fa,

    fa: a.fa * b.ch,

}

这样的话，我们就完成了分数的四则运算。

分数的最简格式转化

最后就是关于，分数的最简格式转化了，其实也很简单，就是将分子、分母的最大公约数求解出来，然后分子、分母同时除以最大公约数，即可得到最简格式的分数。

而两个数的最大公约数的求解，可以使用辗转相除法。如果不熟悉辗转相除法，可以去网上搜索相关资料。

import Foundation

func ODTest_2_35() {
    print("输入描述")
    print("字符串格式的表达式，仅支持+-*/，数字可能超过两位，可能带有空格，没有负数; 长度小于200个字符")
    let SN = (readLine() ?? "").map { String($0) }
    print("输出描述")
    print("表达式结果，以最简格式表达")
    // 操作数栈
    var oper_num: [Fractions] = []
    // 操作符栈
    var oper_sign: [String] = []

    print(getResult())

    func getResult() -> String {
        // +,-,*,/ 运算符优先级
        let priority = [
            "+": 1,
            "-": 1,