首页 > 试题广场 >

解压字符串

[编程题]解压字符串
  • 热度指数：1180 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
猿辅导APP需要下发一些宣传文本给学生，工程师们使用了一种字符压缩算法，为简单起见，假设被压缩的字符全部为大写字母序列，A,B,C,D....Z,压缩规则如下：
1.AAAB可以压缩为A3B (单字符压缩不加括号)
2.ABABA可以压缩为(AB)2A （多字符串压缩才加括号）

输入数据保证不会出现冗余括号，且表示重复的数字一定合法且大于1，即不会出现：
1.（A)2B   ------- （应为：A2B）
2.  ((AB))2C,-----(应为：（AB)2C  )
3. （A)B  ----- （应为：AB）
4.   A1B，（AB)1C，（应为 AB，ABC）

注意：数字可能出现多位数即A11B或者(AB)10C或者A02这种情况。
A11B = AAAAAAAAAAAB
(AB)10C = ABABABABABABABABABABC
A02 = AA

数据分布：
对于60%的数据，括号不会出现嵌套，即不会有 ((AB)2C)2这种结构。
对于80%的数据，括号最多只嵌套一层，即不会有 (((AB)2C)2D)99 这种结构。
对于100%的数据，括号可以嵌套任意层。

输入描述:
第一行是正整数C(C <= 100)，表示下面有C组数据。之后C行，每行为一组数据，每组数据为一个字符串。

每个字符串由A-Z,数字0-9和(,)组成表示一个压缩后的串，保证输入数据一定合法且字符串长度小于50。


输出描述:
输出C行，每行对应一个数据的输出结果，表示压缩前的字符串，保证每个字符串展开后的长度不超过10^6。
示例1

输入

5
A11B
(AA)2A
((A2B)2)2G
(YUANFUDAO)2JIAYOU
A2BC4D2

输出

AAAAAAAAAAAB
AAAAA
AABAABAABAABG
YUANFUDAOYUANFUDAOJIAYOU
AABCCCCDD
算法知识视频讲解
添加回答
Python
沙漠青鸟头像 沙漠青鸟
编程语言：python3
方法：对于每一个待处理字符串，从左到右扫描整个字符串，构造一个列表t作为栈。每遇到一个左括号将t扩充一个字符串元素用来保存括号内的元素；每遇到一个右括号先找到其后的完整数字转为int后用u来保存，并pop出栈t最后新加的字符串元素且将此元素乘以u加入到pop后的t的最后一个元素中；每遇到一个数字时，将整个数字完整的找到后再把t[-1][-1]乘以这个数字减1再并入t[-1]中；每遇到一个普通字母时，只需将其直接并入t[-1]。最后t[0]即是output。 

n=int(input())
st=[]
for i in range(n):
    st.append(input())
     
for s in st:
    t=['']
    j=0
    while j<len(s):
        if s[j]=='(':
            t.append('')
            j+=1
        elif s[j]==')':
            k=j+1
            j+=1
            while j<len(s) and ord(s[j])>=ord('0') and ord(s[j])<=ord('9'):
                j+=1
            u=int(s[k:j])
            v=t.pop()
            t[-1]+=v*u
        elif ord(s[j])>=ord('0') and ord(s[j])<=ord('9'):
            k=j
            j+=1
            while j<len(s) and ord(s[j])>=ord('0') and ord(s[j])<=ord('9'):
                j+=1
            u=int(s[k:j])
            t[-1]+=t[-1][-1]*(u-1)
        else:
            t[-1]+=s[j]
            j+=1
    print(t[0])


发表于 2020-04-02 20:17:31 回复(0)
1+½+¼+⅛+...头像 1+½+¼+⅛+... 
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner input;
        int C, i;
        String[] strs;
        
        input = new Scanner(System.in);
        while(input.hasNext()){
            C = input.nextInt();
            strs = new String[C];
            for(i = 0; i < C; i++){
                strs[i] = input.next();
            }
            for(i = 0; i < C; i++){
                System.out.println(Solution(strs[i]));
            }
        }
    }
    
    private static String Solution(String str){
        StringBuilder ans;
        Stack<Integer> stack;
        int i, j, l;
        char c;
        
        ans = new StringBuilder();
        stack = new Stack<>();
        l = str.length();
        i = 0;
        while(i < l){
            c = str.charAt(i);
            if(c == '('){
                stack.push(ans.length());
                i++;
            }else if(c >= 'A' && c <= 'Z'){
                ans.append(c);
                i++;
            }else if(c >= '0' && c <= '9'){
                j = i;
                while(i < l && str.charAt(i) >= '0' && str.charAt(i) <= '9'){
                    i++;
                }
                ans.append(repeat(ans.substring(ans.length() - 1), Integer.parseInt(str.substring(j, i)) - 1));
            }else if( c == ')'){
                i++;
                j = i;
                while(i < l && str.charAt(i) >= '0' && str.charAt(i) <= '9'){
                    i++;
                }
                ans.append(repeat(ans.substring(stack.pop()), Integer.parseInt(str.substring(j, i)) - 1));
            }
        }
        return ans.toString();
    }
    
    private static String repeat(String str, int n){
        int i;
        StringBuilder ans;
        
        ans = new StringBuilder();
        for(i = 0; i < n; i++){
            ans.append(str);
        }
        return ans.toString();
    }
}

