Khi nhắc đến việc phân tích và tính toán biểu thức, nhiều người thường nghĩ ngay đến phương pháp táiursive descent — một kỹ thuật mạnh mẽ dùng để xây dựng cây cú pháp trừu tượng (AST). Tuy nhiên, cách tiếp cận này đòi hỏi kiến thức sâu về lý thuyết ngôn ngữ hình thức và kỹ năng lập trình cao, khiến nó trở nên khó tiếp cận với người mới bắt đầu.
Thay vào đó, bài viết này giới thiệu một phương pháp đơn giản và hiệu quả hơn: sử dụng biểu thức hậu tố (Reverse Polish Notation – RPN), nơi toán tử được đặt sau các toán hạng. Với RPN, việc tính toán biểu thức có thể thực hiện dễ dàng chỉ bằng thao tác trên ngăn xếp (stack), giúp code rõ ràng, dễ hiểu và tối ưu về hiệu năng.
Bắt đầu từ những khái niệm cơ bản, bạn sẽ từng bước triển khai một trình tính biểu thức số học hoàn toàn bằng C#, không phụ thuộc thư viện bên ngoài.
1. Mở đầu: Xây dựng máy tính đơn giản
Một trong những bài tập đầu tiên mà lập trình viên thường thực hành là xây dựng máy tính trạng thái đơn giản, ví dụ như:
- Nhập số 1
- Nhập dấu +
- Nhập số 2
- Hiển thị kết quả: 3
Nếu bạn có thể làm được điều này, đồng nghĩa với việc bạn đã nắm được các khái niệm cơ bản như: đổi loại dữ liệu (string → number), sử dụng toán tử cơ bản và xử lý đầu vào/đầu ra.
Bây giờ, hãy thử mở rộng hệ thống để xử lý biểu thức phức tạp hơn như:
Một chương trình thực sự hữu ích cần hỗ trợ biểu thức động — ví dụ: người dùng có thể nhập công thức tùy chỉnh cho tính toán thống kê, báo cáo, hoặc cấu hình logic trong ứng dụng linh hoạt mà không cần biên dịch lại. Đây là lúc trình phân tích và tính toán biểu thức trở nên thiết yếu.
2. Các dạng biểu thức phổ biến
2.1 Biểu thức trung tố (Infix)
Đây là dạng biểu thức chúng ta thường gặp trong toán học: toán tử nằm giữa hai toán hạng, ví dụ: (4 + 2) * 3. Trong dạng này, thứ tự ưu tiên và dấu ngoặc rất quan trọng để xác định kết quả chính xác.
2.2 Biểu thức hậu tố (Postfix / RPN)
Đối với biểu thức RPN, toán tử luôn đặt sau toán hạng. Chẳng hạn, biểu thức `(4+2)*3` trong dạng trung tố tương ứng với `4 2 + 3 *` trong dạng hậu tố.
Cách tính RPN rất trực quan: duyệt từ trái sang phải, đẩy số vào ngăn xếp; khi gặp toán tử, lấy hai số ở đỉnh ngăn xếp để thực hiện phép toán, sau đó đặt kết quả trở lại ngăn xếp. Quá trình lặp lại cho đến khi hết biểu thức — số duy nhất còn lại chính là kết quả.
Ví dụ: Tính `3 4 2 + *`
- Nhận '3' → push 3
- Nhận '4' → push 4
- Nhận '2' → push 2
- Nhận '+' → pop 2, pop 4 → tính 4+2=6 → push 6
- Nhận '*' → pop 6, pop 3 → tính 3*6=18 → push 18
- Kết thúc: kết quả là 18
Vì không cần dấu ngoặc hay kiểm tra ưu tiên trong quá trình thực thi, RPN rất phù hợp với máy tính cài đặt đơn giản.
3. Chuyển đổi từ biểu thức trung tố sang hậu tố
3.1 Xác định thứ tự ưu tiên và số lượng toán hạng
Để chuyển đổi đúng, đầu tiên ta phải định nghĩa rõ các toán tử và độ ưu tiên tương ứng. Giả sử chương trình hỗ trợ các toán tử sau:
+ -: bậc 1* /: bậc 2^: bậc 3 (lũy thừa)( ): dấu ngoặc có ưu tiên đặc biệt — không nằm trong hàng ưu tiên thông thường.
Định nghĩa bằng C#:
private static readonly Dictionary OperatorPrecedence = new()
{
['+'] = 1,
['-'] = 1,
['*'] = 2,
['/'] = 2,
['^'] = 3,
['('] = 0,
[')'] = 0
}; Các hàm helper cần thiết:
private static bool IsOperator(char c) =>
OperatorPrecedence.ContainsKey(c);
private static int GetPrecedence(char op) =>
OperatorPrecedence[op];3.2 Thuật toán Shunting-yard (biến đổi trung tố → hậu tố)
Thuật toán này sử dụng một ngăn xếp để giữ toán tử tạm thời, và một danh sách có thứ tự để tích lũy đầu ra dạng hậu tố.
Các bước xử lý ký tự trong biểu thức:
- Nếu là chữ số → thêm vào danh sách kết quả.
- Nếu là `(` → đẩy vào ngăn xếp toán tử.
- Nếu là `)` → liên tục pop các toán tử ra danh sách kết quả cho đến khi gặp `(` (và loại bỏ cả `(`).
- Nếu là toán tử (ví dụ `+`, `*`, ...) → so sánh ưu tiên với toán tử ở đỉnh ngăn xếp:
- Pop các toán tử có độ ưu tiên ≥ toán tử hiện tại vào danh sách kết quả.
- Đẩy toán tử hiện tại vào ngăn xếp.
Sau khi duyệt hết biểu thức, nếu ngăn xếp còn toán tử → pop hết vào danh sách kết quả.
3.3 Minh họa chuyển đổi `(4+2)*3`
| Ký tự xử lý | Ngăn xếp (top → bottom) | Danh sách đầu ra | |-------------|--------------------------|----------------------| | ( | ( | | | 4 | ( | 4 | | + | ( + | 4 | | 2 | ( + | 4 2 | | ) | | 4 2 + | | * | * | 4 2 + | | 3 | * | 4 2 + 3 | | {/*end*/} | | 4 2 + 3 * |Kết quả: ["4", "2", "+", "3", "*"]
3.4 Mã nguồn chuyển đổi
public static List<string> ConvertToPostfix(string expr)
{
var ops = new Stack<char>();
var result = new List<string>();
foreach (var ch in expr.Where(c => !char.IsWhiteSpace(c)))
{
if (char.IsDigit(ch))
{
result.Add(ch.ToString());
}
else if (ch == '(')
{
ops.Push(ch);
}
else if (ch == ')')
{
while (ops.Count > 0 && ops.Peek() != '(')
result.Add(ops.Pop().ToString());
if (ops.Count > 0) ops.Pop(); // pop '('
}
else if (IsOperator(ch))
{
while (ops.Count > 0 && ops.Peek() != '(' &&
GetPrecedence(ops.Peek()) >= GetPrecedence(ch))
result.Add(ops.Pop().ToString());
ops.Push(ch);
}
}
while (ops.Count > 0)
result.Add(ops.Pop().ToString());
return result;
}4. Tính toán biểu thức hậu tố
Với biểu thức ở dạng hậu tố, việc tính toán trở nên cực kỳ đơn giản:
- Khai báo ngăn xếp kiểu số (double)
- Duyệt từng phần tử:
- Nếu là số → push vào ngăn xếp
- Nếu là toán tử → pop 2 phần tử trên cùng phép toán, sau đó push kết quả trở lại
- Phần tử cuối cùng ở ngăn xếp chính là kết quả biểu thức
Phần xử lý chính:
public static double EvaluateRPN(IList<string> postfix)
{
var stack = new Stack<double>();
foreach (var token in postfix)
{
if (double.TryParse(token, out var val))
{
stack.Push(val);
}
else
{
double rhs = stack.Pop();
double lhs = stack.Pop();
double res;
switch (token)
{
case "+": res = lhs + rhs; break;
case "-": res = lhs - rhs; break;
case "*": res = lhs * rhs; break;
case "/":
if (Math.Abs(rhs) < 1e-12)
throw new DivideByZeroException("Lỗi chia cho số 0");
res = lhs / rhs;
break;
case "^": res = Math.Pow(lhs, rhs); break;
default:
throw new InvalidOperationException($"Toán tử không hợp lệ: {token}");
}
stack.Push(res);
}
}
if (stack.Count != 1)
throw new InvalidOperationException("Biểu thức không hợp lệ");
return stack.Pop();
}4.1 Ví dụ thực tế
Với biểu thức: 1+2*(5-1)/(2+3)^2
- Chuyển sang hậu tố:
["1","2","5","1","-","*","2","3","+","2","^","/","+"] - Kết quả sau tính:
~1.32
Hệ thống hoàn chỉnh có thể mở rộng để: - Xử lý chuỗi biểu thức phức tạp - Hỗ trợ biến và hàm tùy chỉnh (nâng cao hơn RPN cơ bản) - Tích hợp vào hệ thống cấu hình động, plugin...
Đây là nền tảng vững chắc để học về trình phân tích cú pháp sâu hơn sau này — bước chuyển quan trọng từ lập trình cơ bản sang xây dựng ngôn ngữ nội bộ (DSL).