Trang chủ » Thuật toán Ký pháp Ba Lan (Prefix/Postfix)
Thuật toán

Thuật toán Ký pháp Ba Lan (Prefix/Postfix)

cplusplus

Xin chào mọi người!

Vừa qua mình đang phải sử dụng phao cứu sinh để vượt qua cơn lũ “deadline” đang tràn về, thật sự thì rất mệt mỏi khi deadline cứ dồn dập vào. Riết mà mình nhìn lịch để bàn có tô đỏ mà cứ tưởng deadline mới xuất hiện :v Thành thử ra mình ít viết bài mới trên blog. Mong các bạn thông cảm!

Tiện thể thì ở Sài Gòn mấy ngày nay trời cứ lành lạnh, tay cứ tê cóng thế nào ấy nên gõ phím chẳng được 🙁 Bạn nữ nào giúp mình vượt qua mùa đông giá rét này với :v

Không lan man nữa, mình xin trở lại vấn đề 😀 dạo chơi vậy đủ rồi.

Chắc các bạn từ đó giờ cũng rất hay gặp những biểu thức dạng như 5^2+3.2*(8-4/10 – log(5))-cos(pi/2) chứ? Rất hay xuất hiện trên các dòng máy tính Casio đấy! Vậy đã bao giờ bạn tự nghĩ rằng, nó thực hiện phép tính như thế nào chưa?

Bản thân mình ngày trước từng nghĩ, nhập vào 1 string rồi duyệt từ đầu đến chân, thấy phép tính nào có độ ưu tiên cao hơn thì mình tính nó, xong ghi đè kết quả lại, cứ tiếp tục như vậy đến khi ra con số cuối cùng. Tất nhiên đó là cách phổ thông khi mình viết tay, còn máy tính thì lại rất khó hiểu. Vì vậy nên cách đó của mình ngày trước không khả thi, cho đến khi mình biết được Ký pháp Ba Lan (hay còn gọi là Ký pháp Tiền tố – prefix notation).

1. Khái niệm

Jan Łukasiewicz (21/12/1878 – 13/2/1956)

Ký pháp Ba Lan được nhà toán học Jan Lukasiewicz đề xuất vào năm 1920. Đây là thuật toán biểu diễn biểu thức bằng cách đặt các toán tử lên phía trước (ví dụ như a + b sẽ thành + a b). Đây được gọi là Biểu thức tiền tố (Prefix). Khác hẳn với biểu thức thông thường ta được học (Biểu thức trung tố – infix), Prefix loại bỏ hoàn toàn các dấu ngoặc ( ), giảm bớt được độ phiền nhiễu của thứ tự các phép toán.

Trái ngược lại với Prefix Biểu thức hậu tố (Postfix). Nếu Prefix biểu diễn toán tử phía trước các toán hạng, thì Postfix sẽ biểu diễn đằng sau (a + b  thành a b +). Postfix được nhà khoa học máy tính Charles Hamblin phát minh vào năm 1950, trước đó sử dụng tên gọi là RPN (Reverse Polish Notation).

Để hiểu rõ hơn về ký pháp Ba Lan, ta có thể sử dụng cây nhị phân để biểu diễn phép tính sau: a + 3*(b – c) – 5/d

Cây nhị phân biểu thức
Cây nhị phân biểu thức

2. Chuẩn bị

Việc biểu diễn biểu thức Infix bằng cây nhị phân tương đối phức tạp, nên mình sẽ hướng dẫn bằng Stack, vì nó dễ cài đặt (dành cho dân mới học như mình mà 😛 ).

Đầu tiên, ta cần phải xác định rõ là toán tử nào sẽ có độ ưu tiên cao hơn. Do có rất nhiều loại toán tử (^, sqrt, !, +, -, *, /, %, sin, cos, log, ln,…) nên ở bài viết này mình sẽ dùng 4 toán tử thông dụng là +, -, *, /, những toán tử khác các bạn có thể nâng cấp thêm 😀

