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)))

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

#include<iostream>
#include<string>
#include<stack>
using namespace std;
int IsStackHaving2more(stack <string> p )
{
    p.pop();
    if (p.empty())
        return 0;
    return 1;
}
int main()
{
    //freopen("INPUT.INP", "rt", stdin);
    int t;
    cin>>t;
    cin.ignore();
    while(t--)
    {
        string s;
        stack<string> p;
        getline(cin,s);
        for(int i=0;i<s.length();++i)
        {
            if (s[i] >= 'a' && s[i] <= 'z')
            {
                string ss(1, s[i]);
                p.push(ss);
            }
            else if(IsStackHaving2more(p) && (s[i]=='+' || s[i]=='-' || s[i]=='*' || s[i]=='/' || s[i]=='^'))
            {
                string c1=p.top();
                p.pop();
                string c2=p.top();
                p.pop();
                string stemp = "(" + c2 + s[i]+ c1 + ")";
                p.push(stemp);
            }
            else
            {
                cout<<"Expression Error!!!";
                break;
            }
        }
        cout<<p.top();
        cout<<endl;
    }
    system("pause");
}