Trong các hệ thống phần mềm doanh nghiệp xử lý biểu thức logic hoặc chính sách phân quyền phức tạp, làm thế nào để sử dụng cấu trúc dữ liệu Stack nhằm chuyển đổi biểu thức trung tố (Infix Expression) sang biểu thức hậu tố (Postfix Expression) và đánh giá giá trị của chúng một cách hiệu quả?

Question

Accepted Answer

Bản chất vấn đề
Trong các hệ thống Enterprise, đặc biệt là các hệ thống Quản lý Quy tắc Kinh doanh (Business Rules Engine) hay phân quyền dựa trên thuộc tính (Attribute-Based Access Control), các điều kiện phức tạp thường được biểu diễn dưới dạng biểu thức toán học hoặc logic trung tố (Infix). Tuy nhiên, máy tính xử lý biểu thức hậu tố (Postfix - RPN) hiệu quả hơn rất nhiều vì không cần quan tâm đến độ ưu tiên của toán tử hay dấu ngoặc.
Giải pháp sử dụng Stack
Để giải quyết bài toán này, chúng ta cần sử dụng hai thuật toán cốt lõi dựa trên cấu trúc dữ liệu Stack:

Chuyển đổi Infix sang Postfix (Thuật toán Shunting-yard của Edsger Dijkstra):
Duyệt qua từng ký tự của biểu thức trung tố.
Nếu gặp toán hạng (operand), đưa thẳng vào kết quả.
Nếu gặp dấu mở ngoặc '(', đẩy vào Stack.
Nếu gặp dấu đóng ngoặc ')', lấy các phần tử từ Stack ra đưa vào kết quả cho đến khi gặp dấu mở ngoặc '('.
Nếu gặp toán tử (operator), so sánh độ ưu tiên với toán tử ở đỉnh Stack. Nếu toán tử hiện tại có độ ưu tiên thấp hơn hoặc bằng toán tử ở đỉnh Stack, lấy toán tử ở đỉnh Stack ra đưa vào kết quả, sau đó đẩy toán tử hiện tại vào Stack.

Đánh giá biểu thức hậu tố:
Duyệt qua biểu thức hậu tố.
Nếu gặp toán hạng, đẩy giá trị vào Stack.
Nếu gặp toán tử, lấy ra 2 phần tử từ Stack, thực hiện phép toán và đẩy kết quả ngược lại vào Stack.

Ví dụ mã nguồn minh họa (JavaScript/TypeScript)
function getPrecedence(operator) {
    if (operator === '+' || operator === '-') return 1;
    if (operator === '*' || operator === '/') return 2;
    return 0;
}

function infixToPostfix(infixExpression) {
    const stack = [];
    const output = [];
    const tokens = infixExpression.match(/([a-zA-Z0-9]+|[\+\-\*/])/g);

for (const token of tokens) {
        if (!isNaN(token)) {
            output.push(token);
        } else if (token === '(') {
            stack.push(token);
        } else if (token === ')') {
            while (stack.length > 0 && stack[stack.length - 1] !== '(') {
                output.push(stack.pop());
            }
            stack.pop(); // Xoa dau '(' khoi stack
        } else {
            while (
                stack.length > 0 &&
                getPrecedence(stack[stack.length - 1]) >= getPrecedence(token)
            ) {
                output.push(stack.pop());
            }
            stack.push(token);
        }
    }

while (stack.length > 0) {
        output.push(stack.pop());
    }

return output;
}

function evaluatePostfix(postfixTokens) {
    const stack = [];

for (const token of postfixTokens) {
        if (!isNaN(token)) {
            stack.push(Number(token));
        } else {
            const b = stack.pop();
            const a = stack.pop();
            let result = 0;
            switch (token) {
                case '+': result = a + b; break;
                case '-': result = a - b; break;
                case '*': result = a * b; break;
                case '/': result = a / b; break;
            }
            stack.push(result);
        }
    }

return stack.pop();
}
Lưu ý kinh nghiệm thực chiến

Độ phức tạp: Cả hai thuật toán đều có độ phức tạp thời gian là $O(N)$ và độ phức tạp không gian là $O(N)$ với $N$ là số lượng token trong biểu thức.
Xử lý lỗi: Cần validate kỹ các trường hợp biểu thức sai cú pháp (thiếu dấu ngoặc, thừa toán tử, chia cho 0) để tránh ngoại lệ gây sập tiến trình (Crash Process) trên môi trường Production.

Bản chất vấn đề

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi stacks liên quan cùng chủ đề