int getPriority(string ope)
{
  // Ta có thể set quyền cao hơn ở đây. VD như if (ope == "^") return 3;
  if (ope == "*" || ope == "/") return 2;
  else if (ope == "+" || ope == "-") return 1;
  else return 0;
}

Kế tiếp, mình sẽ loại bỏ những khoảng trắng thừa trong chuỗi, gọi đây là hàm “Chuẩn hoá”:

void Normalization(string& exp)
{
  for (int i = 0; i < exp.length(); i++)
  {
    if (exp[i] == ' ') exp = exp.erase(i, 1); // Xoá 1 kí tự khoảng trắng 
  }

  // Ngoài ra, ta có thể sử dụng hàm này để xoá các kí tự trắng
  // Đây gọi là Erase-remove idiom, mình không dịch tiếng Việt bởi vì nó rất củ chuối :v
  // Kĩ thuật này sẽ dồn tất cả các khoảng trắng về sau, và sau đó xoá chúng
  // Muốn sử dụng ta cần phải include thư viện <algorithm>
  exp.erase(remove(exp.begin(), exp.end(), " "), exp.end());
}

Cuối cùng, ta cần chuẩn bị 1 hàm để phân biệt toán tử, toán hạng và cặp ngoặc ( ):

int isOperator(string ope)
{
  if (getPriority(ope) == 0)
  {
    if (ope != "(" && ope != ")") return 0;
    else return 1;
  }
  return 2;
}

Công việc chuẩn bị đã hoàn tất! Đến đây ta có thể sử dụng các hàm trên để biểu diễn thuật toán được rồi đấy 😀

3. Biểu diễn

Ở bài viết này, mình chỉ biểu diễn về Postfix, các bạn có thể từ đó nghĩ thêm về Prefix. Kèm theo là mình sẽ sử dụng mảng vector như là 1 stack kiêm luôn mảng để lưu trữ output.

Thuật toán như sau:

Ta cho vòng lặp chạy hết chuỗi:

  • Nếu là số hạng, ta Push vào mảng Output
  • Nếu là toán tử:
    • Thực viện vòng lặp kiểm tra, nếu ở đỉnh Stack là toán tử, mà nó có độ ưu tiên lớn hơn hoặc bằng toán tử hiện tại thì ta lấy toán tử đó ra (Pop) khỏi mảng Stack và Push vào mảng Output.
    • Push toán tử hiện tại vào mảng Stack.
  • Nếu là dấu “(“: ta Push vào mảng Stack
  • Nếu là dấu “)”: Pop các phần tử trong Stack và add vào mảng Output cho đến khi gặp dấu “(” (tất nhiên cũng phải Pop thằng “(” 😀 ).

Hoàn tất vòng lặp, nếu vẫn còn phần tử trong Stack thì ta lần lượt Pop các phần tử đó trong mảng Stack và Push vào Output.

Nói thì có vẻ khó hiểu nhỉ, ta cùng xét ví dụ này:

Chuyển đổi biểu thức 5.5/2 + 3*(4/8 – 2) sang Postfix

Chuyển đổi biểu thức sang Postfix
Chuyển đổi biểu thức sang Postfix

Từ đây, ta có thể viết code được rồi đấy 😀

vector<string> ConvertToPostfix(string exp)
{
  vector<string> Stack;
  vector<string> Output;
  // Do có những toán hạng lớn hơn 10, hoặc số thập phân => Có nhiều hơn 1 ký tự
  // Ta cần phải add toàn bộ các kí tự số đó vào chuỗi number
  string number = "";
  for (int i = 0; i < exp.length(); i++) 
  { 
    string s(1, exp[i]); // Convert kiểu char => string, dễ thao tác
    if (isOperator(s) == 0) number += s;
    else
    {
      // Push toán hạng vào Output
      if (number.length() > 0)
      {
        Output.push_back(number);
        number = "";
      }
      if (isOperator(s) == 1)
      {
        if (s == "(") Stack.push_back("(");
        else if (s == ")")
        {
          string pop = Stack.pop_back();
          // Nhớ là nên Pop cả dấu "(" ra nhé!
          while (pop != "(")
          {
            Output.push_back(pop);
            pop = Stack.pop_back();
          }
        }
      }
      else
      {
        while (!Stack.empty() && getPriority(Stack.back()) >= getPriority(s))
          Output.push_back(Stack.pop_back());
        Stack.push_back(s);
      }
    }
  }
  // Trường hợp còn sót lại toán hạng cuối cùng
  if (number.length() > 0)
  {
    Output.push_back(number);
    number = "";
  }
  while (!Stack.empty()) Output.push_back(Stack.pop_back());
  return Output;
}

Vậy là ta đã hoàn thành việc chuyển biểu thức Infix sang Postfix rồi đấy 😀

4. Tính toán biểu thức Prefix/Postfix

Ta đã chuyển đổi biểu thức Infix sang Prefix/Postfix, nhưng mục đích của ta là tính toán kết quả của 1 biểu thức thì phải làm sao? Tất nhiên khi chuyển đổi sang Prefix/Postfix thì việc tính toán trở nên đơn giản hơn khi còn là Infix rồi 😀

Thuật toán này khá đơn giản nên chỉ dành cho các toán tử 2 ngôi, các bạn có thể tự mở rộng lên cho toán tử 1 ngôi nhé!

Ta duyệt vòng lặp trong mảng Input:

  • Nếu gặp toán hạng: Pop khỏi mảng Input và Push vào Stack
  • Nếu gặp toán tử: Pop 2 toán hạng khỏi mảng Stack, tính toán dựa theo toán tử, và Push lại vào Stack

Kết thúc vòng lặp, phần tử duy nhất trong Stack chính là kết quả cuối cùng

Ta cùng xét ví dụ trên nhé:

Chuyển đổi mảng Postfix 5.5 2 / 3 4 8 / 2 – * +

Tính toán mảng Postfix
Tính toán mảng Postfix
float Calc(vector<string> Input)
{
  vector<string> Stack;
  for (int i = 0; i < Input.size(); i++)
  {
    if (isOperator(Input[i]) == 0) Stack.push_back(Input[i]);
    else
    {
      // Do ta cần quan tâm đến thứ tự các toán hạng
      // Nên ta phải Pop vế sau trước, sau đó vế trước mới Pop sau
      float b = stof(Stack.pop_back());
      float a = stof(Stack.pop_back());
      if (Input[i] == "+") Stack.push_back(a + b);
      else if (Input[i] == "-") Stack.push_back(a - b);
      else if (Input[i] == "*") Stack.push_back(a * b);
      else if (Input[i] == "/") Stack.push_back(a / b);
    }
  }
  return stof(Stack.pop_back());
}

Thật đơn giản phải không nào? Hi vọng sau bài viết này, các bạn có thể tự mình viết 1 phần mềm Calculator “xịn” áp dụng Ký pháp Ba Lan này.

Trên đây là bài hướng dẫn về Thuật toán Ký pháp Ba Lan, cảm ơn các bạn đã chú ý theo dõi. Hẹn gặp lại ở những bài viết sau!

About the author

Võ Hoài Sơn

Tính tình bất định
Chọc vào là bịnh
Rất yêu lập trình
Luôn code hết mình
Mình hiện đang là sinh viên của trường ĐH Khoa học tự nhiên TPHCM. Bản thân rất thích code, kiêm luôn cả mần thơ nên thường hơi hâm hâm dở dở. Ngoài ra chém gió, chém chuối, chém trái cây các kiểu cũng là sở trường của mình. Rất mong được làm quen với các bạn :D

1 Comment