RPN: ალგორითმი, მეთოდები და მაგალითები

RPN ერთხელ საფუძვლად დაედო პროგრამისტად მსოფლიოში. დღეს ეს ასე არ არის ცნობილი. აქედან გამომდინარე, კომიკური ილუსტრაცია, რომელიც ასახავს "გადახედოს" პოლონეთის ძეხვი რულონები გარეთ, ჯერ კიდევ შეიძლება არასწორად ზოგიერთი განათლებული პროგრამებში. არ არის ძალიან კარგად ავუხსნათ, ხუმრობა, მაგრამ ამ შემთხვევაში ეს იქნება სრულად გამართლდა.

infix

ყველა პროგრამისტების, და ყველაზე სტუდენტები იცნობს გამოყენების ოპერატორები. მაგალითად, გამოხატვის x + summation ღირებულებების ცვლადები x და y მეორადი პლუს ნიშანი. ნაკლებად ცნობილია ის ფაქტი, რომ ეს არის ნასესხები მათემატიკის notation მოუწოდა infix notation, ფაქტობრივად, არის დიდი პრობლემა მანქანები. ეს ოპერატორი იღებს შეყვანის ორი ღირებულებები აისახება მარცხენა და მარჯვენა. პროგრამირებაში notation გამოიყენება სურვილისამებრ ნიშნებით ოპერაციებში. მაგალითად, x + y შეიძლება ჩაიწეროს როგორც ფუნქცია ჯერ (x, y), რომელშიც შემდგენელი და საბოლოოდ გარდაქმნის infix notation. თუმცა ყველამ იცის, რომ მათემატიკის არის ძალიან კარგი, რომ არ გამოიყენონ არითმეტიკული გამონათქვამები, რომლებიც ერთგვარი შიდა მინი ენის თითქმის ყველა პროგრამირების ენაზე.

ფორმულა თარჯიმანი

პირველი ნამდვილად წარმატებული Fortran პროგრამირების ენა გახდა იმდენად დიდწილად იმიტომ, რომ არითმეტიკული გამოხატვის (ანუ ფორმულა ..) მოაქცია (გადაცემული) კოდი, აქედან გამომდინარე, სახელწოდება - ფორმულა თარგმანი. მანამდე, უნდა ყოფილიყო, მაგალითად, დაკეცილი სახით ფუნქციების (და გამრავლების (ბ, გ)). In COBOL პრობლემა განხორციელების ავტომატური კონვერტაცია ფორმულა ითვლებოდა ძალიან რთულია, რადგან პროგრამისტები დაწერა რამ, როგორიცაა რჩეულებში A To B Mutliply By C.

რა არის ცუდი infix?

პრობლემა ის არის, რომ ოპერატორების აქვს ისეთი თვისებები, როგორც უპირატესი და associativity. ამის გამო, განმარტებას infix ფუნქცია ხდება არასამთავრობო ტრივიალური ამოცანაა. მაგალითად, გამრავლება აქვს უმაღლესი პრეცენდენტის, ვიდრე დამატებით ან გამოკლება, რაც იმას ნიშნავს, რომ გამოხატვის 2 + 3 * 4 არ არის ტოლი თანხა 2 და 3 გამრავლებული 4, ეს იქნება შესრულება ოპერატორები მარცხნიდან მარჯვნივ. ფაქტობრივად, გამრავლების 3 4 და დაამატოთ 2. ეს მაგალითი გვიჩვენებს, რომ გაანგარიშება infix გამოხატვის ხშირად მოითხოვს ცვლილება ბრძანებით ოპერატორები და operands. გარდა ამისა, აუცილებელია გამოიყენოთ აფრთხილებს, რომ უფრო ნათელი notation. მაგალითად, (2 + 3) * (4 + 5) არ შეიძლება წერილობითი გარეშე ფრჩხილებში, იმიტომ, რომ 2 + 3 * 4 + 5 იმას ნიშნავს, რომ თქვენ უნდა გავამრავლოთ 3 4 და დაამატოთ 2 და 5.

