Algorithm – Cải thiện thuật toán chuyển đổi và tính giá trị biểu thức số học

Trong một số bài viết trước đây tôi đã giới thiệu thuật toán chuyển đối biểu thức toán học giữa các dạng trung tố (infix), tiền tố (prefix) và hậu tố (postfix). Đồng thời tôi cũng trình bày phương pháp tính giá trị của các biểu thức này cũng như xây dựng cây biểu thức trực quan qua chương trình Y2 – Expression Converter Demo. Tuy nhiên thuật toán này chỉ mới hỗ trợ các toán tử hai ngôi (binary operation), trong bài viết này tôi sẽ mở rộng để thuật toán làm việc với các toán tử một ngôi (unary operation).

Algorithm – Tính giá trị của biểu thức tiền tố và hậu tố

Việc tính giá trị của một biểu thức toán học ở dạng trung tố trong máy tính thông thường sẽ được chuyển sang dạng ký pháp nghịch đảo Ba Lan (hậu tố) để việc tính toán được dễ dàng. Bạn có thể xem lại thuật toán chuyển đổi từ trung tố sang hậu tố trong bài viết “Chuyển biểu thức trung tố sang tiền tố và hậu tố bằng Stack” của tôi, và tải project mẫu tại đây. Trong bài viết này, tôi sẽ trình bày phương pháp tính giá trị của một biểu thức tiền tố và hậu tố bằng Stack. Bạn có thể sẽ cần áp dụng kiến thức dưới đây nếu muốn tạo ra một cây biểu thức (expression tree) từ các dạng biểu thức này.

Algorithm – Chuyển biểu thức trung tố sang tiền tố và hậu tố bằng Stack

Các biểu thức đại số được sử dụng hằng ngày đều được biểu diễn dưới dạng trung tố (infix). Cách biểu diễn này rất dễ hiểu với con người vì hầu hết các toán tử (+, -, *, /) đều là toán tử hai ngôi và chúng phân cách giữa hai toán hạng với nhau. Tuy nhiên đối với máy tính, để tính được giá trị của một biểu thức đại số theo dạng này không đơn giản như ta vẫn làm. Để khắc phục điều đó, máy tính cần chuyển cách biểu diễn các biểu thức đại số từ trung tố sang một dạng khác là tiền tố hoặc hậu tố. Trong bài này tôi sẽ giới thiệu kĩ thuật để giúp máy tính thực hiện điều này thông qua ngôn ngữ minh họa C#.

Y2 – Expression Converter Demo (v1.2)- Chuyển biểu thức trung tố sang tiền tố và hậu tố

Đây là một phần mềm Demo minh họa việc chuyển đổi giữa biểu thức trung tố sang biếu thức tiền tố (ký pháp Ba Lan) và hậu tố (ký pháp nghịch đảo Ba Lan). Các loại biểu thức này còn được gọi tắt với tên tiếng Anh là infix (trung tố), prefix (tiền tố) và postfix (hậu tố) dựa vào vị trí của toán tử so với các toán hạng trong biểu thức.