栈模拟：模拟箱子

2024-02-25 19:20

文章标签 模拟箱子

本文主要是介绍栈模拟：模拟箱子，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一道栈模拟题

这道题与力扣394 字符串解码（https://leetcode.cn/problems/decode-string/description/）非常像，但有些不同。

题目描述

模拟箱子

给定一个字符串，“[]”表示一个箱子，“[]2"表示两个箱子，”[[]2]"表示一个大箱子里有两个小箱子。现在要求解析这个字符串，计算所有的箱子数目。

比如"[] [ [] [] [] 2] 3"表示16个箱子，1+（（4+1）*3）=16

求解

在字符串解码这道题中，如果遇到了嵌套的【】，可以马上将嵌套的【】展平。比如"3[a2[c]]“可以先处理成“3[acc]”，俗称消括号行动。

但是在这道模拟箱子的题目中却不能这么做，为什么？考虑嵌套的括号"[ [ ] ]"，我们能展平为“[ ] [ ]"吗？不能。因为如果后面带上数字，我们就不知道前面到底是一个箱子还是两个箱子。归根结底，字符串解码中括号的作用就是表示一个整体，而模拟箱子中，括号还代表箱子，是需要被记入答案的。

那么怎么做比较好？一种考虑是将空箱子【】用一个符号X替代，遇到一个空箱子我们就把它替换为X。但是这样也不好做，因为嵌套的情况“[ [x] [x] 2]" 我们不好计算箱子数量。

于是我做了一层封装，用一个类表示箱子或“["或“]”，类中再加一个计数count，表示箱子里有多少个箱子。如果遇到嵌套的情况，将箱子里的count叠加，这样就解除了嵌套。

class Box {public String type;public int count; // box 里面有多少个 boxBox(int c, String t){count = c;type = t;}Box(Box b){count = b.count;type = b.type;}
}
public class Main {public static int solve(String str) {int l = 0, r = 0, ans = 0, count = 0;Stack<Box> stk = new Stack<>();for (char ch : str.toCharArray()) {if (ch == '[') {stk.push(new Box(0, "["));} else if (ch == ']'){// 合并箱子int cnt = 0;Box box = stk.pop();while(!box.type.equals("[")){cnt += (1+box.count);box = stk.pop();}stk.push(new Box(cnt, "box"));} else {// 遇到了数字，简便起见，假设数字都是一位数Box box = stk.pop();for(int i=0; i<ch-'0';++i){stk.push(new Box(box));}}}// 计算箱子数量while(!stk.isEmpty()){Box box = stk.pop();count += (1+box.count);}return count;}public static void main(String[] args) {String case1 = "[][][]";String case2 = "[[[]]]";String case3 = "[]2[]3[]";String case4 = "[[[]2]]";String case5 = "[][[][][]2]3";String case6 = "[[[[]2]3]4]";System.out.println(solve(case6));}
}