იმისათვის, რომელშიც გსურთ გამოთვალოს ოპერატორების მოითხოვს ხანგრძლივი მახსოვს. ამის გამო, სტუდენტებს, რომლებიც უნდა ვისწავლოთ არითმეტიკული, ხშირად არასწორი შედეგები, მაშინაც კი, თუ ფაქტობრივი ოპერაცია ხორციელდება სწორად. აუცილებელია ასწავლოს, რათა მოქმედების განცხადებები ზეპირად. პირველი, ქმედება უნდა განხორციელდეს ფრჩხილებში, მაშინ გამრავლება და გაყოფა, და საბოლოოდ ამისა და გამოკლება. მაგრამ არსებობს კიდევ ერთი გზა წერის მათემატიკური გამონათქვამები როგორც infix notation მხოლოდ ერთ-ერთი შესაძლო "მცირე ენების", რომელიც შეიძლება დაემატოს სხვა.

პრეფიქსი და postfix notation

ორი ყველაზე ცნობილი ალტერნატიული ჩაწერა ოპერატორი და შემდეგ მისი operands. ისინი ცნობილია როგორც პრეფიქსი და postfix notation. Logician Yan Lukasevich გამოიგონა პირველი 1920 წელს. ცხოვრობდა პოლონეთი, ამიტომ რეკორდული ეწოდება პოლონური. Postfix ვერსია, შესაბამისად, მოუწოდა უკუ პოლონეთის Notation (ARF). ერთადერთი განსხვავება ამ ორ მეთოდების მიმართულებით, რომელიც წაკითხვის ჩანაწერი (მარცხნიდან მარჯვნივ და მარჯვნიდან მარცხნივ), ასე რომ საკმარისია განიხილოს დეტალურად მხოლოდ ერთი მათგანი. OPN ოპერატორი წერილობითი შემდეგ მისი operands. ამდენად, გამოხატვის AB + წარმოადგენს მაგალითად RPN for A + B.

შეუზღუდავი რაოდენობის operands

დაუყოვნებლივ გამოიყენა notation არის ის, რომ უყრის n-Adic ოპერატორი და infix notation მართლაც მუშაობს მხოლოდ ორი operands, ტ. E. არსებითად განკუთვნილია მხოლოდ ორობითი ოპერაციებში. მაგალითად, ABC @ საპირისპირო Polish გამოხატვის გამოყენებით სამების ნიშანს, რომელიც მაქსიმალური ღირებულების A, B და C. ამ შემთხვევაში ოპერატორი მოქმედებს მარცხენა სამი operand თავად და შეესაბამება ფუნქცია ზარის @ (A, B, C). თუ თქვენ ცდილობენ წერენ @ სიმბოლო, როგორც infix, როგორიცაა A @ BC ან რამე მაგდაგვარს, ნათელი ხდება, რომ ეს უბრალოდ არ მუშაობს.

პრიორიტეტი ეძლევა ბრძანებით

RPN კიდევ ერთი უპირატესობა, რომ პრიორიტეტი ოპერატორები შეიძლება წარმოდგენილი, რათა მათი გამოჩენა. ამავე დროს, არ უნდა braces, მიუხედავად იმისა, რომ ისინი შეიძლება იყოს ჩართული, როგორც სიმბოლო ოპერაციები, რათა ხელი შეუწყოს კონვერტაციის infix notation. მაგალითად, AB + C * - ცალსახა ექვივალენტი (A + B) * C, ასე რომ გამრავლება არ შეიძლება გათვლილი სანამ დამატებით შესრულებული, რომელიც აძლევს მეორე operand გამრავლება. რომ არის, თუ გათვლილი AB + C * ერთი ოპერატორი დროს, მივიღებთ AB + C * -> (AB +) * C -> (A + B) * C.

გაანგარიშების ალგორითმი

