Editorial for sheight: Chiều cao cây biểu thức RPN

Hiểu bài toán

Bài toán yêu cầu tính chiều cao của cây biểu thức nhị phân được tạo ra từ một biểu thức hậu tố (RPN). Trong biểu thức hậu tố, các toán hạng (ở đây là các ký tự chữ cái) được xếp trước, và phép toán xuất hiện sau khi các toán hạng của nó. Cây biểu thức là một cây nhị phân mà tại mỗi nút lá là toán hạng và mỗi nút trong là phép toán. Chiều cao của cây được định nghĩa là số lượng cạnh dài nhất từ gốc đến một lá. Với biểu thức hậu tố, ta có thể tính chiều cao bằng cách duyệt từ trái sang phải, sử dụng một ngăn xếp (stack): mỗi khi gặp toán hạng, ta đẩy một độ cao cơ sở (ví dụ 0 hoặc 1) vào stack; mỗi khi gặp phép toán, ta lấy hai giá trị đầu tiên từ stack, cộng độ sâu lớn nhất của chúng với 1, và đẩy kết quả trở lại stack. Giá trị cuối cùng còn lại trên stack chính là chiều cao của cây.

Các cách tiếp cận

Cách Giải pháp dùng Stack tính chiều cao trực tiếp

#include <bits/stdc++.h>
using namespace std;

int calculateHeight(string s) {
    stack<int> st;
    for (char c : s) {
        if (isalpha(c)) {
            st.push(1); // Chiều cao của lá là 1
        } else {
            int h1 = st.top(); st.pop();
            int h2 = st.top(); st.pop();
            st.push(max(h1, h2) + 1);
        }
    }
    return st.top();
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while (t--) {
        string s; cin >> s;
        cout << calculateHeight(s) << "\n";
    }
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Cách tiếp cận này mô phỏng quá trình xây dựng cây bằng stack. Mỗi ký tự trong chuỗi được xử lý một lần. Nếu là toán hạng, ta đẩy độ cao của nó (1) vào stack. Nếu là toán tử, ta lấy hai toán hạng đầu tiên từ stack, tính độ cao mới là max(h1, h2) + 1 và đẩy lại. Độ phức tạp thời gian là O(N) với N là độ dài chuỗi. Đây là cách hiệu quả và trực quan nhất.

Cách Giải pháp dùng Stack mô phỏng Node (Cấu trúc dữ liệu phức tạp hơn)

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

typedef struct Node {
    int v;
    struct Node *next;
} Node;

Node *head = NULL;

void push(int v) {
    Node *p = (Node *)malloc(sizeof(Node));
    p->v = v;
    p->next = head;
    head = p;
}

int pop() {
    if (head == NULL) return 0;
    Node *p = head;
    head = head->next;
    int res = p->v;
    free(p);
    return res;
}

int main() {
    int n;
    scanf("%d", &n);
    while (n--) {
        head = NULL;
        char s[5001];
        scanf("%s", s);
        int len = strlen(s);
        for (int i = 0; i < len; i++) {
            if (isalpha(s[i])) {
                push(0); // Dùng 0 làm độ cao cơ sở cho lá
            } else {
                int a = pop();
                int b = pop();
                push((a > b ? a : b) + 1);
            }
        }
        printf("%d\n", head->v);
        // Giải phóng stack (đoạn này thường bị bỏ qua trong code ngắn)
    }
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Đây là biến thể của giải pháp stack sử dụng cấu trúc dữ liệu Linked List thủ công thay vì thư viện chuẩn. Logic tính toán tương tự: độ cao của phép toán là độ cao lớn nhất của hai nhánh con cộng thêm 1. Việc sử dụng head làm stack pointer và malloc/free cho thấy cách tiếp cận cấp phát động thủ công. Tuy nhiên, về bản chất thuật toán vẫn là O(N).

Cách Giải pháp đệ quy (Simulate)

#include <bits/stdc++.h>
using namespace std;

string s;
int idx;

int solve() {
    if (idx >= s.length()) return 0;
    char c = s[idx++];
    if (isalpha(c)) return 1; // Gốc đến lá là 1 cạnh
    int h1 = solve();
    int h2 = solve();
    return max(h1, h2) + 1;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        cin >> s;
        idx = 0;
        cout << solve() << "\n";
    }
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Thay vì dùng stack, ta có thể dùng đệ quy để mô phỏng việc duyệt cây. Hàm solve() đọc ký tự hiện tại. Nếu là toán hạng, trả về 1. Nếu là toán tử, gọi đệ quy cho toán hạng bên trái và bên phải (do tính chất hậu tố, thứ tự này được đảm bảo bởi việc gọi đệ quy), sau đó trả về max(h1, h2) + 1. Độ sâu đệ quy tối đa tương ứng với độ dài biểu thức.

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

Bài học kinh nghiệm

• Biểu thức hậu tố/RPN loại bỏ nhu cầu về dấu ngoặc đơn và quy tắc ưu tiên phép tính, cho phép xử lý tuần tự từ trái sang phải.
• Bài toán tính chiều cao cây có thể quy về bài toán tính toán trên stack: 'Độ cao của phép toán = 1 + max(độ cao nhánh trái, độ cao nhánh phải)'.
• Với mỗi toán hạng, ta coi nó là một cây con có chiều cao 1 (hoặc 0 tùy định nghĩa, nhưng thường là 1 để tính số cạnh).

Lỗi thường gặp

• Lầm tưởng về chiều cao: Chiều cao cây là số cạnh dài nhất từ gốc đến lá, không phải số nút. Do đó, nếu lá có chiều cao là 0, phép toán thân phải cộng thêm 1.
• Xử lý sai thứ tự lấy toán hạng khỏi stack: Trong RPN, toán hạng đầu tiên được lấy ra là toán hạng bên phải của phép toán.
• Quên kiểm tra độ dài chuỗi hoặc xử lý ký tự kết thúc dòng.