返回目录

题目描述

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

表达式的限制如下：

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

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

输入描述

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

长度小于200个字符

输出描述

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

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

示例：

题目解析

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

双栈实现中缀表达式计算

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

• 一个栈用于记录操作数：假设为oper\_num\_stack
• 一个栈用于记录操作符：假设为oper\_sign\_stack

分数的四则运算

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

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

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

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

{
ch:, // 分子
fa:, // 分母
}

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

如果入栈的元素是一个整数num，则将其转化为如下分数后入 用于记录操作数的栈

{
ch: num,
fa: 1,
}

当我们需要进行出栈运算时，取出的 用于记录操作数的栈顶的两个操作数，假设分别为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,
}

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

分数的最简格式转化

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

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

Python算法源码

# 获取输入
expression = input()

# 操作数栈
operand_stack = []
# 操作符栈
operator_stack = []


# 分数类
class Fraction:
    def __init__(self, numerator, denominator):
        self.numerator = numerator
        self.denominator = denominator


# 辗转相除法，求两个数的最大公约数
def gcd(x, y):
    while y != 0:
        tmp = y
        y = x % y
        x = tmp
    return x


# 计算结果函数
def calculate():
    # 栈顶两个操作数
    b = operand_stack.pop()
    a = operand_stack.pop()

    # 运算符
    op = operator_stack.pop()

    # 计算结果
    result = Fraction(None, None)

    if op == '+':
        result.numerator = a.numerator * b.denominator + b.numerator * a.denominator
        result.denominator = a.denominator * b.denominator
    elif op == '-':
        result.numerator = a.numerator * b.denominator - b.numerator * a.denominator
        result.denominator = a.denominator * b.denominator
    elif op == '*':
        result.numerator = a.numerator * b.numerator
        result.denominator = a.denominator * b.denominator
    elif op == '/':
        result.numerator = a.numerator * b.denominator
        result.denominator = a.denominator * b.numerator

    operand_stack.append(result)


# 获取结果函数
def get_result():
    # 运算符优先级
    priority = {
        "+": 1,
        "-": 1,
        "*": 2,
        "/": 2
    }

    # 数字缓存容器
    num_str = []

    i = 0
    while i < len(expression):
        c = expression[i]

        # 数字字符
        if '9' >= c >= '0':
            while '9' >= c >= '0':
                num_str.append(c)
                if i + 1 >= len(expression):
                    break
                i += 1
                c = expression[i]

            # 转换为分数后压入栈
            operand_stack.append(Fraction(1, int("".join(num_str))))
            num_str.clear()

        # 运算符
        if c in ['+', '-', '*', '/']:
            while len(operator_stack) > 0 and operator_stack[-1] != '(' and priority[c] <= priority[operator_stack[-1]]:
                calculate()
            operator_stack.append(c)
        elif c == ')':
            while operator_stack[-1] != '(':
                calculate()
            operator_stack.pop()
        elif c == '(':
            operator_stack.append(c)

        i += 1

    while len(operand_stack) > 1:
        calculate()

    result = operand_stack.pop()

    if result.denominator == 0:
        return "ERROR"

    # 最大公约数
    k = gcd(result.numerator, result.denominator)
    result.numerator //= k
    result.denominator //= k

    # 符号
    sign = "-" if result.numerator * result.denominator < 0 else ""

    numerator = abs(result.numerator)
    denominator = abs(result.denominator)

    if numerator == 1:
        return f"{sign}{denominator}"
    else:
        return f"{sign}{denominator}/{numerator}"


# 调用算法
print(get_result())

C算法源码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 分数
typedef struct {
    int fa; // 分母
    int ch; // 分子
} Fractions;

// 操作数栈
Fractions oper_num[100];
int oper_num_top = -1;

// 操作符栈
char oper_sign[100];
int oper_sign_top = -1;

// 辗转相除法，求两个数的最大公约数
int getMaxCommonDivisor(int x, int y) {
    while (y != 0) {
        int tmp = y;
        y = x % y;
        x = tmp;
    }
    return x;
}

