Netencyclo tiếng Việt, The wikipedia mirror - The biggest multilingual encyclopedia : Kí pháp Ba Lan

- Kí pháp Ba Lan -

Kí pháp Ba Lan :

Kí pháp Ba Lan

Bách khoa toàn thư mở Wikipedia

Bước tới: menu, tìm kiếm

Kí pháp Ba lan (tiếng Anh: Polish notation) là một cách viết một biểu thức đại số rất thuận lợi cho việc thực hiện các phép toán. Đặc điểm cơ bản của cách viết này là không cần dùng đến các dấu ngoặc và luôn thực hiện từ trái sang phải.

Mục lục

[sửa] Tác giả

Jan Łukasiewicz

Kí pháp Ba Lan do nhà logic toán Jan Łukasiewicz đề xuất khoảng năm 1920. Jan Łukasiewicz là một nhà toán học người Ba Lan. Ông sinh ra ở Lwów, Galicia (nay là Lviv, Ukraina). Lĩnh vực nghiên cứu chính của ông là logic toán.

[sửa] Các phương pháp biểu diễn phép toán hai ngôi

Một phép toán hai ngôi trên tập hợp X là một ánh xạ f: X×X →X cho (a,b)\mapstof(a,b)\inA. Ánh xạ f khi đó thường được ký hiệu bởi *, được gọi là toán tử, các phần tử a, b được gọi là các hạng tử (còn gọi là toán hạng).

Khi viết biểu thức biểu diên phép toán đó ta có thể đặt ký hiệu toán tử ở trước, sau hoặc giữa các toán hạng (là biến hoặc hằng). Thông thường trong các biểu thức đại và số học, ta viết kí hiệu phép toán giữa hai hạng tử. Ví dụ : a +b, a * b, ... Khi một biểu thức có nhiều phép toán, ta dùng các cặp dấu ngoặc "(", ")" và thứ tự ưu tiên các phép toán để chỉ rõ thứ tự thực hiện các phép toán. (Các phép toán đều quy về phép toán 2 ngôi.)

Ta cũng có thể viết hai hạng tử trước và kí hiệu toán tử sau. Chẳng hạn:

a + b viết là a b +, a*b viết là a b *

Cũng có thể viết toán tử trước, hai toán hạng sau. Chẳng hạn:

a + b viết là + a b, a * b viết là * a b

[sửa] Cây biểu diễn biểu thức

Dùng cây biểu diễn biểu thức có thể thấy rõ trình tự tính toán biểu thức.

Ví dụ:

a*(b+c)-d^5

Được thực hiện theo sơ đồ biểu diễn bởi cây nhi phân sau

                -     
              /   \         
             *     ^
           /  \   / \
          a   +  d   5
             /  \
            b    c

Ta mô tả quá trình đọc, ghi nhận giá trị và thực hiện phép tính, giống như quá trình duyệt cây biểu thức theo thứ tự giữa như sau:

  1. Đọc và ghi nhận giá trị biến a(con trái)
  2. Đọc và ghi nhận loại phép toán * (con trái)
  3. Đọc giá trị biến b (con trái)
  4. Đọc và ghi nhận loại phép toán + (con phải)
  5. Đọc giá trị biến c (con phải) thực hiện phép cộng b+c=x và ghi nhận kết quả x,thực hiện phép nhân a*x = y và ghi nhận kết quả y
  6. Đọc và ghi nhận phép toán -
  7. Đọc giá trị biến d
  8. Đọc và ghi nhận phép toán ^
  9. Đọc giá trị 5 và thực hiện phép lũy thừa z=d^5, thực hiện phép trừ k=y-z

Để đơn giản ta giả sử các phép toán đều là hai ngôi. Khi đó cây biểu thức là cây nhị phân đầy đủ. Quy tắc thực hiện phép toán trên cây như sau:

Viết tuần tự các đỉnh duyệt theo thứ tự giữa thì ta có dãy
                -                    -
              /   \                /   \  
             *     ^              +     ^ 
           /  \   / \            / \   / \
          a   +  d   5         *   c  d   5    
             /  \             /  \
            b    c           a    b
a * b + c - 4 * d ^ 5 (1)

Theo cách này, mỗi khi duyệt một đỉnh

  1. Nếu là lá bên trái (biến hoặc hằng) thì ghi nhận giá trị của biến
  2. Nếu là toán tử thì lưu dạng của toán tử
  3. Nếu là con phải và lá thực hiện phép tính theo toán tử đã lưu ở đỉnh cha giữa các giá trị đã lưu tại con phải và giá trị mới đọc tại con trái, ghi kết quả vào đỉnh cha.
Thứ tự duyệt các đỉnh khi đó sẽ là:
a b c + * d 5 ^ - (2)

Khi duyệt theo thứ tự sau, việc thực hiện phép tính tiến hành theo quy tắc:

Mỗi khi thăm một đỉnh thì:

  1. Nếu là lá thì ghi nhận giá trị của biến
  2. Nếu là đỉnh trong thì thực hiện toán tử ghi ở đỉnh này vào các giá trị ghi ở hai đỉnh con, ghi kết quả vào chính đỉnh này.

Với dãy (1) nếu không dùng đến dấu ngoặc, có thể có hai cây biểu thức khác nhau cho cùng một dãy đỉnh khi duyệt thứ tự giữa. Còn với dãy (2) cùng với lưu ý rằng các biến và hằng luôn được biểu diễn bằng các lá, các toán tử luôn biểu diễn bởi các nút trong, từ mỗi dãy dạng (2) ta luôn dựng lại được cây biểu thức duy nhất theo giải thuật sau: Khi độ dài dãy lớn hơn 1, duyệt từ bên trái sang, nếu gặp một phần tử là toán tử, thì lấy hai phần tử đứng trước nó ra khỏi dãy chuyển thành hai con của phần tử ấy (theo đúng thứ tự). Vì thế biểu thức viết bởi dãy (2) là hoàn toàn xác định.

[sửa] Tính giá trị của biểu thức viết dưới dạng phép toán sau

(x+y)*z

[sửa] Chuyển đổi từ biểu thức bình thường sang kí pháp Ba Lan

Việc tính giá trị một biểu thức viết dưới dạng phép toán sau rất thuận tiện như trên, tuy nhiên, theo thói quen thông thường, việc nhập biểu thức đó vào lại không dễ, người ta thường nhập vào một công thức dưới dạng thông thường (phép toán giữa) rồi dùng chương trình chuyển đổi nó sang dạng phép toán sau. Chúng ta hãy xét biểu thức trong ví dụ trên

Q=a*(b+c)-d^5

Kí hiệu biểu thức ghi dưới dạng phép toán sau là P. Trong quá trình chuyển đổi ta dùng một stack S để lưu các phần tử trong P chưa sử dụng đến. Khi đọc từ trái sang phải biểu thức Q la lần lượt có:

  1. Đọc và ghi nhận giá trị a, ghi giá trị a vào P. Vậy P = "a".
  2. Đọc toán tử "*". Đưa toán tử này vào stack S: S = "*"
  3. Đọc dấu ngoặc mở "(", đưa dấu ngoặc này vào stack: S = "*(".
  4. Đọc hạng tử b, đưa b vào P: P= "a b"
  5. Đọc toán tử "+", đặt "+" vào stack: S ="*(+"
  6. Đọc hạng tử "c", đưa c vào cuối P: P="a b c"
  7. Đọc dấu ngoặc đóng ")". Lần lượt lấy các toán tử ở cuối stack ra khỏi stack đặt vào cuối P cho đến khi gặp dấu ngoặc mở "(" trong stack thì giải phóng nó: S= "*"; P="a b c +"
  8. Đọc toán tử "-". Cuối stack S có toán tử "*" có mức ưu tiên lớn hơn toán tử "-", ta lấy toán tử "*" ra khỏi stack, đặt vào cuối P, đặt toán tử "-" vào stack: S="-"; P=" a b c + * "
  9. Đọc hạng tử d, đưa d vào cuối P. P="a b c + * d"
  10. Đọc toán tử "^", đưa toán tử "^" vào cuối stack: S="-^"
  11. Đọc hằng số 5, đưa 5 vào cuối P: P="a b c + * d 5"
  12. Đã đọc hết biểu thức Q, lần lượt lấy các phần tử cuối trong stack đặt vào P cho đến hết. P="q b c + * d 5 ^ -".


 Bài này còn sơ khai.
Mời bạn góp sức viết thêm để bài được hoàn thiện hơn. Xem phần trợ giúp về cách sửa bài.

Kí pháp Ba Lan - theo chủ đề

Kí pháp Ba Lan - Dự án liên quan

© 2008 Netencyclo - Netencyclo Trang Chính - Chính sách về sự riêng tư - Lời phủ nhận - Program Policies
Netencyclo, the Wikipedia mirror : the biggest multilingual free-content encyclopedia on the Internet. Sửa đổi lần cuối lúc 00:11, ngày 14 tháng 5 năm 2007. Tất cả nội dung được phép sử dụng theo Giấy phép Tài liệu Tự do GNU (xem Quyền tác giả để biết thêm chi tiết). All Wikipedia content is licensed under the GNU Free Documentation License (see details). Content on this web site is provided for informational purposes only. We accept no responsibility for any loss, injury or inconvenience sustained by any person resulting from information published on this site. We encourage you to verify any critical information with the relevant authorities.