OPN ოპერატორი გამოიყურება იგივე როგორც ფუნქცია, რომელიც იღებს არგუმენტები ორი ღირებულებები დაწერილი მისი მარცხენა. გარდა ამისა, ეს არის ბუნებრივი notation გამოყენების პროგრამირების ენების, როგორც ფორმით, მისი გაანგარიშების შეესაბამება დასტის ოპერაციების და საჭიროება parsing აღმოფხვრილი. მაგალითად, arrester გამოხატვის 5 + 6 + 7 გამოჩნდება, როგორც 5, 6, 7 *, + და ეს შეიძლება იყოს გათვლილი უბრალოდ სკანირება მარცხნიდან მარჯვნივ და დაწეროთ ღირებულებების დასტის. როდესაც საერთო ნიშანია ოპერაციის მიერ შერჩეული ზედა ელემენტის 2 კომპიუტერის მეხსიერებაში, ოპერატორი გამოიყენება და შედეგად დაბრუნდა მეხსიერება. როდესაც ბოლოს შედეგი გაანგარიშება გამოხატვის იქნება ზევით Stack.

მაგალითად:

• S = () 5, 6, 7, *, + 5 განთავსებული Stack.
• S = (5), 6, 7, *, + 6 განთავსებული Stack.
• S = (5, 6), 7 * 7 + მოთავსება Stack.
• S = (5, 6, 7) * 2 + აირჩიოს ფასეულობათა დასტის, გამოყენების * და განათავსებს შედეგი Stack.
• S = (5, 6 * 7) = (5, 42) + 2 ღირებულებების შერჩეული დასტის, მიმართოს + და ამით შედეგად Stack.
• S = (5 + 42) = (47) გაანგარიშება დასრულდა, შედეგი ინახება ზედა დასტის.

ეს ალგორითმი შეიძლება შემოწმდეს RPN არაერთხელ, მაგრამ ყოველ ჯერზე, რომ იგი იმუშავებს, არ აქვს მნიშვნელობა რამდენად რთული არითმეტიკული გამოხატვის.

OPN და stacks მჭიდროდ უკავშირდება. ეს მაგალითი აჩვენებს, თუ როგორ გამოიყენოთ მეხსიერების გამოვთვალოთ ღირებულება საპირისპირო Polish notation. ნაკლებად აშკარა არის, რომ თქვენ შეგიძლიათ გამოიყენოთ დასტის, კონვერტაცია სტანდარტული infix გამოხატვის მწვავე უკმარისობა.

მაგალითები პროგრამირების ენები

Pascal RPN მიხვდა, როგორც ეს (აჩვენებს პროგრამის ნაწილი).

წაკითხვის ნომრები და ოპერატორები ციკლი ეწოდება პროცედურა, რომელიც განსაზღვრავს, თუ რამდენად ნიშნად ნომერი, ან ნიშანი ოპერაცია. პირველ შემთხვევაში, ღირებულება ინახება დასტის, და მეორე ზედა ორი დასტის ნომრები შესაბამისი ქმედება ხორციელდება და შედეგად ინახება.

toktype: = num;

წაკითხვის (s);

თუ გ [ '+' ', -' '*', '/'] შემდეგ დაიწყება

თუ eoln მაშინ cn = '' სხვა წაიკითხა (CN);

თუ cn = '' შემდეგ

შემთხვევაში

'+': Toktype: = რჩეულებში; "-": toktype: = sub;

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

ბოლოს

სხვა დაიწყება

თუ a = "-" მაშინ sgn: = -1 სხვა შეცდომა: = c <> '+';

ერთად: = cn

ბოლოს

დასრულდება;

თუ (არ შეცდომა) და (toktype = num), მაშინ getnumber;

თუ toktype <> num შემდეგ დაიწყება

y = pop; x = pop;

თუ არა შეცდომა მაშინ

შემთხვევაში toktype of

რჩეულებში: z = x + y; კატეგორია: z = x-y; mul: z = x * y; div: z = x / y

ბოლოს

ბიძგი (z);

