394字符串解码

一、前言

标签&＃xff1a;栈。

问题来源LeetCode 394 难度&＃xff1a;中等。

问题链接&＃xff1a;https://leetcode-cn.com/problems/decode-string/

二、题目

给定一个经过编码的字符串&＃xff0c;返回它解码后的字符串。编码规则为: k[encoded_string]&＃xff0c;表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。你可以认为输入字符串总是有效的&＃xff1b;输入字符串中没有额外的空格&＃xff0c;且输入的方括号总是符合格式要求的。此外&＃xff0c;你可以认为原始数据不包含数字&＃xff0c;所有的数字只表示重复的次数 k &＃xff0c;例如不会出现像 3a 或 2[4] 的输入。

示例 1&＃xff1a;

输入&＃xff1a;s &＃61; "3[a]2[bc]"
输出&＃xff1a;"aaabcbc"

示例 2&＃xff1a;

输入&＃xff1a;s &＃61; "3[a2[c]]"
输出&＃xff1a;"accaccacc"

示例 3&＃xff1a;

输入&＃xff1a;s &＃61; "2[abc]3[cd]ef"
输出&＃xff1a;"abcabccdcdcdef"

示例 4&＃xff1a;

输入&＃xff1a;s &＃61; "abc3[cd]xyz"
输出&＃xff1a;"abccdcdcdxyz"

三、思路

当看到括号&＃xff0c;首先应该想到的就是用栈来解决问题。

四、编码实现

//&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;
/*
* &＃64;file : 394_DecodeString.h
* &＃64;label : 栈
* &＃64;blogs : https://blog.csdn.net/nie2314550441/article/details/107522595
* &＃64;author : niebingyu
* &＃64;date : 2020/07/21
* &＃64;title : 394.字符串解码
* &＃64;purpose : 给定一个经过编码的字符串&＃xff0c;返回它解码后的字符串。
* 编码规则为: k[encoded_string]&＃xff0c;表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
* 你可以认为输入字符串总是有效的&＃xff1b;输入字符串中没有额外的空格&＃xff0c;且输入的方括号总是符合格式要求的。
* 此外&＃xff0c;你可以认为原始数据不包含数字&＃xff0c;所有的数字只表示重复的次数 k &＃xff0c;例如不会出现像 3a 或 2[4] 的输入。
*
* 示例1&＃xff1a;
* 输入&＃xff1a;s &＃61; "3[a]2[bc]"
* 输出&＃xff1a;"aaabcbc"
*
* 示例2&＃xff1a;
* 输入&＃xff1a;s &＃61; "3[a2[c]]"
* 输出&＃xff1a;"accaccacc"
*
* 示例3&＃xff1a;
* 输入&＃xff1a;s &＃61; "2[abc]3[cd]ef"
* 输出&＃xff1a;"abcabccdcdcdef"
*
* 示例 4&＃xff1a;
* 输入&＃xff1a;s &＃61; "abc3[cd]xyz"
* 输出&＃xff1a;"abccdcdcdxyz"
*
* 来源&＃xff1a;力扣&＃xff08;LeetCode&＃xff09;
* 难度&＃xff1a;中等
* 链接&＃xff1a;https://leetcode-cn.com/problems/decode-string/
*/
//&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;
#pragma once
#include
#include
#include
#include
#include
using namespace std;#define NAMESPACE_DECODESTRING namespace NAME_DECODESTRING {
#define NAMESPACE_DECODESTRINGEND }
NAMESPACE_DECODESTRINGclass Solution
{
public:string decodeString(string s) {string res &＃61; "";stack nums;stack strs;int num &＃61; 0;int len &＃61; s.size();for(int i &＃61; 0; i &＃61; &＃39;0&＃39; && s[i] <&＃61; &＃39;9&＃39;)num &＃61; num * 10 &＃43; s[i] - &＃39;0&＃39;;else if((s[i] >&＃61; &＃39;a&＃39; && s[i] <&＃61; &＃39;z&＃39;) ||(s[i] >&＃61; &＃39;A&＃39; && s[i] <&＃61; &＃39;Z&＃39;))res &＃61; res &＃43; s[i];else if(s[i] &＃61;&＃61; &＃39;[&＃39;) {// 将‘[’前的数字压入nums栈内&＃xff0c; 字母字符串压入strs栈内nums.push(num);num &＃61; 0;strs.push(res); res &＃61; "";}else {// 遇到‘]’时&＃xff0c;操作与之相配的‘[’之间的字符&＃xff0c;使用分配律int times &＃61; nums.top();nums.pop();for(int j &＃61; 0; j };以下为测试代码//
// 测试 用例 START
void test(const char* testName, string str, string expect)
{Solution s;string result &＃61; s.decodeString(str);if (result &＃61;&＃61; expect)cout <}// 测试用例
void Test1()
{string str &＃61; "3[a]2[bc]";string expect &＃61; "aaabcbc";test("Test1()", str, expect);
}void Test2()
{string str &＃61; "3[a2[c]]";string expect &＃61; "accaccacc";test("Test2()", str, expect);
}void Test3()
{string str &＃61; "2[abc]3[cd]ef";string expect &＃61; "abcabccdcdcdef";test("Test3()", str, expect);
}void Test4()
{string str &＃61; "abc3[cd]xyz";string expect &＃61; "abccdcdcdxyz";test("Test4()", str, expect);
}
NAMESPACE_DECODESTRINGEND
// 测试 用例 END
//
void DecodeString_Test()
{cout <<"------ start 394.字符串解码 ------" <}

执行结果&＃xff1a;