// 取出oper_num栈顶两个操作数进行运算
void calc() {
    // 操作数顺序会对运算产生影响
    Fractions b = oper_num[oper_num_top--]; // 栈顶元素是运算符右边的操作数
    Fractions a = oper_num[oper_num_top--]; // 栈顶倒数第二个元素是运算符左边的操作数

    // 运算符
    char op = oper_sign[oper_sign_top--];

    // 记录运算结果
    Fractions result;

    switch (op) {
        case '+':
            result.fa = a.fa * b.fa;
            result.ch = a.ch * b.fa + b.ch * a.fa;
            break;
        case '-':
            result.fa = a.fa * b.fa;
            result.ch = a.ch * b.fa - b.ch * a.fa;
            break;
        case '*':
            result.fa = a.fa * b.fa;
            result.ch = a.ch * b.ch;
            break;
        case '/':
            result.fa = a.fa * b.ch;
            result.ch = a.ch * b.fa;
            break;
    }

    oper_num[++oper_num_top] = result;
}

// 获取运算符优先级
int getPriority(char c) {
    switch (c) {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        default:
            return 0;
    }
}

// 求表达式结果
char* getResult(char* s) {
    // 操作数的字符缓存容器
    char numStr[20];

    int i = 0;
    while (i < strlen(s)) {
        char c = s[i];

        // 遇到数字字符
        if (c >= '0' && c <= '9') {
            // 则将该数字所在操作数的剩余数字字符一次性探索完
            int j = 0;
            while (c >= '0' && c <= '9') {
                numStr[j++] = c;
                if (i + 1 >= strlen(s)) break;
                c = s[++i];
            }
            numStr[j] = '\0';
            // 探索完后，将操作数缓存容器中记录的字符，变为分数后，压入操作数栈
            oper_num[++oper_num_top].fa = 1;
            oper_num[oper_num_top].ch = atoi(numStr);
        }

        // 遇到运算符
        if (c == '+' || c == '-' || c == '*' || c == '/') {
            // 只要栈顶运算符的优先级 >= 当前运算符，就需要不停出栈运算
            while (oper_sign_top >= 0 && oper_sign[oper_sign_top] != '(' &&
                   getPriority(c) <= getPriority(oper_sign[oper_sign_top])) {
                calc();
            }
            oper_sign[++oper_sign_top] = c;
        } else if (c == ')') {
            // 遇到')', 需要将操作符栈中靠近栈顶的'('后面的运算都出栈做了
            while (oper_sign[oper_sign_top] != '(') {
                calc();
            }
            // 最后将')'对应的'('出栈
            oper_sign_top--;
        } else if (c == '(') {
            // 遇到'('，则直接压倒操作符栈
            oper_sign[++oper_sign_top] = c;
        }

        i++;
    }

    // oper_num栈中还有2个以上的数，则还需要进行运算
    while (oper_num_top > 0) {
        calc();
    }

    // oper_num栈中只剩一个数时，该数就是表达式结果
    Fractions result = oper_num[oper_num_top--];

    // 如果结果的分母为0（除数为0），则不合法
    if (result.fa == 0) {
        return "ERROR";
    }

    // 求分子、分母的最大公约数，并进行约份，求得最简格式的分子，分母
    int k = getMaxCommonDivisor(result.fa, result.ch);
    result.fa /= k;
    result.ch /= k;

    // 求计算结果的符号，这里用乘法是为了避免 分母小，分子大，除法结果为0的情况，这样会丢失符号信息
    char* sign = (result.fa > 0 && result.ch < 0) || (result.fa < 0 && result.ch > 0) ? "-" : "";

    char* finalResult = (char*)malloc(20 * sizeof(char));

    int fa = abs(result.fa);
    int ch = abs(result.ch);

    if (fa == 1) {
        // 如果分母为1，则直接输出分子
        sprintf(finalResult, "%s%d", sign, ch);
    } else {
        // 如果分母不为1，则输出 分子 / 分母
        sprintf(finalResult, "%s%d/%d", sign, ch, fa);
    }

    return finalResult;
}

int main() {
    char expression[100];
    printf("Enter the expression: ");
    scanf("%s", expression);

    printf("%s\n", getResult(expression));

    return 0;
}

Java算法源码

import java.util.Scanner;

// 分数类
class Fractions {
    int fa; // 分母
    int ch; // 分子
}

public class Main {
    // 操作数栈
    static Fractions[] operNum = new Fractions[100];
    static int operNumTop = -1;

    // 操作符栈
    static char[] operSign = new char[100];
    static int operSignTop = -1;

    // 辗转相除法，求两个数的最大公约数
    static int getMaxCommonDivisor(int x, int y) {
        while (y != 0) {
            int tmp = y;
            y = x % y;
            x = tmp;
        }
        return x;
    }

