Bài 003. TÍNH TOÁN SONG SONG


Biểu thức đủ là một dãy ký tự gồm các biến ký hiệu bằng chữ cái thường tiếng Anh: a..z, các phép toán cộng ký hiệu +, nhân ký hiệu * và các dấu ngoặc (,). Được định nghĩa như sau: i) Mỗi biến a,b,...,z là một biểu thức đủ ii) Nếu X và Y là biểu thức đủ thì (X+Y) và (X*Y) cũng là biểu thức đủ. iii) Những biểu thức nào không xây dựng được theo 2 nguyên tắc trên không là biểu thức đủ. VD: Theo cách định nghĩa trên thì (a+(b+(c+d))) hoặc ((a+b)+(c*d)) là các biểu thức đủ. Cho biết thời gian tính phép + là P, thời gian tính phép * là Q, người ta định nghĩa thời gian tính toán một biểu thức đủ như sau: Nếu biểu thức đủ chỉ gồm 1 biến (a..z) thì thời gian tính toán là 0 Nếu X và Y là 2 biểu thức đủ; thời gian tính X là TX thời gian tính Y là TY thì thời gian tính (X+Y) là max(TX,TY)+P thời gian tính (X*Y) là max(TX,TY)+Q Từ 1 biểu thức đủ người ta có thể biến đổi về một biểu thức tương đương bằng các luật: Giao hoán: (X+Y)  (Y+X); (X*Y)  (Y*X) Kết hợp: (X+(Y+Z))  ((X+Y)+Z); (X*(Y*Z))  ((X*Y)*Z) Yêu cầu: Cho trước một biểu thức đủ E dưới dạng xâu ký tự hãy viết chương trình: 1. Tìm thời gian tính toán biểu thức E 2. Hãy biến đổi biểu thức E thành biểu thức E` tương đương với nó sao cho thời gian tính E` là ít nhất có thể. Dữ liệu vào được đặt trong file văn bản PO.INP như sau: Dòng thứ nhất ghi 2 số P, Q cách nhau 1 dấu cách (P,Q100) Tiếp theo là một số dòng, mỗi dòng ghi 1 biểu thức đủ. Kết quả ra đặt trong file văn bản PO.OUT như sau: Với mỗi biểu thức E trong file PO.INP ghi ra file PO.OUT 3 dòng Dòng thứ nhất: Ghi thời gian tính toán E Dòng thứ hai: Ghi biểu thức E` Dòng thứ ba: Ghi thời gian tính toán E` Chú ý: Để cho gọn, mỗi biểu thức đủ trong input/output file có thể viết mà không cần đến cặp dấu ngoặc ngoài cùng, dữ liệu vào được coi là đúng đắn và không cần kiểm tra Ví dụ:


This image has been resized. Click this bar to view the full image. The original image is sized 667x188 and weights 18KB.



Danh mục đính kèm