UVALive – 4882 Parenthesis 表达式处理、字符串处理、栈

4882 - Parenthesis 表达式处理、字符串处理、栈

Source

UVALive - 4882

Output

题意：给一个有括号小写字母加号组成的字符串，去掉多余的括号后输出。

表表达式处理、字符串处理、栈

用栈，O(n)预处理出每个左括号i 对应的右括号mp[i]的位置，

然后扫一遍mp，对于每个括号判断左括号的左边是否是 字母或者右括号，右括号的右边是否是 字母或者左括号，

如果是就不能去掉，否则去掉的括号把flag[i]标记为true即可，

然后还有2个问题，去掉的括号在接下来的判断中该位置应当忽略，

1、比如

(((x+y)))x  => (x+y)x

故上面所说的左边或者右边是指忽略掉以去除括号的情况下的左边和右边，具体见代码。

2、对于

(xy)z时，故每次加一条判断，即 该对括号内 内括号外 是否有加号((x(y+z)))a，这个也是用sta来预处理到fi数组，具体见代码。

复杂度 O(n)

#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 1e3 + 8;

bool flag[maxn], f[maxn];
stack sta, sta2;
int mp[maxn];

int main()
{
    #ifdef LOCAL
    freopen("a.txt", "r", stdin);
    //freopen("a.out", "w", stdout);
    int T = 1;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    string s;
    int sz, i, j, k, cnt;
    while(cin >> s){
        sz = s.size();
        memset(flag, false, sizeof flag);
        memset(mp, 0, sizeof mp);
        memset(f, false, sizeof f);
        cnt = 0;
        for(i = 0; i < sz; i++){
            if(s[i] == '('){
                sta.push(i);
                sta2.push(cnt);
                cnt = 0;
            }
            else if(s[i] == ')'){
                mp[sta.top()] = i;
                if(cnt == 0){
                    f[sta.top()] = true;
                }
                if(!sta2.empty())cnt = sta2.top();
                else cnt = 0;
                sta2.pop();
                sta.pop();
            }
            if(s[i] == '+') cnt++;
        }
        for(int i = 0; i < sz; i++){
            if(mp[i] != 0){
                if(f[i]){
                    flag[i] = true;
                    flag[mp[i]] = true;
                }
                else{
                j = mp[i] + 1;
                while(flag[j] && j < sz) j++; k = i - 1; while(flag[k] && k >= 0) k--;

                if(!flag[k] && k >= 0){

                    if(!flag[j] && j < sz){

                        if(!isalpha(s[k]) && s[k] != ')' && !isalpha(s[j]) && s[j] != '('){
                            flag[i] = true;
                            flag[mp[i]] = true;
                        }
                    }
                    else{
                        if(!isalpha(s[k]) && s[k] != ')'){
                            flag[i] = true;
                            flag[mp[i]] = true;
                        }
                    }

                }
                else{
                    if(!flag[j] && j < sz){
                        if(!isalpha(s[j]) && s[j] != '('){
                            flag[i] = true;
                            flag[mp[i]] = true;
                        }
                    }
                    else{
                        flag[i] = true;
                        flag[mp[i]] = true;
                    }
                }

                }
            }

        }
        for(int i = 0; i < sz; i++){
            if(!flag[i]) cout << s[i];
        }
        cout << "n";

    }




    #ifdef LOCAL
    //cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx