[Stack] PostFix to InFix

Contact for work: 096.1014.106 (Mr. Tiến)

Bài này là đảo ngược của bài trong link sau: https://kienthuc24h.com/stack-spoj-onp-transfer-expression-infix-postfix/

Các bạn lưu ý về quy định dấu ngoặc ( ).

Ví dụ:

ab+ —> (a+b)

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

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

Nội dung bài viết

Thuật toán

Đọc từ đầu đến cuối chuỗi, thực hiện các thao tác sau:

  • Nếu gặp kí tự là ‘a’ -> ‘z’ thì cho vào stack.st
  • Nếu gặp kí tự là ‘+’, ‘-‘, ‘*’, ‘/’, ‘^’ thì lấy 2 phần tử đầu trong stack ra và thực hiện phép toán với toán tử, sau đó thêm ‘(‘ ‘)’ vào 2 đầu.
  • Hàm IsStackHaving2more để kiểm tra xem Stack còn chứa ít nhất 2 phần tử hay ko? Nếu không thì chứng tỏ dữ liệu nhập vào là sai.

Khi duyệt hết chuỗi, lấy phần tử cuối cùng ra khỏi Stack, đó là kết quả.

Code

 

 

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 *