C-განხორციელების RPN (ნაჩვენები პროგრამის ნაწილი):

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

a = strtod (s, და ელექტრონული);

თუ (e> s) ბიძგი (ა);

განსაზღვრავს rpnop (x) printf ( "% c:", * s), b = პოპ (), a = პოპ (), ბიძგი (x)

სხვაგან თუ (* s == '+') rpnop (a + b);

სხვაგან თუ (* s == "-") rpnop (ა - ბ);

სხვაგან თუ (* s == '*') rpnop (a * ბ);

სხვაგან თუ (* s == '/') rpnop (a / b);

#undef rpnop

}

ტექნიკის შესრულება

იმ დღეებში, როდესაც კომპიუტერული ტექნიკის იყო ძალიან ძვირი, მას ეგონა, კარგი იდეა, რათა აიძულოს ადამიანი გამოიყენოთ მცლელი. 1960-იან წლებში., როგორც ახლა, შესაძლებელი იყო, რომ შეიძინოთ კალკულატორები, რომელიც მუშაობს საპირისპირო Polish notation. იმისათვის, რომ დაამატოთ 2 და 3 მათგანი უნდა შეიყვანოთ 2, 3, და დააჭირეთ "პლუს" ღილაკს. ერთი შეხედვით, შეყვანის operands ოპერატორი, როგორც ჩანს, რთული და რთული უნდა გვახსოვდეს, მაგრამ მას შემდეგ, ხოლო ზოგი ნარკომანი ამ აზროვნებას და ვერ გამიგია, რატომ სხვები ამტკიცებენ, სულელური infix, რომელიც იმდენად რთული და ასე არის შეზღუდული.

Burroughs კომპანია კი აშენდა mainframe, რომელიც არ ჰქონდა სხვა მეხსიერების, გარდა Stack. ერთადერთი რამ, რაც მანქანა - გამოყენებული ალგორითმები და მეთოდები RPN ცენტრალური Stack. ყველა მისი ოპერაციების იყო მიჩნეული arresters ოპერატორები, რომელიც ვრცელდება ზედა n ღირებულებებს. მაგალითად, გავიდა დაბრუნება მისამართი ზემოდან დასტის, და ასე შემდეგ. D. არქიტექტურა ასეთი მანქანა იყო მარტივი, მაგრამ არ არის საკმარისი სწრაფი კონკურენციას უფრო გავრცელებული არქიტექტორები. ბევრი, თუმცა, მაინც ვნანობ, რომ ასეთი მარტივი და ელეგანტური მიდგომა computing ყველა პროგრამა გამოხატულება იყო OPN, ნაპოვნია მისი გაგრძელება.

ერთ დროს კალკულატორები რომელზეც RPN იყო პოპულარული, და ზოგიერთი ადამიანი მაინც მივცეთ უპირატესობა. გარდა ამისა, მათ მიერ შემუშავებული დასტის ორიენტირებული ენებზე, როგორიცაა სხვა. დღეს ეს არის პატარა გამოყენებული, მაგრამ მაინც ნოსტალგიური მისი ყოფილი მომხმარებლებს.

ასე რომ, რას ნიშნავს ხუმრობები Reverse Polish ძეხვი?

თუ დავუშვებთ, რომ ოპერატორი ძეხვი, რომ infix notation, ეს უნდა იყოს ფარგლებში roll როგორც ჩვეულებრივი ცხელი ძაღლი. RPN მდებარეობს მარჯვენა ორ ნაწილად მოემზადოს therebetween გაანგარიშების შემდეგ. ახლა მოდის რთული ნაწილი - მდოგვი. მან უკვე ძეხვი, ტ. E. უკვე გამოითვლება როგორც unary ოპერატორი. ითვლება, რომ მდოგვი უნდა იყოს ნაჩვენები, როგორც uncalculated და ამიტომ უნდა გადავიდა მარჯვნივ ძეხვი ... მაგრამ ეს შესაძლებელია, ეს დასჭირდება ძალიან დიდი დასტის ...