AcWing 1225. 正则问题-栈做法

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 1225. 正则问题-栈做法原题链接中等

作者：

启真湖里启真鱼 , 2021-04-09 22:26:41 , 所有人可见 , 阅读 1823

36

9

正则问题

题目描述

考虑一种简单的正则表达式：

只由 x ( ) | 组成的正则表达式。

小明想求出这个正则表达式能接受的最长字符串的长度。

例如 ((xx|xxx)x|(x|xx))xx 能接受的最长字符串是： xxxxxx，长度是6。
输入格式

一个由x()|组成的正则表达式。
输出格式

输出所给正则表达式能接受的最长字符串的长度。
数据范围

输入长度不超过100，保证合法。

样例

((xx|xxx)x|(x|xx))xx

样例输出

算法

时间复杂度 $O(n^2)$

主要思路

**比较菜，只能想到表达式那类问题的做法，于是按照表达式求值对括号的处理思路对本题进行求解
具体的思路就不说了，核心的思想是栈————遇到’)’则对当前括号进行处理，否则入栈

有几个要注意的地方：**
1. 不要忘了把左括号pop出来
2. 一个括号里可能有多个’|’，要选择合适的做法去得到当前括号最大长度
3. 最后要再count一次，因为可能此时栈里还有’|’
4. 最后栈的size，就是我们的答案了

C++ 代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<stack>
#include<algorithm>

using namespace std;

string str;
stack<char> stk;

void count(){
    //统计现在这个括号里的最大值
    //注意括号里可能没有'|'
    //但也可能有多个'|'   
    int n1 = 0, max_n = 0;
    while(stk.size() && stk.top() != '('){
        char top_ch = stk.top();
        stk.pop();
        if(top_ch == 'x'){
            n1++;
        }else{
            max_n = max(max_n, n1);
            n1 = 0;
        }
    }
    max_n = max(max_n, n1);
    //cout << max_n << endl;

    if(stk.size()) stk.pop();//把'('pop出来

    //在push进去最多的*
    for(int j = 0; j < max_n; j++){
        stk.push('x');
    }

}

int main(){
    cin >> str;

    int l = str.size();

    for(int i = 0; i < l; i++){
        int ch = str[i];
        if(ch != ')'){
            stk.push(ch);
        }else{
            count();
        }
    }

    count();

    cout << stk.size() << endl;

    return 0;
}

12 评论

启真湖里启真鱼 2021-04-09 22:27

我要顶自己hhhhhh

追逐光成为光 2022-02-14 12:01

冲你这份自信，顶你一下。

面壁者北茶 9个月前

这位老哥（大姐）算法有一个明显的瑕疵，就是每次求值后，会将一连串的 x 压回栈中，下次求值又反复弹出，导致时间开销为 O(n^2) 。受博主代码的启发，本菜狗进行了一点简单的优化，把每次求值后的子串使用一个整数来维护，于是时间代价就降低到 O(n)。代码如下：

#include <iostream>
#include <string>
#include <stack>
#include <algorithm>

using namespace std;

// 分别表示逻辑或, 左括号 
const int OR = -1, BRA = -2;

string str;
int n;

stack<int> stk;

// 计算左边到左括号为止的子串长度 
void evaluate() {
    int curr = 0, maxv = 0;
    while (stk.top() != BRA) {
        int t = stk.top(); stk.pop();
        if (t > 0) {
            curr += t;      // 如果是数字, 执行逻辑与 
        }
        else {              // t = -1, 执行逻辑或 
            maxv = max(maxv, curr);
            curr = 0;
        }
    }
    maxv = max(maxv, curr);

    stk.pop();      // 弹出左括号 

    stk.push(maxv);     // 将当前子串的最大长度压回栈中 
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    // 相当于在整个表达式的外围加一个括号 
    stk.push(BRA);

    cin >> str;
    n = str.size();

    for (int i = 0; i < n; i++) {
        char c = str[i];

        // 如果是 x, 统计连续的 x 的长度并压入栈中 
        if (c == 'x') {
            int cnt = 1, j = i + 1;
            while (j < n && str[j] == 'x') {
                cnt++;
                j++;
            }
            i = j - 1;
            stk.push(cnt);
        }

        // 左括号压入栈中 
        else if (c == '(') {
            stk.push(BRA);
        }

        // 右括号, 将到最近的左括号为止的子串求值 
        else if (c == ')') {
            evaluate();
        }

        // 操作符压入栈中 
        else {
            stk.push(OR);
        }
    }

    evaluate();

    cout << stk.top(); 

    return 0;
}

尘飄 10个月前

佬

自律的俗人 9个月前

厉害啊

acwing_8880 9个月前

#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
using namespace std;

string str;
char stk[110];
int top;

void count(){

int n1=0,max_n=0;
while(stk[top]!=0&&stk[top]!=’(‘){
char top_ch=stk[top];
top–;
if(top_ch==’x’){
n1++;
}
else{//’ ( | ‘
max_n=max(max_n,n1);
n1=0;//重新计数
}
}
if(stk[top]){
top–;//删除（
}

max_n=max(max_n,n1);
//之前清空栈找到最长的的X了
//现在放回去最长X，以后可能有|需要判断
for(int j=0;j<max_n;j){
stk[top]=’x’;
}
}

int main(){
cin>>str;

int l=str.size();

for(int i=0;i<l;i){
int ch=str[i];
if(ch!=’)’){
stk[top]=ch;
}
else count();
}
count();//理括号外的任何“x”字符，之前这里忘了可恶

cout<<top;
}// ((xx|xxx)x|(x|xx)) (xx)x|xx(xxx|xx)(x(xx|x)xx)xxx
// (xx)x|x