592.分数加减运算

链接：592.分数加减运算
难度：Medium
标签：数学、字符串、模拟
简介：给定一个表示分数加减运算的字符串 expression ，你需要返回一个字符串形式的计算结果。 。

题解 1 - cpp

• 编辑时间：2022-07-27
• 内存消耗：5.9MB
• 编程语言：cpp
• 解法介绍：解析字符串后通分约分。

class Solution {
   public:
    typedef pair<int, int> node;
    string fractionAddition(string expression) {
        char op = '+';
        node ans = make_pair(0, 1);
        for (int i = 0; i < expression.size(); i++) {
            int end = i;
            string tmp = "";
            while (end < expression.size() && !is_op(expression, end))
                tmp += expression[end++];
            i = end;
            op_node(ans, to_node(tmp), op);
            op = expression[i];
        }
        return to_string(ans.first) + "/" + to_string(ans.second);
    }
    bool is_op(string &expression, int idx) {
        if (idx == 0 || idx == expression.size() - 1) return false;
        if (expression[idx] != '+' && expression[idx] != '-') return false;
        if (!isdigit(expression[idx - 1])) return false;
        return true;
    }
    node to_node(string &str) {
        node ans = make_pair(0, 0);
        int i = 0, f = 1;
        if (str[0] == '-') f = -1;
        if (str[0] == '+' || str[0] == '-') i++;
        while (str[i] != '/') ans.first = ans.first * 10 + str[i++] - '0';
        i++;
        while (i < str.size()) ans.second = ans.second * 10 + str[i++] - '0';
        ans.first *= f;
        return ans;
    }
    void op_node(node &node1, node node2, char op) {
        format1(node1, node2);
        if (op == '+')
            node1.first += node2.first;
        else
            node1.first -= node2.first;
        format2(node1);
    }
    int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
    int lcm(int a, int b) { return a * b / gcd(a, b); }
    void format1(node &node1, node &node2) {
        if (node1.second != node2.second) {
            int num_lcm = lcm(node1.second, node2.second);
            node1.first *= num_lcm / node1.second;
            node2.first *= num_lcm / node2.second;
            node1.second = node2.second = num_lcm;
        }
    }
    void format2(node &node) {
        int f = 1;
        if (node.first < 0) {
            f = -1;
            node.first *= f;
        }
        int num_gcd = gcd(node.first, node.second);
        if (num_gcd != 1) {
            node.first /= num_gcd;
            node.second /= num_gcd;
        }
        node.first *= f;
    }
};

题解 2 - rust

• 编辑时间：2022-07-27
• 内存消耗：2MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn fraction_addition(expression: String) -> String {
        let expression: Vec<char> = expression.chars().collect();
        let mut op = '+';
        let mut ans = Node::new(0, 1);
        let mut i = 0;
        while i < expression.len() {
            let mut end = i;
            let mut tmp = String::new();
            while end < expression.len() && !Solution::is_op(&expression, end) {
                tmp.push(expression[end]);
                end += 1;
            }
            i = end;
            Solution::op_node(&mut ans, Solution::to_node(&tmp), op);
            if i < expression.len() {
                op = expression[i];
            }
            i += 1;
        }
        ans.to_string()
    }
    fn is_op(expression: &Vec<char>, idx: usize) -> bool {
        if idx == 0 || idx == expression.len() - 1 {
            false
        } else if expression[idx] != '+' && expression[idx] != '-' {
            false
        } else if !expression[idx - 1].is_ascii_digit() {
            false
        } else {
            true
        }
    }
    fn to_node(string: &String) -> Node {
        let string: Vec<char> = string.chars().collect();
        let mut node = Node::new(0, 0);
        let mut i = 0;
        let mut f = 1;
        if string[0] == '-' {
            f = -1;
        }
        if string[0] == '+' || string[0] == '-' {
            i += 1;
        }
        while string[i] != '/' {
            node.first = node.first * 10 + (string[i] as i32 - '0' as i32);
            i += 1;
        }
        i += 1;
        while i < string.len() {
            node.second = node.second * 10 + (string[i] as i32 - '0' as i32);
            i += 1;
        }
        node.first *= f;
        node
    }
    fn op_node(node1: &mut Node, node2: Node, op: char) {
        let mut node2 = node2;
        Solution::format1(node1, &mut node2);
        if op == '+' {
            node1.first += node2.first;
        } else {
            node1.first -= node2.first;
        }
        Solution::format2(node1);
    }
    fn format1(node1: &mut Node, node2: &mut Node) {
        if node1.second != node2.second {
            let lcm = Solution::lcm(node1.second, node2.second);
            node1.first *= lcm / node1.second;
            node2.first *= lcm / node2.second;
            node1.second = lcm;
            node2.second = lcm;
        }
    }
    fn format2(node: &mut Node) {
        let mut f = 1;
        if node.first < 0 {
            f = -1;
            node.first *= f;
        }
        let gcd = Solution::gcd(node.first, node.second);
        if gcd != 1 {
            node.first /= gcd;
            node.second /= gcd;
        }
        node.first *= f;
    }
    fn gcd(a: i32, b: i32) -> i32 {
        if b == 0 {
            a
        } else {
            Solution::gcd(b, a % b)
        }
    }
    fn lcm(a: i32, b: i32) -> i32 {
        a * b / Solution::gcd(a, b)
    }
}
struct Node {
    first: i32,
    second: i32,
}
impl Node {
    fn new(first: i32, second: i32) -> Self {
        Self { first, second }
    }
    fn to_string(&self) -> String {
        format!("{}/{}", self.first, self.second)
    }
}