华为OD机试-简单的解压缩算法-2022Q4 A卷-Py/Java/JS

现需要实现一种算法，能将一组压缩字符串还原成原始字符串，还原规则如下：

1、字符后面加数字N，表示重复字符N次。例如：压缩内容为A3，表示原始字符串为AAA。
2、花括号中的字符串加数字N，表示花括号中的字符重复N次。例如压缩内容为{AB}3，表示原始字符串为ABABAB。
3、字符加N和花括号后面加N，支持任意的嵌套，包括互相嵌套，例如：压缩内容可以{A3B1{C}3}3

输入描述：

输入一行压缩后的字符串

输出描述：

输出压缩前的字符串

示例1 输入输出示例仅供调试，后台判题数据一般不包含示例

输入

{A3B1{C}3}3

输出

AAABCCCAAABCCCAAABCCC

说明

{A3B1{C}3}3代表A字符重复3次，B字符重复1次，花括号中的C字符重复3次，最外层花括号中的AAABCCC重复3次。

Java 代码

import java.util.Scanner;
import java.util.*;
import java.util.stream.Collectors;class Main {public static void main(String[] args) {// 处理输入Scanner in = new Scanner(System.in);//防止最后一个字符是数字String str = in.nextLine();Stack<String> stack = new Stack<>();for (int i = 0; i < str.length(); i++) {char c = str.charAt(i);if (c=='{') {stack.push("{");}else if (c=='}') {if (Character.isDigit(str.charAt(i+1))) {int p = i+1;while (p<str.length() && Character.isDigit(str.charAt(p))) p++;int num = Integer.parseInt(str.substring(i+1,p));StringBuilder sb = new StringBuilder();while (!stack.peek().equals("{")){String s = stack.pop();sb.append(s);}stack.pop();stack.push(repeat(sb.toString(), num));i = p-1;}}else if (Character.isAlphabetic(c)){if (Character.isDigit(str.charAt(i+1))) {int p = i+1;while (p<str.length() && Character.isDigit(str.charAt(p))) p++;int num = Integer.parseInt(str.substring(i+1,p));stack.push(repeat(c+"",num));i = p-1;}else {stack.push(c+"");}}}StringBuilder sb = new StringBuilder();while (!stack.isEmpty()) {sb.append(stack.pop());}String str0 = sb.toString();sb = new StringBuilder();for (int i = str0.length()-1; i >=0 ; i--) {sb.append(str0.charAt(i));}System.out.println(sb.toString());}public static String repeat(String str, int num) {StringBuilder sb = new StringBuilder();for (int i = 0; i < num; i++) {sb.append(str);}return sb.toString();}}

Python代码

import functools
import collections
import mathdef repeat_operation(stack,pos,repeat_count):count = len(stack) - pos# temp_stack用于存储弹栈数据temp_stack = [0 for x in range(count)]while (count >= 1):count -= 1temp_stack[count] = stack.pop()temp_str = "".join(temp_stack)result = ""#重复repeat_count次for i in range(repeat_count):result += temp_strstack.append(result);#处理输入
input_str = input() + " "
stack = []
# bracket_pos 保存的是所有花括号出现的位置
bracket_pos = []
number_str = ""for i in range(len(input_str)):c = input_str[i]if (c >= '0' and c <= '9'): number_str += ccontinue#数字if (len(number_str)>0): repeat_count = int(number_str) number_str = ""# 若此时栈顶是 } 字符, 将对应的字母重复repeat_count次if (stack[-1] == "}"): #获取上一个{的位置pos = bracket_pos.pop()#删除左右{stack.pop(pos) stack.pop()# 重复{之间的字母repeat_operation(stack, pos, repeat_count) else: #不是 } 字符, 简单重复栈顶字符对应次即可repeat_operation(stack, len(stack) - 1, repeat_count)#{ 字符if (c == '{'):bracket_pos.append(len(stack))# 其他字符 (字母 + )stack.append(c + "")# 输出
print("".join(stack)) 

JS代码

function main(input_str) {input_str += " ";let normal_chars = new Array()let bracket_pos  = new Array()let numbers = new Array()for (let i=0;i<input_str.length;i++) {//是否为数字if (/\\d/.test(input_str[i])) {numbers.push(input_str[i]);continue;}// 若当前字符不是数字，且数字数组长度大于0if (numbers.length > 0) {let real_count = parseInt(numbers.join(""));let top = normal_chars.pop()if (top === "}") {let inside_str = normal_chars.splice(bracket_pos.pop()).slice(1).join("");normal_chars.push(...new Array(real_count).fill(inside_str).join(""));} else {normal_chars.push(...new Array(real_count).fill(top));}numbers = []}// 左花括号if (input_str[i] === "{") {bracket_pos.push(normal_chars.length);}// 正常字符normal_chars.push(input_str[i]);}console.log(normal_chars.join("").trim()) 
}main("{A3B1{C}3}3")