# [592. Fraction Addition and Subtraction](https://leetcode.com/problems/fraction-addition-and-subtraction/description/)

# 1. Tóm tắt đề bài

Cho một xâu `expression` biểu diễn một biểu thức toán học bao gồm các phép cộng trừ phân số.

Hãy trả về kết quả của biểu thức toán học đó dưới dạng một xâu [phân số tối giản](https://vi.wikipedia.org/wiki/Ph%C3%A2n_s%E1%BB%91_t%E1%BB%91i_gi%E1%BA%A3n). Nếu kết quả là số nguyên `a`, trả về dưới dạng `a/1`.

### Giới hạn

- `expression` chỉ chứa các ký tự `+`, `-`, dấu `/` và các chữ số từ `0` đến `9`.
- Mỗi phân số trong `expression` được biểu diễn dưới dạng `±a/b`. Nếu phân số đầu tiên trong biểu thức là dương, dấu `+` sẽ không xuất hiện trước phân số đó. Điều này áp dụng tương tự với xâu phân số kết quả trả về.
- Các phân số trong `expression` đều là **phân số tối giản và hợp lệ**. Nếu có số nguyên `a` trong biểu thức thì nó được viết dưới dạng `a/1`.
- Khoảng giá trị của tử số và mẫu số của các phân số trong `expression` là $[1, 10]$
- Tử số và mẫu số của **phân số kết quả** chắc chắn không vượt quá số nguyên 32-bit.

# 2. Quan sát

**Độ phức tạp dự tính: $O(n)$**

Dưới đây là toàn bộ các quy tắc cần biết để giải bài toán này:

- $\frac{a}{b} \pm \frac{c}{d} = \frac{a \times d \pm c \times b}{b \times d}$
- Với $c = \gcd(a, b) \Rightarrow a = cd, b = ce$, ta có: $\frac{a}{b} = \frac{cd}{ce} = \frac{d}{e}$ (phân số tối giản)
- Thuật toán Euclid (đệ quy) để tìm ước chung lớn nhất giữa hai số nguyên $a$ và $b$:
- Nếu $b = 0$, trả về $a$
- Ngược lại, trả về $\gcd(b, a\ \mathrm{mod}\ b)$

Tuy nhiên, bài này lấy đầu vào là xâu, nên ta cần phải parse xâu đó thành các phân số rồi thực hiện phép cộng trừ. Có hai cách để làm điều này:

- **Thủ công**: Ta thêm dấu cách giữa từng phân số và sử dụng hàm `split()` để tách xâu thành một mảng các phân số có định dạng như phần [Giới hạn](#Giới-hạn).
- **Regular Expression (Regex)**: Sử dụng biểu thức chính quy như sau: `"[+-]?\d+"` để tìm tất cả các phân số trong chuỗi.

# 3. Lời giải chi tiết

- Parse xâu đầu vào thành các phân số, sử dụng một trong hai cách ở trên.
- Khởi tạo hai biến `a = 0` và `b = 1` lần lượt là tử số và mẫu số của phân số kết quả.
- Duyệt qua từng phân số trong mảng:
- Tách phân số thành tử số `c` và mẫu số `d`.
- Cập nhật `a` và `b` và tối giản phân số theo quy tắc ở trên.
- Trả về phân số kết quả dưới dạng xâu `a/b`.

### Code mẫu (Python)

#### Cách 1: Manual Parsing

class Solution:
    def fractionAddition(self, expression: str) -> str:
        fracs = expression.replace("+", " +").replace("-", " -").split()
        a, b = 0, 1

        for frac in fracs:
            c, d = map(int, frac.split("/"))
            a = a * d + b * c
            b = b * d
            common = math.gcd(a, b)
            a //= common
            b //= common

        return str(a) + "/" + str(b)

[**LeetCode Submission**](https://leetcode.com/submissions/detail/1365329080/)

#### Cách 2: Regular Expression (Regex)

class Solution:
    def fractionAddition(self, expression: str) -> str:
        nums = list(map(int, re.findall(r"[+-]?\d+", expression)))
        a, b = 0, 1

        for c, d in zip(nums[::2], nums[1::2]):
            a = a * d + b * c
            b = b * d
            common = math.gcd(a, b)
            a //= common
            b //= common

        return str(a) + "/" + str(b)

[**LeetCode Submission**](https://leetcode.com/submissions/detail/1365327889/)

### Độ phức tạp thuật toán

Thời gian: $O(n)$

Bộ nhớ mở rộng: $O(1)$

# 4. Kết luận & Gợi ý mở rộng

Một bài kết hợp giữa toán và xử lý xâu khá hay.