Hotline: 024.62511017

024.62511081

  Trang chủ   Sản phẩm   Phần mềm Dành cho nhà trường   Phần mềm Hỗ trợ học tập   Kho phần mềm   Liên hệ   Đăng nhập | Đăng ký

Tìm kiếm

School@net
 
Xem bài viết theo các chủ đề hiện có
  • Hỗ trợ khách hàng (474 bài viết)
  • Hoạt động của công ty (527 bài viết)
  • Thông tin khuyến mại (73 bài viết)
  • Sản phẩm mới (216 bài viết)
  • Mô hình & Giải pháp (145 bài viết)
  • IQB và mô hình Ngân hàng đề kiểm tra (116 bài viết)
  • TKB và bài toán xếp Thời khóa biểu (236 bài viết)
  • Học tiếng Việt (175 bài viết)
  • Dành cho Giáo viên (379 bài viết)
  • Download - Archive- Update (156 bài viết)
  • Cùng Học (93 bài viết)
  • Learning Math: Tin học hỗ trợ học Toán trong nhà trường (72 bài viết)
  • Thông tin tuyển dụng (3 bài viết)
  • School@net 15 năm (18 bài viết)
  • Mỗi ngày một phần mềm (7 bài viết)
  • Dành cho cha mẹ học sinh (114 bài viết)
  • Khám phá phần mềm (30 bài viết)
  • GeoMath: Giải pháp hỗ trợ học dạy môn Toán trong trường phổ thông (34 bài viết)
  • Phần mềm cho em (13 bài viết)
  • Tin học và Toán học (116 bài viết)
  • Phần mềm Quản lý đào tạo nhà trường (69 bài viết)
  • Làm quen với Tin học (17 bài viết)
  • Vui học đường (1 bài viết)
  • Bài học trực tuyến (60 bài viết)
  • Các vấn đề giáo dục (2 bài viết)
  • Các Thuật toán hay (1 bài viết)
  • TKBU và bài toán thời khóa biểu trường đại học (11 bài viết)
  • Xem toàn bộ bài viết (3170 bài viết)
  •  
    Đăng nhập/Đăng ký
    Bí danh
    Mật khẩu
    Mã kiểm traMã kiểm tra
    Lặp lại mã kiểm tra
    Ghi nhớ
     
    Quên mật khẩu | Đăng ký mới
    
     
    Giỏ hàng

    Xem giỏ hàng


    Giỏ hàng chưa có sản phẩm

     
    Bản đồ lưu lượng truy cập website
    Locations of visitors to this page
     
    Thành viên có mặt
    Khách: 4
    Thành viên: 0
    Tổng cộng: 4
     
    Số người truy cập
    Hiện đã có 82207432 lượt người đến thăm trang Web của chúng tôi.

    KÝ PHÁP NGHỊCH ĐẢO BA LAN PHƯƠNG PHÁP TÍNH GIÁ TRỊ BIỂU THỨC TOÁN HỌC

    Ngày gửi bài: 16/10/2007
    Số lượt đọc: 5889

    Khi lập trình, tính giá trị một biểu thức toán học là điều quá đỗi bình thường. Tuy nhiên, trong nhiều ứng dụng (như chương trình vẽ đồ thị hàm số chẳng hạn, trong đó chương trình cho phép người dùng nhập vào hàm số), ta cần phải tính giá trị của một biểu thức được nhập vào từ bàn phím dưới dạng một chuỗi. Với các biểu thức toán học đơn giản (như a+b) thì bạn có thể tự làm bằng các phương pháp tách chuỗi “thủ công”. Nhưng để “giải quyết” các biểu thức có dấu ngoặc, ví dụ như (a+b)*c + (d+e)*f , thì các phương pháp tách chuỗi đơn giản đều không khả thi. Trong tình huống này, ta phải dùng đến Ký Pháp Nghịch Đảo Ba Lan (Reserve Polish Notation – RPN), một thuật toán “kinh điển” trong lĩnh vực trình biên dịch.

    Để đơn giản cho việc minh họa, ta giả định rằng chuỗi biểu thức mà ta nhận được từ bàn phím chỉ bao gồm: các dấu mở ngoặc/đóng ngoặc; 4 toán tử cộng, trừ, nhân và chia (+, -, *, /); các toán hạng đều chỉ là các con số nguyên từ 0 đến 9; không có bất kỳ khoảng trắng nào giữa các ký tự.

    Thế nào là ký pháp nghịch đảo Ba Lan?

    Cách trình bày biểu thức theo cách thông thường tuy tự nhiên với con người nhưng lại khá “khó chịu” đối với máy tính vì nó không thể hiện một cách tường minh quá trình tính toán để đưa ra giá trị của biểu thức. Để đơn giản hóa quá trình tính toán này, ta phải biến đổi lại biểu thức thông thường về dạng hậu tố - postfix (cách gọi ngắn của thuật ngữ ký pháp nghịch đảo Ba Lan). Để phân biệt hai dạng biểu diễn biểu thức, ta gọi cách biểu diễn biểu thức theo cách thông thường là trung tố - infix (vì toán tử nằm ở giữa hai toán hạng).

    Ký pháp nghịch đảo Ba Lan được phát minh vào khoảng giữa thập kỷ 1950 bởi Charles Hamblin - một triết học gia và khoa học gia máy tính người Úc - dựa theo công trình về ký pháp Ba Lan của nhà Toán học người Ba Lan Jan Łukasiewicz. Hamblin trình bày nghiên cứu của mình tại một hội nghị khoa học vào tháng 6 năm 1957 và chính thức công bố vào năm 1962.

    Từ cái tên hậu tố các bạn cũng đoán ra phần nào là theo cách biểu diễn này, các toán tử sẽ được đặt sau các toán hạng. Cụ thể là biểu thức trung tố: 4+5 sẽ được biểu diễn lại thành 4 5 +.

    Quá trình tính toán giá trị của biểu thức hậu tố khá tự nhiên đối với máy tính. Ý tưởng là đọc biểu thức từ trái sang phải, nếu gặp một toán hạng (con số hoặc biến) thì push toán hạng này vào ngăn xếp; nếu gặp toán tử, lấy hai toán hạng ra khỏi ngăn xếp (stack), tính kết quả, đẩy kết quả trở lại ngăn xếp. Khi quá trình kết thúc thì con số cuối cùng còn lại trong ngăn xếp chính là giá trị của biểu thức đó.

    Ví dụ: biểu thức trung tố :

    5 + ((1 + 2) * 4) + 3

    được biểu diễn lại dưới dạng hậu tố là (ta sẽ bàn về thuật toán chuyển đổi từ trung tố sang hậu tố sau):

    5 1 2 + 4 * + 3 +

    Quá trình tính toán sẽ diễn ra theo như bảng dưới đây:

    Chuyển đổi từ trung tố sang hậu tố

    Thuật toán chuyển đổi này được phát minh bởi vị giáo sư người Đức nổi tiếng Edsger Dijkstra (cũng là tác giả của thuật toán tìm đường đi ngắn nhất được đặt theo tên ông và semaphore, một kỹ thuật để đồng bộ các tiến trình trong lập trình đa nhiệm). Thuật toán này cũng dựa theo cơ chế ngăn xếp. Ý tưởng chung của thuật toán cũng là duyệt biểu thức từ trái sang phải:

    - Nếu gặp một toán hạng (con số hoặc biến) thì ghi nó vào chuỗi kết quả (chuỗi kết quả là biểu thức trung tố).

    - Nếu gặp dấu mở ngoặc, đưa nó vào stack.

    - Nếu gặp một toán tử (gọi là o1 ), thực hiện hai bước sau:

    o Chừng nào còn có một toán tử o2 ở đỉnh ngăn xếp độ ưu tiên của o1 nhỏ hơn hay bằng độ ưu tiên của o2 thì lấy o2 ra khỏi ngăn xếp và ghi vào kết quả.

    o Push o1 vào ngăn xếp

    - Nếu gặp dấu đóng ngoặc thì cứ lấy các toán tử trong ngăn xếp ra và ghi vào kết quả cho đến khi lấy được dấu mở ngoặc ra khỏi ngăn xếp.

    - Khi đã duyệt hết biểu thức trung tố, lần lượt lấy tất cả toán hạng (nếu có) từ ngăn xếp ra và ghi vào chuỗi kết quả.

    Để dễ hiểu, bạn hãy quan sát quá trình thực thi của thuật toán qua một ví dụ cụ thể sau: Biểu thức cần chuyển đổi: 3+4*2/(1-5)

    Dĩ nhiên là thuật toán được trình bày ở đây là khá đơn giản và chưa ứng dụng được trong trường hợp biểu thức có các hàm như sin, cos,… hoặc có các biến. Tuy nhiên, việc mở rộng thuật toán là hoàn toàn nằm trong khả năng của bạn nếu bạn đã hiểu cặn kẽ thuật toán cơ bản này.

    Đinh Nguyễn Anh Dũng (Theo diễn đàn báo điện tử của sinh viên ĐH CNTT)



     Bản để in  Lưu dạng file  Gửi tin qua email


    Lên đầu trang

     
    CÔNG TY CÔNG NGHỆ TIN HỌC NHÀ TRƯỜNG
     
    Phòng 804 - Nhà 17T1 - Khu Trung Hoà Nhân Chính - Quận Cầu Giấy - Hà Nội
    Phone: 024.62511017 - 024.62511081
    Email: kinhdoanh@schoolnet.vn


    Bản quyền thông tin trên trang điện tử này thuộc về công ty School@net
    Ghi rõ nguồn www.vnschool.net khi bạn phát hành lại thông tin từ website này
    Site xây dựng trên cơ sở hệ thống NukeViet - phát triển từ PHP-Nuke, lưu hành theo giấy phép của GNU/GPL.