[Stack] PostFix to InFix

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");
}

 

 

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 *