[Stack]- SPOJ ONP – Transfer the expression – Infix to Postfix

Link: http://www.spoj.com/problems/ONP/

Giải thích SPOJ ONP

Chuyển cách biểu diễn 1 biểu thức từ infix sang postfix ( các bạn google để hiểu thêm hihi).

Thứ tự biểu thức quy định bởi dấu ngoặc đơn. ().

Ví dụ:

(a+b) —–> ab+

((a+t)*((b+(a+c))^(c+d))) —–> at+bac++cd+^*

((a+(b-c))*((d-e)/((f-g)+h))) ——> abc-+de-fg-h+/*

Lưu ý: Khi cho các bộ test, các bạn phải đặt đầy đủ dấu ngoặc ( ).

a+b+c –> wrong answer

(a+b+c) –> wrong answer

((a+b)+c) –> right answer

Các bạn có thể kiểm tra kết quả trong link sau: http://www.mathblog.dk/tools/infix-postfix-converter/

 

Thuật toán SPOJ ONP

Đọc từng dòng, duyệt từ đấu đến cuối chuỗi:

  • Nếu gặp kí tự trong bảng chữ cái ‘a’ – ‘z’ thì in ra.
  • Nếu gặp các phép toán thì bỏ vào stack.
  • Nếu gặp kí tự ‘)’ thì lấy 1 phần tử ở đầu của stack ra.

Code tham khảo SPOJ ONP

 

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *