字符串算术运算_虾皮信息笔试题

pein531

用正则表达式将字符串中的中括号和乘号替换为空，并将数字全部提取出来形成倍数列表，利用数字分割字符串形成子串列表。以题中示例来说明算法：

3*[a2*[c]] -> 3a2c

倍数列表：[3,2]

子串列表：[a,c]

初始化结果字符串为res，弹出两个列表的末尾元素2和c，得到首先要将c重复2遍，得cc；再弹出两个列表的末尾元素3和a，将a与上一步的结果cc先拼接，得acc，然后重复3遍，得accaccacc。两个列表此时已经为空了，算法结束。

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

发表于 2021-07-23 20:48:17 回复(1)

牛客995893182号

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;
    }
}

发表于 2021-03-08 19:46:55 回复(0)

ToddGao

由于需要从里到外处理，所以需要用栈的方式处理

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
}

编辑于 2021-05-16 03:01:13 回复(1)

甘13156

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();
    }
};

定义几个栈。

记录状态就好了。如果上一次状态是字母，这一次还是，就和字母栈顶层合并。数字也是同样的操作。

发表于 2021-03-06 15:25:46 回复(0)

filter一切

functioncomputeString( str ) {

let testStr = new RegExp('^[a-zA-Z]+$');

let result = str;

while(!testStr.test(result)){

result = result.replace(/([0-9]+)\*\[([a-zA-Z]+)\]/g,(value,a,b)=>b.repeat(a));

}

return result;

}

编辑于 2021-03-18 02:38:12 回复(1)

HubertZhong

递归

#
# 
# @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

发表于 2022-04-18 18:33:43 回复(0)

wonderson

栈模拟运算

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();
    }
}

发表于 2022-03-28 10:01:32 回复(0)

梦朝彼岸

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);
    }
};

发表于 2022-03-12 00:17:07 回复(0)

C/C++

jr_river

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();
    }
};

发表于 2022-03-09 21:09:02 回复(0)

nevertoolate！

看到字符串+括号就想用栈

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();
    }
}

发表于 2022-03-06 21:53:39 回复(0)

洛洛7389

class Solution:
def computeString(self , string ):
stack = []
items = []
# items_change = []

for char in string:
if char.isdigit() or char.isalpha():
items.append(char)
# print("单独的字符",items)
i = 0
while i<len(items):
if items[i].isdigit():
char = items[i]
i+=1
while i<len(items) and items[i].isdigit():
char += items[i]
i += 1
# print(char)
stack.append(char)
elif items[i].isalpha():
char = items[i]
i+=1
while i<len(items) and items[i].isalpha():
char += items[i]
i +=1
# print(char)
stack.append(char)
else:
stack.append(items[i])

print(stack)

res = ""
a = ""
while stack:
cur = stack.pop()
# print(cur)
if cur.isalpha():
a = cur
print("1",a)
if cur.isdigit():
cur = int(cur)
# print(cur)
b = a+res
x = 0
res=''
while(x<cur):#

res += b
print("2",res)
x +=1
return res

发表于 2022-03-06 21:40:33 回复(0)

--千本樱

def computeString(string):
    stack = []
    res = ""
    for char in string:
        if char.isdigit() or char.isalpha():
            stack.append(char)

    while stack:
        cur = stack.pop()
        if cur.isalpha():
            res = cur + res
        if cur.isdigit():
    return res

发表于 2021-07-14 11:16:22 回复(0)

aliang_keep_up

C++反向遍历字符串，模拟栈处理[]

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;
    }
};

发表于 2021-07-12 17:18:34 回复(0)

有一个地方.

#
#
# @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)

发表于 2021-07-09 21:12:38 回复(0)

木心W

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

发表于 2021-06-29 10:45:59 回复(0)

xxnjl

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);
    }
}

发表于 2021-05-21 11:06:10 回复(0)

牛客220549164号

动态规划

发表于 2021-04-01 08:29:32 回复(0)

Postyear

import re

# python 递归解题

class Solution:

def computeString(self,inputStr):

inputStr = str(inputStr)

K = ''

for index, letter, in enumerate(inputStr):

if letter != '*':

K = K + letter

else:

newstr = inputStr[index+2:-1] # 不含[]

break

num = int(re.sub("\D", "", K)) # 取出字符串中数字

var = ''.join(re.findall(r'[A-Za-z]', K)) # 取出字符串中字符

if '[' in newstr:

the_iter = Solution().computeString(newstr)

return var + the_iter * num

else:

return var + newstr * num

发表于 2021-03-30 09:23:29 回复(0)

煎饼果子w

栈 + 队列 + 暴力repeat字符的方法

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);
    }
}

发表于 2021-03-26 21:11:59 回复(0)

薛原

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;
    }
};

蒟蒻懒得开栈，用的递归，抛砖引玉

发表于 2021-03-08 21:15:45 回复(0)

字符串算术运算

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题