PTIT122A - Loại bỏ dấu ngoặc thừa

Link Sub: http://www.spoj.com/PTIT/problems/PTIT122A/
Người Gửi: Dương Lee

• Problem:

Cho một biểu thức đúng và thỏa mãn:
- Các biến trong biểu thức chỉ chứa các chữ cái viết hoa.
- Các toán tử trong biểu thức là ‘+’ hoặc ‘-‘ (trong biểu thức không có phép toán nhân hay chia đâu nhé ;) )
Nhiệm vụ của các bạn trong bài này sẽ là loại bỏ các dấu ngoặc thừa mà vẫn giữ nguyên ý nghĩa của biểu thức.

Input

Dữ liệu vào gồm nhiều bộ test:
- Dòng đầu tiên chứa số biểu thức M (1<=M<=10).
- M dòng tiếp theo, mỗi dòng là một biểu thức đúng, có thể có các dấu cách tùy ý trong mỗi dòng. Độ dài mỗi dòng (bao gồm cả dấu cách) không quá 255 kí tự.

Output

Với mỗi biểu thức, in ra trên một dòng riêng biệt biểu thức cùng ý nghĩa với biểu thức đã cho và không có các dấu ngoặc thừa. Chú ý: Thứ tự của các toán hạng trong biểu thức in ra và biểu thức đầu vào phải giống nhau. Các dấu cách thừa cũng phải được loại bỏ.

Example:

Input

3
(A-B + C) - (A+(B - C)) - (C-(D- E) )
((A)-( (B)))
A-(B+C)

Output:

A-B+C-(A+B-C)-(C-(D-E))
A-B
A-(B+C)

• Solution:

- Bài này thực chất là chỉ xử lý string bình thường và độ dài xâu cũng không quá dài (255 ký tự). Nhưng nếu làm theo cách xủ lý thông thường thì quá lằng nhằng và phức tạp + time chặt = 0.214s -> Khó 1 đấm AC ^^. Vậy nên để giải quyết nhanh gọn với độ phức tạp O(n) ta sẽ dùng stack để xử lý.
- Code dưới đây chia ra 3 phần xủ lý chính:
+ xóa dấu cách (cái này quá dễ rồi, chỉ cần không duyệt dấu cách là được)
+ xóa các cặp ngoặc kiểu dạng: (a)->a, ((a+b))->(a+b), ((a+((b-c))))->(a+(b-c)). Ý tưởng chính đối với loại cặp ngoặc này đó là với mỗi lần duyệt cặp ngoặc trong stack ta xác định xem trong cặp ngoặc đó có +, - không? nếu có thì đó là cặp ngoặc của một biểu thức, nếu không thì sẽ là cặp ngoặc thừa. (Để xử lý với O(n) dùng thêm stack_index và mảng dele[] để lưu vị trí và đánh dấu lại cặp ngoặc bị thừa)
VD:
((a+b))
x[0]='(' - Stack: empty
x[1]='(' - Stack: ( 
x[2]='a' - Stack: ( (
x[3]='+' - Stack: ( ( a
x[4]='b' - Stack: ( ( a +
x[5]=')' - Stack: ( ( a + b 
->Pop() -> Stack: ( -> có '+' -> ngoặc không thừa
x[6]=')' - Stack: ( 
->Pop() -> Stack: empty -> không có '+'or'-' -> ngoặc thừa

+ xóa các cặp ngoặc kiểu dạng: (a+(a+b))->a+a+b, d-((a-b)+c)->d-(a-b+c). Ý tưởng chính cho đối với cặp ngoặc này là với mỗi ngoặc '(' thì xem trước nó có dấu '-' hay không? Nếu không có thì có thể xóa cặp ngoặc đó. (Dùng stack để xủ lý với phức tạp O(n)).

• Code:

C++:

https://ideone.com/tQedM4

#include <iostream>
#include <stack>
using namespace std;

string deleteSpace (string x)   //a+ b -> a+b
{
    string rs = "";
    for (int i=0; i<x.length(); i++)
        if (x[i]!=' ')
            rs+=x[i];
    return rs;
}

string delete_1 (string x)  //delete string like (a)->a || ((a+b))->(a+b)
{
    stack <char> s;
    stack <int> index;
    int dele[300] = {0};
    for (int i=0; i<x.length(); i++)
    {
        if (x[i]==')')
        {
            int flag = 0;
            while (s.top()!='(')
            {
                char top = s.top();
                if (top=='+' || top=='-')
                    flag = 1;
                s.pop();
                index.pop();
            }
            if (flag == 0)
            {
                dele[index.top()] = 1;
                dele[i] = 1;
            }
            s.pop();
            index.pop();
        }
        else
        {
            s.push(x[i]);
            index.push(i);
        }
    }
    string rs = "";
    for (int i=0; i<x.length(); i++)
    {
        if (dele[i]==0)
            rs+=x[i];
    }
    return rs;
}

string delete_2 (string x)  //delete string like ((a+b)+c)->(a+b+c) || (a+(b-c))->(a+b-c)
{
    stack <char> s;
    stack <int> index;
    int dele[300] = {0};
    for (int i=x.length()-1; i>=0; i--)
    {
        if (x[i]=='(')
        {
            int flag = 1;
            if (i==0 || x[i-1]!='-')
                flag = 0;
            while (s.top()!=')')
            {
                s.pop();
                index.pop();
            }
            if (flag == 0)
            {
                dele[index.top()] = 1;
                dele[i] = 1;
            }
            s.pop();
            index.pop();
        }
        else
        {
            s.push(x[i]);
            index.push(i);
        }
    }
    string rs="";
    for (int i=0; i<x.length(); i++)
    {
        if (dele[i]==0)
            rs+=x[i];
    }
    return rs;
}

int main ()
{
    string str = "";
    int n;
    cin>>n;
    cin.ignore();
    while (1)
    {
        if (n==0) break;
        n--;
        getline(cin, str);
        string str_no_space = deleteSpace(str);
        string str_1 = delete_1(str_no_space);
        string str_2 = delete_2(str_1);
        cout<<str_2<<endl;
    }
    return 0;
}

JAVA:

...

Python:

...

Author : DL

Share this

Related Posts