发表于 2019-12-15 11:05:55 回复(0)
啊啊啊啊喵头像 啊啊啊啊喵 
n = int(input())
temp = []
for i in range(n):
    temp.append(input())
for s in temp:
    temp0 = [] #[
    temp1 = '' #(HUN)
    temp2 = '' #ASDF
    n_temp = len(s)
    j=0
    while j < n_temp:
        if s[j] == '(':
            temp0 += s[j]
            j+=1
        elif s[j] == ')':
            temp0.pop()
            j+=1
        elif ord(s[j])>= ord('0') and ord(s[j])<=ord('9'):
            k=j
            j+=1
            if j<len(s) and ord(s[j])<=ord('9') and ord(s[j])>=ord('0'):
                j = j+1
            u = int(s[k:j])
            if len(temp1) != 0:
                temp2 += temp1*u
                temp1=''
            else:
                temp2 += temp2[-1]*(u-1)
        else:
            if len(temp0) == 0:
                temp2 += s[j]
                j += 1
            else:
                temp1 += s[j]
                j = j+1
    print(temp2)
python3解法
发表于 2020-07-29 16:39:17 回复(0)
WYACAC头像 WYACAC 
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.nextLine();
        StringBuilder sb = new StringBuilder();
        int tem = 0;
        Stack<String> stack1 = new Stack();
        while(n>0){
            String str = scanner.nextLine();
            for(int i=0;i<str.length();i++){
                char ch = str.charAt(i);
                if(ch == '('){
                    stack1.push("(");
                }else if(ch == ')'){
                    sb = new StringBuilder();
                    while(!stack1.peek().equals("(")){
                         
                        sb.append(stack1.pop());
                    }
                    stack1.pop();
                    stack1.push(sb.toString());
                }else if(ch>='A'&&ch<='Z'){
                    stack1.push(ch+"");
                }else{
                    tem = 0;
                    while(ch>='0'&&ch<='9'){
                        tem = tem*10+ch-'0';
                        i++;
                        if(i>=str.length())
                            break;
                        ch = str.charAt(i);
                    }
                    sb = new StringBuilder();
                    String str1 = stack1.pop();
                    for(int j=0;j<tem;j++){
                        sb.append(str1);
                    }
                    stack1.push(sb.toString());
                    i--;
                }
            }
            sb = new StringBuilder();
            while(!stack1.isEmpty()){
                sb.append(stack1.pop());
            }
            System.out.println(sb.reverse().toString());
            n--;
        }
    }
}

发表于 2021-03-27 10:28:23 回复(0)
我是厉害的菜鸡头像 我是厉害的菜鸡
1.方法1：用栈实现，遇到左括号就进栈，直到遇到右括号，出栈 
#include <iostream>
#include <string>
#include <stack>
using namespace std;
int readNum(const string str,int& i)
{
    int num=0;
  while(i<str.size()&&str[i]>='0'&&str[i]<='9')
   {
        num*=10;
        num+=str[i]-'0';
        i++;
    }
    return num;
}
int main()
{
    string str;
    int n;
    cin>>n;
    while(cin>>str)
    {
        stack<string> str_brack;
        str_brack.push(""); //这个是结果
        for(int i=0;i<str.size();)
        {
            if(str[i]=='(')
                str_brack.push("");
            else if(str[i]==')')
            {
                //读取数据
                i++;  //数字开始
                int num=readNum(str,i); 
                string rep=str_brack.top();
                str_brack.pop();
                string tmp="";
                while(num--)
                    tmp+=rep;
                str_brack.top()+=tmp;
                continue;
            }
            else if(str[i]-'0'<10&&str[i]-'0'>=0) //单个重复
            {
                char repeat=str[i-1];
                int num=readNum(str,i);
                while(--num)
                        str_brack.top()+=repeat;
                continue;
            }
            else  str_brack.top()+=str[i];
            i++;
        }
        cout<<str_brack.top()<<endl;
    }
return 0;
}


发表于 2020-12-20 19:42:52 回复(1)
emptyCoder头像 emptyCoder

