Chương 32 - String Parser (Stack, State Machine, Regex)

Bài “string parser” hỏi bạn implement 1 mini-language: calculator, atom formula, lisp, … Pattern chung: (i) Stack cho cấu trúc lồng, (ii) State machine cho parsing token, (iii) Recursive descent cho grammar có nested rule. Bài 8.6 (Decode String) và 2.4 (atoi) đã teaser.

Mục tiêu chương

Sau chương này, bạn sẽ:

• 3 paradigm: stack (nested), FSM (token-level), recursive descent (grammar).
• Bài cốt lõi: Calculator (stack), Number of Atoms (stack of dicts), Valid Number (FSM).
• Regex Matching là DP - đặt vào chương parser vì kết quả parsing.
• Pattern “isdigit + 10*x + int(ch)” để đọc nhiều chữ số.

Khi nào dùng pattern này?

• Đề bài: “Implement Calculator”, “Parse Lisp”, “Validate HTML Tag”, v.v.
• Có grammar rõ ràng - số, toán tử, ngoặc, biểu thức lồng nhau, …
• Yêu cầu đánh giá (eval), kiểm tra hợp lệ (validate), trích xuất hoặc chuẩn hoá chuỗi đầu vào.

3 mẫu thường dùng:

Mẫu	Bài ví dụ
Stack với operator	Basic Calculator I/II
FSM tokens	atoi, Valid Number
Recursive descent	Parse Lisp, Add Operators

Bài tự luyện cuối chương

• LC 224, 227, 772 - Basic Calculator family
• LC 591 - Tag Validator
• LC 736 - Parse Lisp Expression
• LC 1106 - Parsing A Boolean Expression
• LC 726 - Number of Atoms

---

32.1 Basic Calculator II (LC 227)

Đề bài

Cho chuỗi s chứa số, +, -, *, /, dấu cách. Tính giá trị biểu thức. Chia lấy phần nguyên hướng về 0. Không có ngoặc.

Ví dụ

Input:  s = " 3+5 / 2 "
Output: 5
        (3 + (5/2) = 3 + 2 = 5; chia lấy phần nguyên)

Input:  s = " 14-3/2 "
Output: 13
        (14 - (3/2) = 14 - 1 = 13)

Ràng buộc

• 1 <= len(s) <= 3·10^5
• s chứa số nguyên, +, -, *, /, space

Clarifying questions

• Có ngoặc không? → Không (bài này không xử lý ngoặc; LC 224 có).
• Chia số âm? → Truncate towards 0.

Hướng tiếp cận

Stack giữ “term” đang được build. Khi gặp operator mới: - +x → push x. - -x → push -x. - *x → top = top * x. - /x → top = int(top / x).

Cuối: sum stack.

Code Python 3

class Solution:
    def calculate(self, s: str) -> int:
        s += '+'                  # sentinel
        stack: list[int] = []
        num = 0
        op = '+'
        for ch in s:
            if ch.isdigit():
                num = num * 10 + int(ch)
            elif ch in '+-*/':
                if op == '+': stack.append(num)
                elif op == '-': stack.append(-num)
                elif op == '*': stack[-1] *= num
                else: stack[-1] = int(stack[-1] / num)    # truncate to 0
                op = ch
                num = 0
        return sum(stack)

Phân tích độ phức tạp

• Thời gian: O(n).
• Bộ nhớ: O(n) cho stack.

Bình luận

• Trick sentinel +: không phải special-case lần cuối.
• Bẫy chia số âm: -7 // 2 = -4, nhưng cần -3 (truncate to 0) → dùng int(a / b).

Bài tự luyện liên quan

• LC 224 - Basic Calculator (thêm ngoặc).
• LC 772 - Basic Calculator III (cả 2).

---

32.2 Decode String (LC 394) - recap

Đã giải đầy đủ ở Chương 8.6. Pattern stack lồng với (prev_str, k).

Liên hệ với chương này

Đây là gateway cho String Parser - nested structure → stack. Toàn chương 32 mở rộng pattern này: Calculator (operator stack), Number of Atoms (dict stack), Regex (DP table), Valid Number (FSM).

Code Python 3 (recap)

class Solution:
    def decodeString(self, s: str) -> str:
        stack: list[tuple[str, int]] = []
        cur, k = "", 0
        for ch in s:
            if ch.isdigit():
                k = k * 10 + int(ch)
            elif ch == '[':
                stack.append((cur, k))
                cur, k = "", 0
            elif ch == ']':
                prev_str, prev_k = stack.pop()
                cur = prev_str + cur * prev_k
            else:
                cur += ch
        return cur

Phân tích độ phức tạp

• Thời gian: O(N) (N = độ dài output). Bộ nhớ: O(N).

Bài tự luyện liên quan

• LC 726 - Number of Atoms (bài 32.3).

---

32.3 Number of Atoms (LC 726)

Đề bài

Cho công thức hoá học (vd "K4(ON(SO3)2)2"). Trả về dạng chuẩn K4N2O14S4 - alphabetic atomic names + counts.

Ví dụ

Input:  formula = "H2O"
Output: "H2O"

Input:  formula = "Mg(OH)2"
Output: "H2MgO2"
        (Mg×1, O×2, H×2; sort alphabetic; số 1 lược bỏ)

Input:  formula = "K4(ON(SO3)2)2"
Output: "K4N2O14S4"
        (K×4, N×2, O×14, S×4; sort alphabetic)

Ràng buộc

• 1 <= len(formula) <= 1000
• formula hợp lệ

Clarifying questions

• Formula có ngoặc và multiplier không? → Có (theo đề: H2O, Mg(OH)2).
• Atom có thể là single letter (vd H) hoặc 2 letters (vd Mg)? → Có.

Hướng tiếp cận

Stack of dicts. Mỗi ( mở 1 dict mới. Mỗi ) + multiplier → multiply dict và merge vào parent. Mỗi atom name + count → cộng vào dict top.

Code Python 3

from collections import Counter, defaultdict

class Solution:
    def countOfAtoms(self, formula: str) -> str:
        stack: list[dict] = [defaultdict(int)]
        i, n = 0, len(formula)
        while i < n:
            ch = formula[i]
            if ch == '(':
                stack.append(defaultdict(int))
                i += 1
            elif ch == ')':
                i += 1
                j = i
                while j < n and formula[j].isdigit():
                    j += 1
                mult = int(formula[i:j]) if j > i else 1
                i = j
                top = stack.pop()
                for atom, cnt in top.items():
                    stack[-1][atom] += cnt * mult
            else:
                j = i + 1
                while j < n and formula[j].islower():
                    j += 1
                atom = formula[i:j]
                i = j
                k = i
                while k < n and formula[k].isdigit():
                    k += 1
                count = int(formula[i:k]) if k > i else 1
                i = k
                stack[-1][atom] += count
        result = stack[-1]
        return ''.join(
            atom + (str(cnt) if cnt > 1 else '')
            for atom, cnt in sorted(result.items())
        )

Phân tích độ phức tạp

• Thời gian: O(n²) worst (merge dicts).
• Bộ nhớ: O(n).

Bình luận

• Bài Hard tiêu biểu cho parser dạng stack - stack of dict + parse “uppercase + lowercase + digits” theo từng đoạn.

Bài tự luyện liên quan

• LC 736 - Parse Lisp Expression.

---

32.4 Regular Expression Matching (LC 10)

Đề bài

Kiểm tra string s có match pattern p không. p chứa . (match 1 char) và * (match 0+ ký tự trước đó).

Ví dụ

Input:  s = "aa", p = "a*"
Output: True
        (`a*` match 0+ ký tự 'a' → match "aa")

Input:  s = "mississippi", p = "mis*is*p*."
Output: False

Input:  s = "ab", p = ".*"
Output: True
        (`.*` match 0+ ký tự bất kỳ → match "ab")

