RPN: thuật toán, phương pháp và ví dụ

RPN khi đã hình thành cơ sở của một lập trình viên máy tính trên thế giới. Hôm nay nó không phải là quá nổi tiếng. Vì vậy, minh họa truyện tranh, miêu tả một "đảo ngược" cuộn xúc xích Ba Lan bên ngoài, vẫn có thể bị hiểu lầm bởi một số lập trình viên có kiến thức. Không phải là rất tốt giải thích các trò đùa, nhưng trong trường hợp này nó sẽ hoàn toàn hợp lý.

ghi vào

Tất cả các lập trình viên, và hầu hết các sinh viên đã quen thuộc với việc sử dụng các nhà khai thác. Ví dụ, các giá trị biểu thức x + tổng kết cho các biến x và y dấu cộng đã qua sử dụng. Ít nổi tiếng là một thực tế rằng đây là vay mượn từ ký hiệu toán học, được gọi là ký hiệu ghi vào, trên thực tế, là một vấn đề lớn đối với các máy. Toán tử này nhận như là đầu vào hai giá trị được ghi ở bên trái và phải. Trong lập trình ký hiệu sử dụng tùy chọn với các hoạt động dấu hiệu. Ví dụ, x + y có thể được viết như một chức năng của lần (x, y), trong đó trình biên dịch và cuối cùng chuyển đổi ký hiệu ghi vào. Tuy nhiên, mọi người đều biết toán học là quá tốt không sử dụng biểu thức số học, hình thành nên một loại mini-ngôn ngữ nội bộ trong hầu hết các ngôn ngữ lập trình.

dịch công thức

Ngôn ngữ lập trình Fortran thực sự thành công đầu tiên đã trở nên chủ yếu là do các biểu thức số học (tức là công thức ..) Nó chuyển đổi (broadcast) trong mã, vì thế mà tên của nó - Formula dịch. Trước đó, họ đã phải viết, ví dụ, gấp theo hình thức chức năng (và nhân (b, c)). Trong bài toán COBOL thực hiện công thức chuyển đổi tự động được coi là rất khó khăn bởi vì các lập trình viên phải viết những thứ như Add A đến B Mutliply By C.

Điều gì là sai với ghi vào?

Vấn đề là, rằng các nhà khai thác có tính chất như ưu tiên và associativity. Bởi vì điều này, định nghĩa về chức năng ghi vào trở thành nhiệm vụ không tầm thường. Ví dụ, nhân có độ ưu tiên cao hơn cộng thêm hoặc trừ, có nghĩa là biểu thức 2 + 3 * 4 không bằng tổng của 2 và 3, nhân với 4, vì nó sẽ là trong việc thực hiện các nhà khai thác từ trái sang phải. Trong thực tế, nhân 3 bằng 4 và thêm 2. Ví dụ này minh họa rằng tính toán của biểu thức trung tố thường đòi hỏi một sự thay đổi theo thứ tự của các nhà khai thác và toán hạng. Bên cạnh đó, nó là cần thiết để sử dụng niềng răng nhìn ký hiệu rõ ràng hơn. Ví dụ, (2 + 3) * (4 + 5) không thể được viết mà không cần dấu ngoặc đơn, bởi vì 2 + 3 * 4 + 5 có nghĩa là bạn cần phải nhân 3 bằng 4 và thêm 2 và 5.

Thứ tự mà bạn muốn tính các nhà khai thác đòi hỏi một nhớ lâu. Bởi vì điều này, sinh viên bắt đầu học số học, thường có được kết quả sai, ngay cả khi hoạt động thực tế được thực hiện một cách chính xác. Nó là cần thiết để dạy thứ tự của báo cáo hành động của tim. Thứ nhất, hành động phải được thực hiện trong ngoặc đơn, sau đó nhân và chia, và cuối cùng cộng và trừ. Nhưng có một cách khác để viết biểu thức toán học như ký hiệu ghi vào chỉ là một trong những khả năng "ngôn ngữ nhỏ" có thể được thêm vào nhiều hơn nữa.

ký hiệu tiền tố và hậu tố

