02/10/2018, 15:06
[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+^* ...
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
#include<iostream>
#include<string>
#include<stack>
using namespace std;
int t;
string in;
int main()
{
cin >> t;
cin.ignore();
while (t--)
{
stack<char> p;
getline(cin, in);
for (int i = 0; i < in.length(); i++)
{
if (in[i] >= 'a' && in[i] <= 'z')
{
cout<<in[i];
}
else if (in[i]==')')
{
cout<<p.top();
p.pop();
}
else if(in[i]!='(')
p.push(in[i]);
}
cout<<endl;
}
return 0;
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | #include<iostream> #include<string> #include<stack> using namespace std; int t; string in; int main() { cin >> t; cin.ignore(); while (t--) { stack<char> p; getline(cin, in); for (int i = 0; i < in.length(); i++) { if (in[i] >= 'a' && in[i] <= 'z') { cout<<in[i]; } else if (in[i]==')') { cout<<p.top(); p.pop(); } else if(in[i]!='(') p.push(in[i]); } cout<<endl; } return 0; } |