非常非常直接的题目！！！
维护一个字符串类型的栈，遇到左括号 + 大写字母入栈，碰到数字 num，出栈（s），对 s 执行 num 次拼接**栈，遇到右括号不断出栈，并对出栈字符串逆序拼接，到碰到左括号为止！！！
最后栈中的字符串逆序拼接就是最终的结果！！！ 

// EJ105(DFG(ADC2B3CC5)2)2GA2
// 主要是熟悉 go 中一些高效的字符串拼接操作
package main

import (
    "fmt"
    "strings"
)

func main() {
    var C int
    fmt.Scan(&C)
    for i := 1; i <= C; i++ {
        curLine := ""
        fmt.Scan(&curLine)

        data := []string{}
        var cnt int

        for i := 0; i < len(curLine); i++ {
            if curLine[i] == '(' {
                data = append(data, "(")
                continue
            }
            if curLine[i] == ')' {
                var tmp string
                for data[len(data)-1] != "(" {
                    tmp = strings.Join([]string{data[len(data)-1], tmp}, "")
                    data = data[:len(data)-1]
                }
                data[len(data)-1] = tmp // 覆盖 "("
                continue
            }
            if curLine[i] >= 'A' && curLine[i] <= 'Z' {
                data = append(data, string(curLine[i]))
                continue
            }

            for i < len(curLine) && curLine[i] >= '0' && curLine[i] <= '9' {
                cnt = 10*cnt + int(curLine[i]-'0')
                i++
            }
            if cnt != 0 {
                //fmt.Println(data[len(data)-1])
                data[len(data)-1] = strings.Repeat(data[len(data)-1], cnt)
                // 重置
                cnt = 0
            }
            i-- // 退一步
        }
        var ans strings.Builder
        for i := 0; i < len(data); i++ {
            ans.WriteString(data[i])
        }
        fmt.Println(ans.String())
    }
}
编辑于 2020-10-04 21:47:09 回复(0)
搬砖的醇香土豆泥头像 搬砖的醇香土豆泥 
import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int C = Integer.parseInt(br.readLine());
        for (int i = 0; i < C; i++) {
            String s = br.readLine();
            StringBuilder sb = new StringBuilder();
            Deque stack = new ArrayDeque();
            for (int j = 0; j < s.length(); j++) {
                char c = s.charAt(j);
                if (c == '(') {
                    // 左括号压栈下标
                    stack.push(sb.length());
                } else if (c == ')') {
                    // 右括号出栈，并考虑后面有无数字
                    int left = stack.pop();
                    String sub = sb.substring(left);
                    j++;
                    int cnt = s.charAt(j) - '0';
                    // 计算重复次数
                    while (j = '0' && s.charAt(j + 1) <= '9') {
                        cnt = cnt * 10 + s.charAt(j + 1) - '0';
                        j++;
                    }
                    // 在遍历时已经添加过一遍，故重复cnt-1遍
                    for (int k = 0; k < cnt - 1; k++) {
                        sb.append(sub);
                    }
                } else if (c >= '0' && c <= '9') {
                    // 单个字符的重复，取sb中最后一个字符进行重复
                    int cnt = c - '0';
                    while (j = '0' && s.charAt(j + 1) <= '9') {
                        cnt = cnt * 10 + s.charAt(j + 1) - '0';
                        j++;
                    }
                    char lastChar = sb.charAt(sb.length() - 1);
                    for (int k = 0; k < cnt - 1; k++) {
                        sb.append(lastChar);
                    }
                } else {
                    sb.append(c);
                }
            }
            System.out.println(sb);
        }
    }
}

类似题目：LeetCode 394. 字符串解码

发表于 2020-09-19 21:46:59 回复(0)
梅怪小南头像 梅怪小南
import java.util.*;

public class Main {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        while(n>0)
        {
            String s=input.next();
            char[] c=s.toCharArray();
            int l=c.length;
            int i=0;
            StringBuffer buffer=new StringBuffer();
            Stack<String> st=new Stack<>();
            while(i<l)
            {   
                //处理左括号和字符
                while(i<l&&c[i]=='(') { st.push("(");i++;}
                while(i<l&&c[i]>='A'&&c[i]<='Z') {buffer.append(c[i]);i++;}
                st.push(buffer.toString());
                buffer=new StringBuffer();
                //处理右括号
                while(i<l&&c[i]==')'&&!st.isEmpty()&&!st.peek().equals("(")) buffer.insert(0, st.pop());
                if(!st.isEmpty()&&st.peek().equals("(")) { st.pop();i++;}
                //处理数字
                int times=1;
                StringBuffer num=new StringBuffer();
                while(i<l&&c[i]>='0'&&c[i]<='9') {num.append(c[i]);i++;}
                if(!num.toString().equals("")) times=Math.max(times,Integer.parseInt(num.toString()));
                //缓冲区内元素复制
                Boolean flag=true; //判断有没有右括号，true为有
                if(buffer.toString().equals("")&&!st.isEmpty()) { buffer.insert(0, st.pop());flag=false;}
                String copy=new String((flag==true?buffer.toString():buffer.substring(buffer.length()-1)));
                for(int k=1;k<times;k++) buffer.append(copy);
                //连接和重新入栈
                while(!st.isEmpty()&&!st.peek().equals("(")) buffer.insert(0, st.pop());
                st.push(buffer.toString());
                buffer=new StringBuffer();    
            }
            System.out.println(st.pop());
            n--;
        }
    }
}