Hai trong số các lựa chọn thay thế nổi tiếng nhất là để ghi lại các nhà điều hành trước hoặc sau toán hạng của nó. Họ được gọi là các tiền tố và hậu tố ký hiệu. Logic học Yan Lukasevich phát minh ra đầu tiên vào năm 1920. Ông sống ở Ba Lan, do đó kỷ lục được gọi là Ba Lan. Postfix phiên bản, tương ứng, mang tên là Reverse Polish Notation (ARF). Sự khác biệt duy nhất giữa hai phương pháp này là sự chỉ đạo, trong đó để đọc hồ sơ này (từ trái sang phải hoặc phải sang trái), vì vậy nó cũng đủ để xem xét một cách chi tiết chỉ có một trong số họ. Nhà điều hành OPN được viết sau khi toán hạng của nó. Như vậy, khái niệm AB + đại diện cho một ví dụ RPN cho A + B.

Không giới hạn số toán hạng

Ưu điểm trực tiếp của ký hiệu là nó tóm tắt các toán tử n-adic và ký hiệu ghi vào thực sự là chỉ hoạt động với hai toán hạng, t. E. Are vốn chỉ thích hợp cho các hoạt động nhị phân. Ví dụ, ABC @ là biểu Ba Lan ngược lại sử dụng nhãn hiệu bộ ba đó là giá trị lớn nhất của A, B và C. Trong trường hợp này các nhà điều hành hoạt động ở bên trái của ba toán hạng riêng của mình và tương ứng với một chức năng gọi @ (A, B, C). Nếu bạn cố gắng để viết biểu tượng @ như ghi vào, chẳng hạn như A @ BC hoặc một cái gì đó như thế, nó trở nên rõ ràng rằng nó chỉ đơn giản không hoạt động.

Các ưu tiên theo lệnh

RPN có lợi thế khác trong đó ưu tiên hàng đầu của các nhà khai thác có thể được đại diện bởi các thứ tự xuất hiện của họ. Đồng thời không bao giờ cần niềng răng, mặc dù họ có thể được bao gồm như là nhân vật hoạt động để thuận lợi cho việc chuyển đổi từ ký hiệu ghi vào. Ví dụ, AB + C * - rõ ràng tương đương (A + B) * C, vì vậy nhân không thể được tính đến việc bổ sung thực hiện, mang đến cho một toán hạng thứ hai cho phép nhân. Đó là, nếu tính toán AB + C * bởi một nhà điều hành tại một thời điểm, chúng tôi nhận AB + C * -> (AB +) * C -> (A + B) * C.

thuật toán tính

Nhà điều hành OPN trông giống như một hàm mang theo như các đối số hai giá trị ghi trên trái của cô. Bên cạnh đó, nó là một ký hiệu tự nhiên để sử dụng trong ngôn ngữ lập trình, như cách tính của nó tương ứng với các hoạt động ngăn xếp và nhu cầu phân tích cú pháp được loại bỏ. Ví dụ, sét trong biểu thức 5 + 6 * 7 sẽ xuất hiện như một 5, 6, 7 *, +, và nó có thể được tính toán đơn giản bằng cách quét từ trái sang phải và viết các giá trị trong một chồng. Bất cứ khi nào một dấu hiệu phổ biến của hoạt động, bởi các yếu tố trên 2 của bộ nhớ máy tính được lựa chọn, các nhà điều hành được sử dụng và kết quả trả về vào bộ nhớ. Khi kết quả cuối cùng của biểu thức tính toán sẽ được ở phía trên cùng của ngăn xếp.

Ví dụ:

• S = () 5, 6, 7, *, + 5 đặt trên stack.
• S = (5) 6, 7, *, + 6 đặt trên stack.
• S = (5, 6), 7 * 7 + đặt ngăn xếp.
• S = (5, 6, 7), * 2 + chọn giá trị từ ngăn xếp, sử dụng * và đặt kết quả trong ngăn xếp.
• S = (5, 6 * 7) = (5, 42) + 2 giá trị được chọn từ ngăn xếp, để áp dụng + và đặt kết quả trong ngăn xếp.
• S = (5 + 42) = (47) tính được hoàn thành, kết quả được lưu trữ trong phía trên cùng của ngăn xếp.

Thuật toán này có thể được kiểm tra RPN nhiều lần, nhưng mỗi lần nó sẽ làm việc, bất kể độ phức tạp của biểu thức số học.

OPN và ngăn xếp được liên kết chặt chẽ. Ví dụ này cho thấy làm thế nào để sử dụng bộ nhớ để tính giá trị của các ký hiệu Ba Lan ngược lại. Ít rõ ràng là bạn có thể sử dụng ngăn xếp, chuyển đổi biểu ghi vào tiêu chuẩn trong suy thận cấp tính.

Ví dụ về các ngôn ngữ lập trình

Pascal RPN nhận ra như thế này (cho thấy một phần của chương trình).