    // 取出operNum栈顶两个操作数进行运算
    static void calc() {
        // 操作数顺序会对运算产生影响
        Fractions b = operNum[operNumTop--]; // 栈顶元素是运算符右边的操作数
        Fractions a = operNum[operNumTop--]; // 栈顶倒数第二个元素是运算符左边的操作数

        // 运算符
        char op = operSign[operSignTop--];

        // 记录运算结果
        Fractions result = new Fractions();

        switch (op) {
            case '+':
                result.fa = a.fa * b.fa;
                result.ch = a.ch * b.fa + b.ch * a.fa;
                break;
            case '-':
                result.fa = a.fa * b.fa;
                result.ch = a.ch * b.fa - b.ch * a.fa;
                break;
            case '*':
                result.fa = a.fa * b.fa;
                result.ch = a.ch * b.ch;
                break;
            case '/':
                result.fa = a.fa * b.ch;
                result.ch = a.ch * b.fa;
                break;
        }

        operNum[++operNumTop] = result;
    }

    // 获取运算符优先级
    static int getPriority(char c) {
        switch (c) {
            case '+':
            case '-':
                return 1;
            case '*':
            case '/':
                return 2;
            default:
                return 0;
        }
    }

    // 求表达式结果
    static String getResult(String s) {
        // 操作数的字符缓存容器
        StringBuilder numStr = new StringBuilder();

        int i = 0;
        while (i < s.length()) {
            char c = s.charAt(i);

            // 遇到数字字符
            if (Character.isDigit(c)) {
                // 则将该数字所在操作数的剩余数字字符一次性探索完
                int j = 0;
                while (Character.isDigit(c)) {
                    numStr.append(c);
                    if (i + 1 >= s.length()) break;
                    c = s.charAt(++i);
                }
                // 探索完后，将操作数缓存容器中记录的字符，变为分数后，压入操作数栈
                operNum[++operNumTop] = new Fractions();
                operNum[operNumTop].fa = 1;
                operNum[operNumTop].ch = Integer.parseInt(numStr.toString());
                numStr.setLength(0); // 清空StringBuilder
            }

            // 遇到运算符
            if (c == '+' || c == '-' || c == '*' || c == '/') {
                // 只要栈顶运算符的优先级 >= 当前运算符，就需要不停出栈运算
                while (operSignTop >= 0 && operSign[operSignTop] != '(' &&
                        getPriority(c) <= getPriority(operSign[operSignTop])) {
                    calc();
                }
                operSign[++operSignTop] = c;
            } else if (c == ')') {
                // 遇到')', 需要将操作符栈中靠近栈顶的'('后面的运算都出栈做了
                while (operSign[operSignTop] != '(') {
                    calc();
                }
                // 最后将')'对应的'('出栈
                operSignTop--;
            } else if (c == '(') {
                // 遇到'('，则直接压倒操作符栈
                operSign[++operSignTop] = c;
            }

            i++;
        }

        // operNum栈中还有2个以上的数，则还需要进行运算
        while (operNumTop > 0) {
            calc();
        }

        // operNum栈中只剩一个数时，该数就是表达式结果
        Fractions result = operNum[operNumTop--];

        // 如果结果的分母为0（除数为0），则不合法
        if (result.fa == 0) {
            return "ERROR";
        }

        // 求分子、分母的最大公约数，并进行约分，求得最简格式的分子，分母
        int k = getMaxCommonDivisor(result.fa, result.ch);
        result.fa /= k;
        result.ch /= k;

        // 求计算结果的符号，这里用乘法是为了避免 分母小，分子大，除法结果为0的情况，这样会丢失符号信息
        String sign = (result.fa > 0 && result.ch < 0) || (result.fa < 0 && result.ch > 0) ? "-" : "";

        StringBuilder finalResult = new StringBuilder();

        int fa = Math.abs(result.fa);
        int ch = Math.abs(result.ch);

        if (fa == 1) {
            // 如果分母为1，则直接输出分子
            finalResult.append(sign).append(ch);
        } else {
            // 如果分母不为1，则输出 分子 / 分母
            finalResult.append(sign).append(ch).append('/').append(fa);
        }

        return finalResult.toString();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter the expression: ");
        String expression = scanner.nextLine();

        System.out.println(getResult(expression));
    }
}