3*[a2*[c]] -> 3a2c倍数列表:[3,2]
import re class Solution: def computeString(self , s): # write code here s = re.sub("[\*\[\]]", "", s) res = "" n = len(s) times = list(map(int, re.findall("[0-9]+", s))) substrs = re.split('[0-9]+', s) if substrs[0] == "": substrs = substrs[1:] while times: res = substrs.pop() + res res = times.pop() * res return res
import java.util.*; public class Solution { /** * * @param str string字符串 * @return string字符串 */ public String computeString (String str) { // write code here StringBuilder sb=new StringBuilder(""); char ch[]=str.toCharArray(); helper(sb,ch,0,1); return sb.toString(); } public int helper(StringBuilder sb, char[] ch, int index, int k){ int nextK=0; StringBuilder sb1=new StringBuilder(""); while(index<ch.length){ if(ch[index]==']'){ StringBuilder sb2=new StringBuilder(sb1); for(int i=0;i<k-1;i++){ sb1.append(sb2); } sb.append(sb1); return index; } else if(ch[index]>=48&&ch[index]<=57){ nextK=10*nextK+ch[index]-48; } else if(ch[index]=='['){ index=helper(sb1,ch,index+1,nextK); } else if(ch[index]!='*'){ sb1.append(ch[index]); } index++; } sb.append(sb1); return index; } }
由于需要从里到外处理,所以需要用栈的方式处理
package main import "strings" import "strconv" /** * * @param str string字符串 * @return string字符串 */ func computeString( str string ) string { // write code here strStack := []string{} numStack := []int{} num, res := 0, "" for _, char := range str { if char >= '0' && char <= '9' { n, _ := strconv.Atoi(string(char)) num = num * 10 + n } else if char == '[' { strStack = append(strStack, res) numStack = append(numStack, num) num, res = 0, "" } else if char == ']' { str := strStack[len(strStack)-1] count := numStack[len(numStack)-1] strStack = strStack[:len(strStack)-1] numStack = numStack[:len(numStack)-1] res = str + strings.Repeat(res, count) } else if char == '*'{ continue } else { res += string(char) } } return res }
class Solution { public: /** * * @param str string字符串 * @return string字符串 */ // 0 数字 // 1 * // 2 【】 // 3 字母 int state = 0; string computeString(string str) { // write code here stack<int> shuzi; stack<char> chenghao; stack<char> kuohao; stack<string> zimu; for (int i = 0; i < str.size(); ++i) { if (str[i] <= '9' && str[i] >= '0') { if (state == 0 && !shuzi.empty()) { int t = shuzi.top(); shuzi.pop(); t = t * 10 + str[i] - '0'; shuzi.push(t); } else { shuzi.push(str[i] - '0'); } state = 0; } else if (str[i] == '*') { state = 1; chenghao.push(str[i]); } else if (str[i] <= 'z' && str[i] >= 'a') { if (state == 3 && !zimu.empty()) { string t = zimu.top(); zimu.pop(); t = t + str[i]; zimu.push(t); } else { string t = ""; t += str[i]; zimu.push(t); } state = 3; } else if (str[i] == '[') { kuohao.push(str[i]); state = 2; } else if (str[i] == ']') { kuohao.pop(); chenghao.pop(); int t = shuzi.top(); string s = zimu.top(); string res = ""; shuzi.pop(); zimu.pop(); for (int i = 0; i < t; ++i) { res += s; } if (zimu.empty()) zimu.push(res); else { string t = zimu.top(); zimu.pop(); t += res; zimu.push(t); } } } return zimu.top(); } };
# # # @param str string字符串 # @return string字符串 # class Solution: def computeString(self , str ): # write code here if str==""&nbs***bsp;str[0]=="]": return "" val=0 obj="" for i in range(len(str)): if str[i].isdigit(): val=val*10+int(str[i]) elif str[i]=="[": return obj+val*self.computeString(str[i+1:]) elif str[i].isalpha(): obj+=str[i] return obj
import java.util.*; public class Solution { public String computeString (String str) { char[] cs = str.toCharArray(); int n = cs.length; String[] strs = new String[n]; Stack<Integer> nums = new Stack<>(); int idx = -1; for (char c: cs) { if (c == '*') { //取出前面的数字 int num = 0; int d = 1; while (idx >= 0 && strs[idx].matches("^[0-9]$")) { //取出栈顶所有的单个数字 int t = Integer.parseInt(strs[idx--]); num += (t * d); d *= 10; } nums.push(num); } else if (c == ']') { //进行一轮运算 StringBuilder sb = new StringBuilder(); while (!"[".equals(strs[idx])) { sb.insert(0, strs[idx--]); } idx--; //[出栈 int num = nums.pop(); String tmp = sb.toString(); for (int i = 1; i < num; i++) { sb.append(tmp); } //重新加入到栈顶 strs[++idx] = sb.toString(); } else { //普通字符、数字和[直接入栈 strs[++idx] = String.valueOf(c); } } StringBuilder sb = new StringBuilder(); while (idx >= 0) { sb.insert(0, strs[idx--]); } return sb.toString(); } }
class Solution { public: /** * * @param str string字符串 * @return string字符串 */ // 3*[a2*[c]] // accaccacc stack<string> ch; stack<int> num; stack<char> op; string computeString(string str) { for (int i = 0; i < str.size(); i++) { char c = str[i]; if (isdigit(c)) { int j = i, x = 0; while (j < str.size() && isdigit(str[j])){ x = x * 10 + str[j] - '0'; j++; } num.push(x); i = j - 1; } else if (c == '[') { op.push(c); } else if (c == ']') { while (op.size() && op.top() != '[') eval(); op.pop(); } else if (c == '*') { op.push(c); } else { int j = i; string x; while (j < str.size() && (str[j] != '[' && str[j] != ']' && !isdigit(str[j]) && str[j] != '*')) j++; ch.push(str.substr(i, j - i)); if (j < str.size() && isdigit(str[j])) op.push('|'); i = j - 1; } } while (op.size()) eval(); return ch.top(); } void eval() { char c = op.top(); op.pop(); string res; if (c == '*') { int a = num.top(); num.pop(); string b = ch.top(); ch.pop(); while (a--) { res += b; } } else { string b = ch.top(); ch.pop(); string d = ch.top(); ch.pop(); res = d + b; } ch.push(res); } };
class Solution { public: /** * * @param str string字符串 * @return string字符串 */ string computeString(string str) { // write code here //字母 stack<string> c; //数字 stack<int> n; //结果 stack<string> res; //int q; for(int k = 0; k < str.size(); k++){ //if(isalpha(str[k])) c.push(str[k]); int q = 1; int sum = 0; string h1 =""; while(str[k] - '0' >= 0 && str[k] - '0' <= 9){ sum *= q; sum += str[k] - '0'; q *= 10; k++; } if(sum != 0) n.push(sum); while(isalpha(str[k])){ h1 += str[k]; k++; } if(h1 != ""){ c.push(h1); k--; } if(str[k] == ']') break; } while(!n.empty() && !c.empty()){ int i = n.top(); n.pop(); string j = c.top(); c.pop(); if(!res.empty()){ string k ; //res.pop(); string k2; k2 += j; k2 += res.top(); res.pop(); for(int l = 0; l < i; l++){ k += k2; } res.push(k); } else{ string k; for(int l = 0; l < i; l++){ k += j; } res.push(k); } } return res.top(); } };
import java.util.*; public class Solution { /** * * @param str string字符串 * @return string字符串 */ public String computeString (String str) { // write code here Stack s=new Stack(); String num=""; for(int i=0; i<str.length();i++ ){ //是数字,把后面一段数字变放进去 if(Character.isDigit(str.charAt(i))){ while(i<str.length()&&Character.isDigit(str.charAt(i))){ num+=str.charAt(i); i++; } s.push(Integer.parseInt(num)); num=""; }else if(Character.isLetter(str.charAt(i))){ //是字符,把后面一段字符都放进去 while(i<str.length()&&Character.isLetter(str.charAt(i))){ num+=str.charAt(i); i++; } i--; s.push(num); num=""; }else if('['==str.charAt(i)){ s.push("]"); }else { StringBuilder ss=new StringBuilder(); StringBuilder temp=new StringBuilder(); while (s.size()!=0 && (String)s.peek()!="]"){ temp.insert(0,s.pop()); } //弹出"]" s.pop(); //接收数字 int count=(int)s.pop(); for (int j = 0; j < count; j++) { ss.append(temp); } s.push(ss.toString()); } } return (String)s.peek(); } }
class Solution { public: /** * * @param str string字符串 * @return string字符串 */ string computeString(string str) { // write code here string tmp; int len = str.length(); for(int i = len - 1; i >= 0;) { if (str[i] == ']') { i--; continue; } else if (str[i] >= 'a' && str[i] <= 'z') { tmp = str[i] + tmp; i--; } else if (str[i] == '[') { assert(--i >= 0 && str[i] == '*'); assert(--i >= 0 && str[i] >= '0' && str[i] <= '9'); int num = 0; int fac = 1; while (i >= 0 && str[i] >= '0' && str[i] <= '9') { num = num + (str[i] - '0') * fac; i--; fac *= 10; } string ans; for (int i = 0; i < num; i++) { ans += tmp; } cout << ans << endl; tmp = ans; } } return tmp; } };
# # # @param str string字符串 # @return string字符串 # class Solution: def computeString(self , str ): # write code here n = len(str) num_stack = [] ch_stack = [] i = 0 while i < n: if str[i].isdigit(): res = 0 while i < n and str[i].isdigit(): res = res * 10 + int(str[i]) i += 1 num_stack.append(res) if str[i] == '*': i += 1 continue if str[i] == '[': ch_stack.append('[') i += 1 continue if str[i].isalpha(): ch_stack.append(str[i]) i += 1 continue if str[i] == ']': tmp = "" while ch_stack and ch_stack[-1] != '[': tmp = ch_stack[-1] + tmp ch_stack.pop() if ch_stack and ch_stack[-1] == '[': ch_stack.pop() if num_stack: tmp = tmp * num_stack[-1] num_stack.pop() for c in tmp: ch_stack.append(c) i += 1 return "".join(ch_stack)
class Solution { public: /** * * @param str string字符串 * @return string字符串 */ bool isnum(char c) { return c >= '0' && c <= '9'; } string parse(int& i, const string& s) { string t; while (true) { if (i == s.size() || s[i] == ']') break; if (isnum(s[i])) { int k = i; while (isnum(s[i])) i++; int num = stoi(s.substr(k, i-k)); i += 2; string sub = parse(i, s); i++; for (int j = 0; j < num; j++) t += sub; } else { t += s[i]; i++; } } return t; } string computeString(string str) { // write code here int i = 0; return parse(i, str); } };递归parser
import java.util.*; import java.util.regex.*; public class Solution { /** * * @param str string字符串 * @return string字符串 */ public static String func(int x, String str){ StringBuilder sb = new StringBuilder(); for(int i = 0; i < x; i++){ sb.append(str); } return sb.toString(); } public static String computeString (String str) { // write code here if(!str.contains("[")){ return str; } String result = str; Pattern pattern = Pattern.compile("(\\d*)\\*\\[([^\\[\\]]*)\\]"); Matcher matcher = pattern.matcher(result); while(matcher.find()){ result = result.replaceFirst("(\\d*)\\*\\[([^\\[\\]]*)\\]", func(Integer.parseInt(matcher.group(1)), matcher.group(2))); } return computeString(result); } }
import java.util.*; public class Solution { /** * * @param str string字符串 * @return string字符串 */ public String computeString (String str) { // write code here char[] sc = str.toCharArray(); int n = sc.length; char[] ch = new char[1_0000_0000]; int topChar = -1; int[] num = new int[n]; int topNum = -1; Deque<Character> queue = new ArrayDeque<>(); for (int i = 0; i < n; ++i) { if(Character.isDigit(sc[i])){ int t = sc[i] - '0'; while (Character.isDigit(sc[++i])){ t = t * 10 + sc[i] - '0'; } num[++topNum] = t; } else if (sc[i] == ']') { // repeat num[topNum] times while (ch[topChar] != '[') { queue.push(ch[topChar--]); } // pop [ topChar--; // repeat int k = num[topNum--]; for (int j = 0; j < k; ++j) { for (Character c : queue) { ch[++topChar] = c; } } queue.clear(); } else { ch[++topChar] = sc[i]; } } return new String(ch, 0, topChar + 1); } }
class Solution { public: /** * * @param str string字符串 * @return string字符串 */ int pos=0; string tostr(string s) { string cc=""; while(s[pos]!=']'&&pos<s.length()){ if(islower(s[pos])){ while(islower(s[pos])) { cc+=s[pos];pos++; } //cout<<cc<<endl; }else if(isdigit(s[pos])) { cc+=fun(s); //cout<<cc<<endl; } } return cc; } string fun(string s){ string res=""; int num=0; while(isdigit(s[pos])) { num=num*10+s[pos]-'0'; pos++; } //cout<<num<<endl; pos+=2; string sx=tostr(s); for(int i=0; i<num; i++) { res+=sx; } return res; } string computeString(string str) { // write code here int le=str.length(); string ans=""; for(pos=0; pos<le; pos++) { if(str[pos]>='a'&&str[pos]<='z') { ans+=str[pos]; //cout<<ans<<endl; }else if(str[pos]>='0'&&str[pos]<='9') { ans+=fun(str); //cout<<ans<<endl; } } return ans; } };