Tính giá trị của một chuỗi!

English | Vietnamese

Rules

Main Forum

Portal

Member Listing

Statistics

Search

Reading Room
[Register]

Login [ | https ]

Forum Index

Thảo luận hệ điều hành Windows

Tính giá trị của một chuỗi!

[Programming] Tính giá trị của một chuỗi!	02/12/2008 08:35:34 (+0700) \| #1 \| 160981

publicIT
Member

Joined: 12/04/2008 14:44:09
Messages: 63
Offline

Mình có một chuỗi sau : "8 * 9 * 5 + (3 + 4) /2 - 13" (Đây chì là một ví dụ minh họa, có thể là một chuỗi bất kỳ)
Input là một chuỗi như trên, còn output là giá trị của biểu thức trong chuỗi.
Làm sao để tính giá trị của biểu thức trong chuỗi .Ai có ý tưởng để giải bài toán này thì chỉ cho mình nha!Mình đang cần gấp!THANKS!

[Question] Re: Tính giá trị của một chuỗi!	02/12/2008 12:36:43 (+0700) \| #2 \| 161010

FaL
Moderator

Joined: 14/04/2006 09:31:18
Messages: 1232
Offline

Bồ cần phải phân biệt được tokens nhập vào ở đây có các token căn bản như: số, phép toán (+-*/...) dấu ngoặc (), khoảng trắng,... Sau đó xác định trạng thái (state) rồi xử lý tùy theo trạng thái đó. Tìm với từ khóa "Finite-state machine" (nếu tôi không nhầm thì tiếng Anh là vậy).

PS: Ý tưởng bài này nằm trong lý thuyết của môn "Ngôn ngữ lập trình và trình biên dịch". Và hình như nó cũng có từ lâu lắm rồi, chứ không phải ý tưởng của tui nghen smilie

Hãy giữ một trái tim nóng và một cái đầu lạnh

[Question] Re: Tính giá trị của một chuỗi!	02/12/2008 12:37:06 (+0700) \| #3 \| 161011

VaT
Member

Joined: 04/09/2008 00:17:52
Messages: 87
Offline

Thuật giải đơn giản nhất cho bài này là dùng : stack. Bạn có thể đọc trong cuốn cẩm nang thuật toán để biết thêm chi tiết và tham khảo thêm các thuật toán khác.

[Question] Re: Tính giá trị của một chuỗi!	03/12/2008 00:52:12 (+0700) \| #4 \| 161049

4hfoo
Elite Member

Joined: 29/01/2007 01:50:20
Messages: 115
Offline

Một trong các thuật toán khá phổ biến để tính giá trị biểu thức là Thuật toán đảo Ba Lan (Reverse Polish notation)
Bạn có thể kiếm tài liệu đọc thêm trên Internet.

http://en.wikipedia.org/wiki/Reverse_Polish_Notation

Thân

[Question] Re: Tính giá trị của một chuỗi!	04/12/2008 11:00:18 (+0700) \| #5 \| 161236

publicIT
Member

Joined: 12/04/2008 14:44:09
Messages: 63
Offline

Mình cũng đã xem qua thuật toán nghịch đảo BALAN nhưng vẫn chưa hiểu lắm về cách chuyển từ biểu thức trung tố sang biểu thức hậu tố!
Cám ơn các bạn đã trả lời mình nha! smilie

[Question] Re: Tính giá trị của một chuỗi!	04/12/2008 14:42:14 (+0700) \| #6 \| 161264

FaL
Moderator

Joined: 14/04/2006 09:31:18
Messages: 1232
Offline

publicIT:
Ở link 4hfoo đưa có sẵn ví dụ, cách đọc token vào stack rồi đấy, bồ xem kỹ lại xem.
Mà thuật toán này chỉ đảo thôi, chứ không phải là nghịch đảo smilie

Hãy giữ một trái tim nóng và một cái đầu lạnh

Go to:

Users currently in here
1 Anonymous