华为OD题目： 简单的解压缩算法

华为OD题目： 简单的解压缩算法

知识点栈
时间限制: 1s 空间限制: 256MB 限定语言: 不限
题目描述:
现需要实现一种算法，能将一组压缩字符串还原成原始字符串，还原规则如下:1、字符后面加数字N，表示重复字符N次。例如: 压缩内容为A3，表示原始字符串为AAA。2、花括号中的字符串加数字N，表示花括号中的字符串重复N次。例如: 压缩内容为(AB3，表示原始字符串为ABABAB
3、字符加N和花括号后面加N，支持任意的嵌套，包括互相嵌套。例如: 压缩内容可以{A3B1{C}3}3.

输入描述:
输入一行压缩后的宁符串
输出描述
输出压缩前的宁符串
补充说明:
输入保证，数字不会为0，花括号中的内容不会为空，保证输入的都是合法有效的压缩字符串
输入输出字符串区分大小写
输入的字符串长度为范围[1,10000]
输出的字符串长度为范围[1，100000]
数字N范围[1，10000]

示例1
输入:
A3
输出:
AAA
说明:
A3代表A字符重复3次
示例2
输入:
{A3B1{C}3}3
输出:
AAABCCCAAABCCCAAABCCC
说明:
(A3B1C313代表A字符重复3次，B字符重复1次，花括号中的C字符重复3次，最外层花括号中的AAABCCC重复3次

解题思路：

• 使用栈来处理，本题就是逻辑麻烦一些
• 遍历字符数组，如果当前字符是非数字，那么入栈，
• 否则，就向后先把数字获取出来，然后分情况将栈里的字符取出来后，倒序成字符串，再按照数字的倍数拼接

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

/**
 * 简单的解压缩算法
 * 解题思路：
 * 使用栈来处理，本题就是逻辑麻烦一些
 * 遍历字符数组，如果当前字符是非数字，那么入栈，
 * 否则，就向后先把数字获取出来，然后分情况将栈里的字符取出来后，倒序成字符串，再按照数字的倍数拼接
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        char[] chars = line.toCharArray();
        int len = chars.length;
        Deque<Character> stack = new ArrayDeque<>(len);

        int i = 0;
        while (i <= len - 1) {
            char currChar = chars[i];
            //如果不是数字，则入栈
            if (!Character.isDigit(currChar)) {
                stack.push(currChar);
                i++;
                continue;
            }

            //如果是数字
            if (Character.isDigit(currChar)) {
                String str = "";
                //先获取数字前面的字符串
                if (chars[i - 1] == '}') {
                    //取括号里的字符串
                    str = getStrWithMark(stack);
                }else {
                    str = getOnlyLetterStr(stack);
                }
                StringBuilder sbNum = new StringBuilder();
                while (i < len && Character.isDigit(chars[i])) {
                    sbNum.append(chars[i]);
                    i++;
                }
                int n = Integer.parseInt(sbNum.toString());
                //将前面的字符串，n倍拼接
                String s = getNumTimes(str, n);
                //放入栈里面
                for (int j = 0; j < s.length(); j++) {
                    stack.push(s.charAt(j));
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        String string = sb.reverse().toString();
        System.out.println(string);


    }

    //获取数字前面括号里面的内容
    public static String getStrWithMark(Deque<Character> stack) {
        StringBuilder sb = new StringBuilder();
        if (stack.peek() == '}') {
            stack.pop();
        }
        while (stack.peek() != '{') {
            char c = stack.pop();
            sb.append(c);
        }
        if (stack.peek() == '{') {
            stack.pop();
        }
        String s = sb.reverse().toString();
        return s;
    }

    //获取数字前面的字符串
    public static String getOnlyLetterStr(Deque<Character> stack) {
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty() && stack.peek() != '{') {
            char c = stack.pop();
            sb.append(c);
        }
        String s = sb.reverse().toString();
        return s;
    }

    public static String getNumTimes(String s, int n) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(s);
        }
        return sb.toString();
    }

}