发表于 2020-08-23 21:09:30 回复(0)
C/C++
想要个offer啊求求了头像 想要个offer啊求求了
#include<iostream>
#include<string>
using namespace std;

string decode(string s, int &i){
    if(i >= s.size())
        return NULL;
    string res = "";
    while(i < s.size()){
        if(s[i] == '('){
            i++;
            res += decode(s, i);
        }
        else if(isupper(s[i])){
            res += s[i++];
        }
        else if(isdigit(s[i])){
            int num = 0;
            while(i < s.size() && isdigit(s[i]))
                num = num*10 + (s[i++]-'0');
            res.append(num-1, res[res.size()-1]);
        }
        else if(s[i] == ')'){
            i++;
            int num = 0;
            while(i < s.size() && isdigit(s[i])){
                num = num*10+(s[i++]-'0');
            }
            string ans = "";
            for(int v = 0; v < num; v++){
                ans += res;
            }
            return ans;
        }
        
    }
    return res;
}
int main(){
    int N;
    cin >> N;
    for(int n = 0; n < N; n++){
        string s;
        cin >> s;
        int i = 0;
        string res = decode(s,i);
        cout << res << endl;
    }
    return 0;
}
发表于 2020-08-01 17:33:38 回复(0)
翻滚的后浪头像 翻滚的后浪 
n = int(input())
while n:
    s = input()
    stack = []
    i = 0
    while i<len(s):
        if s[i].isdigit():
            num = s[i]
            i+=1
            while i< len(s) and s[i].isdigit():
                num  = num + s[i]
                i+=1
            pre = stack.pop()
            temp = ''
            if pre.isalpha():
                temp = pre
            elif pre == ')':
                while stack[-1]!='(':
                    temp = stack.pop() + temp
                stack.pop()
            stack += [temp]*int(num)

        else:
            stack.append(s[i])
            i+=1
    n-=1
    print(''.join(stack))

发表于 2020-07-31 23:05:35 回复(0)
Java
HovvYoung头像 HovvYoung
java
遇到 '(' 进入递归，遇到 ')' 将当前递归的结果拼接好返回。一层递归处理一对()内字符串的展开并返回给上一层。 

import java.util.*;

public class Main {
    private static int idx;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        List<String> input = new ArrayList<>();
        while(sc.hasNextLine()) {
            input.add(sc.nextLine());
        }
        for (int i = 0; i < input.size(); i++) {
            idx = 0;
            String res = helper(input.get(i));
            System.out.println(res);
        }
    }

    private static String helper(String str) {
        StringBuilder sb = new StringBuilder();
        int len = str.length();
        if (len == 0) return "";
        char[] array = str.toCharArray();
        while (idx < len) {
            if (array[idx] >= '0' && array[idx] <= '9') {
                int num = 0;
                while (idx < len && array[idx] >= '0' && array[idx] <= '9') {
                    num = num*10 + array[idx++]-'0';
                }
                char prev = sb.charAt(sb.length()-1);
                for (int j = 0; j < num-1; j++) {
                    sb.append(prev);
                }
            } else if (array[idx] == '(') {
                idx++;
                sb.append(helper(str));
            } else if (array[idx] == ')') {
                idx++;
                int num = 0;
                while (idx < len && array[idx] >= '0' && array[idx] <= '9') {
                    num = num*10 + array[idx++]-'0';
                }
                String cpy = sb.toString();
                for (int i=0; i < num-1; i++) {
                    sb.append(cpy);
                }
                return sb.toString();
            } else {
                sb.append(array[idx]);
                idx++;
            }
        }
        return sb.toString();
    }
}


发表于 2020-07-29 08:15:03 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 安全工程师 c#工程师 数据库工程师 猿辅导 2020 大数据开发工程师 Java工程师
上传者：小小
难度：
11条回答 5634浏览

热门推荐

通过挑战的用户

相关试题

解压字符串

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号