Để đọc những con số và các nhà khai thác trong chu trình gọi là thủ tục, trong đó xác định xem số hoặc ký hiệu hoạt động thẻ. Trong trường hợp đầu tiên, giá trị được lưu trữ trong ngăn xếp, và lần thứ hai của hai số ngăn xếp trên hành động tương ứng được thực hiện và kết quả được lưu trữ.

toktype: = num;

đọc (s);

nếu c trong [ '+', '-', '*', '/'] sau đó bắt đầu

nếu eoln thì cn: = '' khác đọc (cn);

nếu cn = '' rồi

trường hợp của một

'+': Toktype: = thêm; '-': toktype: = sub;

'*': Toktype: = mul; '/': Toktype: = div

chấm dứt

khác bắt đầu

nếu a = '-' sau đó sgn: = -1 khác lỗi: = c <> '+';

với: = cn

chấm dứt

kết thúc;

if (không lỗi) và (toktype = num) sau đó getnumber;

nếu toktype <> num sau đó bắt đầu

y = pop; x: = pop;

nếu không phải lỗi sau đó

trường hợp toktype của

thêm: z: = x + y; phụ: z: = x-y; mul: z: = x * y; div: z: = x / y

chấm dứt

push (z);

RPN C-thi (hiển thị một phần của chương trình):

for (s = strtok (s, w); s; s = strtok (0, w)) {

a = strtod (s, & e);

if (e> s) push (a);

#define rpnop (x) printf ( "% c:", * s), b = pop (), a = pop (), push (x)

else if (* s == '+') rpnop (a + b);

else if (* s == '-') rpnop (a - b);

else if (* s == '*') rpnop (a * b);

else if (* s == '/') rpnop (a / b);

rpnop #undef

}

triển khai phần cứng

Trong những ngày đó, khi công nghệ máy tính đã rất đắt tiền, người ta nghĩ một ý tưởng tốt để buộc mọi người sử dụng hãm tăng. Năm 1960-tệ., Như bây giờ, nó đã có thể mua máy tính, mà làm việc trong ký hiệu Ba Lan ngược lại. Để thêm 2 và 3 trong số họ phải nhập 2, sau đó 3, và bấm "cộng với" nút. Thoạt nhìn, các toán hạng đầu vào cho các nhà điều hành có vẻ phức tạp và khó nhớ, nhưng sau một thời gian một số là nghiện cách nghĩ này và không thể hiểu tại sao những người khác nhấn mạnh vào ghi vào ngu ngốc, đó là quá phức tạp và do đó bị hạn chế.

Công ty Burroughs thậm chí xây dựng một máy tính lớn, mà không có ký ức khác, ngoại trừ chồng. Điều duy nhất mà làm cho máy tính - áp dụng các thuật toán và phương pháp RPN vào stack trung ương. Tất cả các hoạt động kinh doanh được coi là nhà khai thác hãm, áp dụng cho các giá trị n trên. Ví dụ, nhóm nghiên cứu đã lấy Địa chỉ Return từ phía trên cùng của ngăn xếp, và vân vân. D. Các kiến trúc của một máy như vậy là đơn giản, nhưng không đủ nhanh để cạnh tranh với các kiến trúc phổ biến hơn. Nhiều, tuy nhiên, vẫn còn hối tiếc thực tế là một phương pháp đơn giản và thanh lịch như vậy để tính toán nơi mỗi chương trình là một biểu hiện của OPN, tìm thấy sự tiếp nối của nó.

Một thời gian máy tính với RPN là phổ biến, và một số người vẫn cho họ thích. Bên cạnh đó, họ đã phát triển một chồng theo định hướng ngôn ngữ, chẳng hạn như Forth. Hôm nay nó rất ít được sử dụng, nhưng vẫn hoài cổ từ những người dùng cũ của mình.

Vì vậy, những câu nói đùa ý nghĩa về xúc xích Xếp Ba Lan là gì?

Nếu chúng ta giả định rằng các nhà điều hành của xúc xích, các ký hiệu ghi vào, nó phải là trong cuộn như trong xúc xích truyền thống. Các RPN tọa lạc ngay tại hai nửa được therebetween sẵn sàng sau khi tính toán. Bây giờ đến phần khó khăn - mù tạt. Cô đã là trên xúc xích, t. E. Đã tính như một nhà điều hành unary. Người ta tin rằng mù tạt cũng nên được hiển thị như uncalculated và do đó cần được chuyển đến phía bên phải của xúc xích ... Nhưng có thể, điều này sẽ đòi hỏi chồng quá lớn của ...