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

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ó:

Đọc và ghi nhận giá trị a, ghi giá trị a vào P. Vậy P = "a".

Đọc toán tử "*". Đưa toán tử này vào stack S: S = "*"

Đọc dấu ngoặc mở "(", đưa dấu ngoặc này vào stack: S = "*(".

Đọc hạng tử b, đưa b vào P: P= "a b"

Đọc toán tử "+", đặt "+" vào stack: S ="*(+"

Đọc hạng tử "c", đưa c vào cuối P: P="a b c"

Đọ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 +"

Đọ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 + * "

Đọc hạng tử d, đưa d vào cuối P. P="a b c + * d"

Đọc toán tử "^", đưa toán tử "^" vào cuối stack: S="-^"

Đọc hằng số 5, đưa 5 vào cuối P: P="a b c + * d 5"

Đã đọ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="a b c + * d 5 ^ -".

Thuật toán chuyển từ ký pháp trung tố sang ký pháp tiền tố hoặc hậu tố rất gần với cách xử lý các phép tính trong máy tính bấm tay (hay máy tính bỏ túi). Một biểu thức chỉ gồm các phép toán hai ngôi bất kỳ luôn có thể được tính bằng máy tính bấm tay mà không cần dùng dấu ngoặc. Các phép toán ở trước nếu có độ ưu tiên (ưu tiên bởi toán tử hoặc bởi dấu ngoặc) thấp hơn một phép toán ở sau được đẩy vào một ngăn xếp (stack), chỉ khi nào các phép toán ưu tiên hơn ở sau được tính xong, các phép toán ở trước mới được xử lý.

Các phương pháp biểu diễn phép toán hai ngôi

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)f(a,b)A. Á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 (ký pháp tiền tố), sau (ký pháp hậu tố) hoặc giữa (ký pháp trung tố) các toán 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ử, đó là ký pháp trung 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

Về lý thuyết, ký pháp tiền tố và ký pháp hậu tố còn có thể được mở rộng cho các phép toán ba ngôi hoặc nhiều hơn mà vẫn không phải dùng tới dấu ngoặc để thể hiện độ ưu tiên các phép toán, tương tự với hàm số đa biến, còn ký pháp trung tố thì không thể. Tuy nhiên, trong thực tế không có nhiều phép toán đa ngôi và ký pháp trung tố vẫn được dùng rộng rãi vì thói quen. Ví dụ: + a b c có thể được hiểu là tổng của 3 số a, b và c trong ký pháp tiền tố. Tương tự, f a b c có thể được hiểu là hàm f của 3 biến a, b và c trong ký pháp tiền tố.

Ký pháp Ba lan

