LeetCode(394&1190)：括号匹配问题（栈）

LeetCode1190:反转每对括号间的子串

题目描述

给出一个字符串 s（仅含有小写英文字母和括号）。

请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果。

注意，您的结果中 不应 包含任何括号。

示例 ： 输入：s = “(abcd)” 输出：“dcba”

输入：s = “(u(love)i)” 输出：“iloveu”

输入：s = “(ed(et(oc))el)” 输出：“leetcode”

解题思路

核心思想就是栈操作 1、当遇到"(“时将未入栈暂存的串str入栈，且将str重置。 2、当遇到”)"时将未入栈暂存的串str反转，再取出并弹出栈顶串，连接到反转后的串str上 3、遇到字母时，添加到未入栈暂存的串str上

代码（c++）

string reverseParentheses(string s) { stack<string> strs; string str; for( int i=0;i<s.size();i++) { if( s[i] == '(') { strs.push(str); str = ""; //str串重置 } else if( s[i] == ')') { reverse(str.begin(),str.end() ); strs.top() += str; str = strs.top(); strs.pop();//反转串，并取出栈顶串和反转串连接 } else str += s[i]; } return str; }

LeetCode394:字符串解码

题目描述

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整 数。 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例: s = “3[a]2[bc]”, 返回 “aaabcbc”. s = “3[a2[c]]”, 返回 “accaccacc”. s = “2[abc]3[cd]ef”, 返回 “abcabccdcdcdef”.

解题思路

双栈，一个数字栈用于记录重复的次数k，一个字符串栈用于记录重复的字符串 思路同上 1、当遇到"[“时将未入栈的字符串str以重复次数num及入栈，并重置。 2、当遇到”]“时将未入栈的字符串str重复k次，这里的是数字栈的栈顶元素，刚好对应前一个”["的数字，再取 出并弹出字符串的栈顶字符串，连接到重复了k次的字符串str上 3、遇到数字或字母，分别添加到未入栈的字符串str或数字num上

代码（c++）

string decodeString(string s) { stack<string> strs; stack<int> nums; string str; int num=0; for(int i=0;i<s.size();i++) { if( s[i]<='9' && s[i]>= '0') num = num*10 + s[i]-'0'; else if( s[i] == '[') { strs.push(str); nums.push(num); str = ""; num =0; } else if( s[i] == ']') // a2[bc] { string tmp = str; // tmp = str = "bc" while( nums.top() > 1) { str += tmp; nums.top()--; } //str = "bcbc" nums.pop(); strs.top() += str; str = strs.top(); //str = "abcbc" strs.pop(); } else str += s[i]; } return str; }