[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

    #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;
    }