Ký pháp Ba lan (tiếng Anh: Polish notation), còn gọi là ký pháp tiền tố (tiếng Anh: prefix 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.

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.

Hàng đợi trong khoa học máy tính

Hàng đợi (tiếng Anh: queue) là một cấu trúc dữ liệu dùng để chứa các đối tượng làm việc theo cơ chế FIFO (viết tắt từ tiếng Anh: First In First Out), nghĩa là "vào trước ra trước"

Trong hàng đợi, các đối tượng có thể được thêm vào hàng đợi bất kỳ lúc nào, nhưng chỉ có đối tượng thêm vào đầu tiên mới được phép lấy ra khỏi hàng đợi. Thao tác thêm vào và lấy một đối tượng ra khỏi hàng đợi được gọi lần lượt là "enqueue" và "dequeue". Việc thêm một đối tượng luôn diễn ra ở cuối hàng đợi và một phần tử luôn được lấy ra từ đầu hàng đợi.

Trong tin học, cấu trúc dữ liệu hàng đợi có nhiều ứng dụng: khử đệ qui, tổ chức lưu vết các quá trình tìm kiếm theo chiều rộng và quay lui, vét cạn, tổ chức quản lý và phân phối tiến trình trong các hệ điều hành, tổ chức bộ đệm bàn phím.

Cấu trúc dữ liệu hàng đợi có thể định nghĩa như sau: Hàng đợi là một cấu trúc dữ liệu trừu tượng (ADT) tuyến tính. Tương tự như ngăn xếp, hàng đợi hỗ trợ các thao tác:

EnQueue(o): thêm đối tượng o vào cuối hàng đợi.

DeQueue(): lấy đối tượng ở đầu queue ra khỏi hàng đợi và trả về giá trị của nó. Nếu hàng đợi rỗng thì lỗi sẽ xảy ra.

IsEmpty(): kiểm tra xem hàng đợi có rỗng không.

Front(): trả về giá trị của phần tử nằm ở đầu hàng đợi mà không hủy nó. Nếu hàng đợi rỗng thì lỗi sẽ xảy ra.

Các thao tác thêm, trích và huỷ một phần tử phải được thực hiện ở hai phía khác nhau của hàng đợi, do đó hoạt động của hàng đợi được thực hiện theo nguyên tắc FIFO. Cũng như ngăn xếp, cấu trúc mảng một chiều hoặc cấu trúc danh sách liên kết có thể dùng để biểu diễn cấu trúc hàng đợi.

Kiểu dữ liệu trừu tượng ngăn xếp

Trong khoa học máy tính, một ngăn xếp (còn gọi là bộ xếp chồng, tiếng Anh: stack) là một cấu trúc dữ liệu trừu tượng hoạt động theo nguyên lý "vào sau ra trước"

Kiểu dữ liệu trừu tượng ngăn xếp

Một ngăn xếp là một cấu trúc dữ liệu dạng thùng chứa (container) của các phần tử (thường gọi là các nút (node)) và có hai phép toán cơ bản : push and pop. Push bổ sung một phần tử vào đỉnh (top) của ngăn xếp, nghĩa là sau các phần tử đã có trong ngăn xếp. Pop giải phóng và trả về phần tử đang đứng ở đỉnh của ngăn xếp. Trong stack, các đối tượng có thể được thêm vào stack bất kỳ lúc nào nhưng chỉ có đối tượng thêm vào sau cùng mới được phép lấy ra khỏi stack.

Ngoài ra, stack cũng hỗ trợ một số thao tác khác:

isEmpty(): Kiểm tra xem stack có rỗng không.

Top(): Trả về giá trị của phần tử nằm ở đầu stack mà không hủy nó khỏi stack. Nếu stack rỗng thì lỗi sẽ xảy ra.

Các phép toán

Trong ngôn ngữ máy tính hiện nay, một ngăn xếp thường được dùng với các phép toán "push" và "pop". Độ dài (số phần tử) của ngăn xếp cũng là một tham số cần thiết của nó. Đôi khi cần tới một phép toán chỉ cần lấy giá trị của phần từ trên đỉnh ngăn xếp mà không xóa nó khỏi ngăn xếp 

Cấu trúc dữ liệu tuyến tính

Cấu trúc dữ liệu tuyến tính:

Mảng

Mảng

Bản đồ hai chiều

Mảng bit

Bit field

Bảng bit

Bitmap

Circular buffer

Bảng điều khiển

Ảnh

Mảng động

Gap buffer

Cây mảng băm

Heightmap

Bảng tra cứu

Ma trận

Mảng song song

Mảng sắp xếp

Sparse array

Sparse matrix

Vector Iliffe

Variable-length array

Danh sách

Danh sách liên kết

Danh sách liên kết đôi

Danh sách tự sắp xếp

Skip list

Unrolled linked list

VList

Danh sách liên kết XOR

Zipper

Doubly connected edge list

Kiểu dữ liệu

Kiểu dữ liệu cơ bản

Boolean (chỉ lưu một trong hai giá trị True/False)

Char (lưu giá trị ký tự)

Float (lưu giá trị số thực)

Double (kiểu dữ liệu kích thước lớn hơn float)

int (lưu giá trị nguyên hoặc fixed-precision)

String (lưu chuỗi của những ký tự)

Kiểu liệt kê

Kiểu kết hợp

Mảng

Bản ghi (còn được gọi là tuple hoặc struct)

Union

Tagged union (còn được gọi là biến thể, bản ghi biến thể, discriminated union, hoặc disjoint union)

Plain old data structure

Kiểu dữ liệu trừu tượng

Container

Deque

Map/Mảng kết hợp/Từ điển

Multimap

Set

Multiset

Hàng đợi

Hàng đợi ưu tiên

Ngăn xếp

Chuỗi

Cây

Đồ thị

Băm

Tổng quan cấu trúc dữ liệu

Tổng quan cấu trúc dữ liệu 

Thông thường, một cấu trúc dữ liệu được chọn cẩn thận sẽ cho phép thực hiện thuật toán hiệu quả hơn. Việc chọn cấu trúc dữ liệu thường bắt đầu từ chọn một cấu trúc dữ liệu trừu tượng. Một cấu trúc dữ liệu được thiết kế tốt cho phép thực hiện nhiều phép toán, sử dụng càng ít tài nguyên, thời gian xử lý và không gian bộ nhớ càng tốt. Các cấu trúc dữ liệu được triển khai bằng cách sử dụng các kiểu dữ liệu, các tham chiếu và các phép toán trên đó được cung cấp bởi một ngôn ngữ lập trình.

Tri thức đó đã dẫn đến sự nổi lên của nhiều ngôn ngữ lập trình và phương pháp thiết kế được hình thức hóa, mà trong đó, nhân tố tổ chức quan trọng là các cấu trúc dữ liệu chứ không phải các thuật toán. Đa số ngôn ngữ có một tính năng thuộc dạng hệ thống module cho phép các cấu trúc dữ liệu được tái sử dụng an toàn trong các ứng dụng khác nhau, bằng cách dùng các giao diện có điều khiển để che các chi tiết cài đặt đã được kiểm thử. Đặc biệt, các ngôn ngữ lập trình hướng đối tượng như C++ và Java sử dụng lớp (class) cho mục đích này.

Vì cấu trúc dữ liệu có tính chất quyết định đối với các chương trình chuyên nghiệp nên có rất nhiều hỗ trợ về cấu trúc dữ liệu trong các thư viện chuẩn của các ngôn ngữ lập trình hiện đại, ví dụ thư viện mẫu chuẩn của C++, Java API, và Microsoft .NET Framework.

Các cấu trúc xây dựng căn bản của hầu hết các cấu trúc dữ liệu là mảng (array), bản ghi (record), tổ hợp phân biệt(?) (discriminated union), và tham chiếu (reference). Ví dụ, tham chiếu khả rỗng (có thể có giá trị null) là một kết hợp của tham chiếu và cấu trúc discriminated union, và cấu trúc dữ liệu liên kết đơn giản nhất, danh sách liên kết, được xây dựng từ các bản ghi và các tham chiếu khả rỗng.

Tổng quan Thuật toán tìm kiếm nhị phân

Thuật toán tìm kiếm nhị phân dùng để tìm kiếm phần tử trong một danh sách đã được sắp xếp, ví dụ như trong một danh bạ điện thoại sắp xếp theo tên, có thể tìm kiếm số điện thoại của một người theo tên người đó.

Thuật toán tìm kiếm nhị phân chạy nhanh hơn tìm kiếm tuyến tính nhưng cũng có một số nhược điểm. Tìm kiếm nhị phân có thể chậm hơn bảng băm. Nếu nội dung danh sách bị thay đổi thì danh sách phải được sắp xếp lại trước khi sử dụng tìm kiếm nhị phân. Thao tác này thường tốn nhiều thời gian.

Thuật toán tìm kiếm nhị phân

Trong khoa học máy tính, thuật toán tìm kiếm nhị phân là một thuật toán dùng để tìm kiếm phần tử trong một danh sách đã được sắp xếp. Thuật toán hoạt động như sau. Trong mỗi bước, so sánh phần tử cần tìm với phần tử nằm ở chính giữa danh sách. Nếu hai phần tử bằng nhau thì phép tìm kiếm thành công và thuật toán kết thúc. Nếu chúng không bằng nhau thì tùy vào phần tử nào lớn hơn, thuật toán lặp lại bước so sánh trên với nửa đầu hoặc nửa sau của danh sách. Vì số lượng phần tử trong danh sách cần xem xét giảm đi một nửa sau mỗi bước, nên thời gian thực thi của thuật toán là hàm lôgarit.