Ràng buộc

• 1 <= len(s), len(p) <= 20
• s chứa chữ thường
• p chứa chữ thường, ‘.’, ’*’

Clarifying questions

• p rỗng? → Match chỉ khi s rỗng.
• s, p chỉ chứa a-z, ., *? → Theo đề: có.

Hướng tiếp cận

DP 2D. dp[i][j] = s[:i] match p[:j] không.

• p[j-1] là *:
  • 0 lần → dp[i][j-2].
  • 1+ lần (nếu match) → dp[i-1][j].
• p[j-1] là . hoặc ==s[i-1]: dp[i-1][j-1].

Code Python 3

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = True
        for j in range(2, n + 1):
            if p[j - 1] == '*':
                dp[0][j] = dp[0][j - 2]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if p[j - 1] == '*':
                    dp[i][j] = dp[i][j - 2]
                    if p[j - 2] == '.' or p[j - 2] == s[i - 1]:
                        dp[i][j] = dp[i][j] or dp[i - 1][j]
                else:
                    if p[j - 1] == '.' or p[j - 1] == s[i - 1]:
                        dp[i][j] = dp[i - 1][j - 1]
        return dp[m][n]

Phân tích độ phức tạp

• Thời gian: O(m · n). Bộ nhớ: O(m · n).

Bình luận

• Bài DP kinh điển. Cốt lõi: * bao gồm cả 0 lần - đây là điểm khó.

Bài tự luyện liên quan

• LC 44 - Wildcard Matching.

---

32.5 Valid Number (LC 65)

Đề bài

Kiểm tra một chuỗi s có phải là số hợp lệ hay không. Loại số hợp lệ bao gồm: số nguyên, số thập phân, và ký pháp khoa học (scientific notation), ví dụ "2", "-2.5", "3e+10", "-.5".

Ví dụ

Input:  s = "0"             → Output: True
Input:  s = "e"             → Output: False  (chỉ chữ e, không có digit)
Input:  s = "."             → Output: False  (chỉ dấu chấm, không có digit)
Input:  s = "+6e-1"         → Output: True   (số khoa học hợp lệ)

Ràng buộc

• 1 <= len(s) <= 20

Clarifying questions

• Multiple sign (vd ++3)? → Không hợp lệ.
• Số . riêng lẻ? → Không hợp lệ.

Hướng tiếp cận

FSM 9 trạng thái hoặc dùng regex. FSM gọn và dễ giải thích hơn cho phỏng vấn.

Code Python 3 (dùng regex)

import re

class Solution:
    def isNumber(self, s: str) -> bool:
        pattern = r'^[+-]?(\d+\.?\d*|\.\d+)([eE][+-]?\d+)?$'
        return bool(re.match(pattern, s.strip()))

Phân tích độ phức tạp

• Thời gian: O(n) (regex match).
• Bộ nhớ: O(1).

Bình luận

• Regex pattern explained:
  • ^[+-]? - sign tuỳ chọn.
  • (\d+\.?\d*|\.\d+) - 12, 12., 12.3, .3 (integer / decimal).
  • ([eE][+-]?\d+)? - exponent tuỳ chọn.
• Phiên bản FSM cũng đáng học - đây là pattern tiêu biểu cho parser nhanh và dễ chứng minh đúng đắn.

Bài tự luyện liên quan

• LC 8 - String to Integer (atoi).

---

32.6 Integer to English Words (LC 273)

Đề bài

Convert số num (≤ 2³¹-1) sang text tiếng Anh.

Ví dụ

Input:  num = 123
Output: "One Hundred Twenty Three"

Input:  num = 12345
Output: "Twelve Thousand Three Hundred Forty Five"

Input:  num = 0
Output: "Zero"

Ràng buộc

• 0 <= num <= 2^31-1

Clarifying questions

• num = 0? → Trả “Zero”.
• num âm? → Theo đề: 0 ≤ num ≤ 2^31-1.

Hướng tiếp cận

Chia thành nhóm 3 chữ số (units, thousands, millions, billions). Mỗi nhóm 3 có pattern: hundreds + tens-ones.

Code Python 3

class Solution:
    UNDER_20 = ["", "One","Two","Three","Four","Five","Six","Seven","Eight","Nine",
                "Ten","Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen",
                "Seventeen","Eighteen","Nineteen"]
    TENS = ["", "", "Twenty","Thirty","Forty","Fifty","Sixty","Seventy","Eighty","Ninety"]
    THOUSANDS = ["", "Thousand", "Million", "Billion"]

    def numberToWords(self, num: int) -> str:
        if num == 0: return "Zero"

        def under_thousand(n: int) -> str:
            if n == 0: return ""
            if n < 20: return self.UNDER_20[n] + " "
            if n < 100: return self.TENS[n // 10] + " " + under_thousand(n % 10)
            return self.UNDER_20[n // 100] + " Hundred " + under_thousand(n % 100)

        parts = []
        i = 0
        while num > 0:
            if num % 1000 != 0:
                parts.append((under_thousand(num % 1000) + self.THOUSANDS[i]).strip())
            num //= 1000
            i += 1
        return ' '.join(reversed(parts)).strip()

Phân tích độ phức tạp

• Thời gian: O(log n) (chia nhóm nghìn).
• Bộ nhớ: O(log n).

Bình luận

• Bẫy 0: xử lý riêng num == 0 → "Zero".
• Trim space cẩn thận - pattern cộng/strip hay sinh extra space.

Bài tự luyện liên quan

• LC 12 - Integer to Roman.

Tóm tắt chương & Quyết định

Parser taxonomy

Loại	Đặc trưng	Bài
Stack-based	Nested structures (paren, brackets)	LC 224, 394, 726
FSM / state machine	Token tuyến tính, các state rõ ràng	LC 8, 65
Recursive descent	Grammar có cấu trúc đệ quy	LC 736, 770
DP on string	Match với pattern (., *)	LC 10, 44

Valid Number (LC 65) - FSM table

States: 0 start, 1 sign, 2 int, 3 dot_after_int, 4 dot_before_int (require frac), 5 frac, 6 e/E, 7 exp_sign, 8 exp_int, 9 end (whitespace/error). | Trạng thái | digit | +/- | . | e/E | |-|-|-|-|-| | 0 (start) | 2 | 1 | 4 | – | | 1 (sign) | 2 | – | 4 | – | | 2 (int) | 2 | – | 3 | 6 | | 3 (dot after int) | 5 | – | – | 6 | | 4 (dot only) | 5 | – | – | – | | 5 (frac) | 5 | – | – | 6 | | 6 (e) | 8 | 7 | – | – | | 7 (exp sign) | 8 | – | – | – | | 8 (exp int) | 8 | – | – | – |

Accept states: {2, 3, 5, 8}.

Regex Matching (LC 10) - vì sao DP?

• * cho phép 0 hoặc nhiều lần → quyết định không local: chữ * ở p[j] ảnh hưởng nhiều prefix của s.
• dp[i][j] = s[..i] match p[..j]?
• Khi p[j] == '*': thử “dùng 0 lần” dp[i][j-2] hoặc “dùng thêm 1 lần” dp[i-1][j] nếu s[i-1] khớp p[j-1].

Number of Atoms (LC 726) - nested stack trace

"K4(ON(SO3)2)2":

stack = [Counter()]
'K' '4'  → top {K:4}
'('      → push new {}
'O' 'N'  → top {O:1, N:1}
'('      → push
'S' 'O' '3' → top {S:1, O:3}
')' '2'  → pop, multiply by 2: {S:2, O:6} → merge into below {O:1,N:1,S:2,O:7} ⇒ {O:7, N:1, S:2}
')' '2'  → pop, mul 2, merge into base {K:4} → {K:4, O:14, N:2, S:4}

---