Please help me to find a easiest Algorithm for this case

I am working on strings on Julia language. I working on a function where input string format is need to be converted to respective output mentioned below, please help me in finding a easier algorithm for this condition.

Input example:

“aaa[fffff[kkkkk;lllll];ooooo;gggg[nnnnnnn;bbbbbbb]]”



Output should be:



Array{}

[

“aaafffffkkkkk”,

“aaaffffflllll”,

“aaaooooo”,

“aaaggggnnnnnnn”,

“aaaggggbbbbbbb”

]

Thanks

What have you tried so far? Out of curiosity, what are you using this for?

Also, please mention cross-posting: https://stackoverflow.com/questions/63771842/please-help-me-to-find-a-easiest-algorithm-for-this-case

2 Likes

Ok, I got nerd sniped :smile:. It’s not that difficult to write parsers for simple languages like this, with just a little bit of recursion:

parse(s) = _parse!(IOBuffer(s), [""], 0)

function _parse!(io, a, nesting)
    s = a[end]
    while !eof(io)
        c = read(io, Char)
        if c == ']'
            if nesting == 0
                error("Unexpected \"]\"")
            else
                break
            end
        elseif c == ';'
            push!(a, s)
        elseif c == '['
            _parse!(io, a, nesting + 1)
        else
            a[end] *= c
        end
    end
    return a
end

Your example:

julia> parse("aaa[fffff[kkkkk;lllll];ooooo;gggg[nnnnnnn;bbbbbbb]]")
5-element Array{String,1}:
 "aaafffffkkkkk"
 "aaaffffflllll"
 "aaaooooo"
 "aaaggggnnnnnnn"
 "aaaggggbbbbbbb"

Edit: slightly more efficient implementation.

6 Likes

Full marks on the homework :wink:

6 Likes

A longer version :frowning_face: :

struct Node
    prefix::String
    childs::Array{Node,1}
end

function parseNode(s)
    parRanges = findall(x -> x == '[' || x == ']',s)
    if length(parRanges)>0
        pref = s[1:parRanges[1]-1]
        nextString = s[parRanges[1]+1:parRanges[end]-1]
        subStrings = String[]
        openSquared = 0
        lastStripPos = 1
        for (i,c) in enumerate(nextString)
            if c == '[' openSquared += 1; end
            if c == ']' openSquared -= 1; end
            if openSquared == 0 && c == ';'
                sString = nextString[lastStripPos:i-1]
                push!(subStrings,sString)
                lastStripPos = i+1
            end
        end
        if lastStripPos <= length(nextString)
            push!(subStrings,nextString[lastStripPos:end])
        end
        return Node(pref,parseNode.(subStrings))
    else
        Node(s,String[])
    end
end

function joinNode(n)
    toReturn = String[]
    if length(n.childs) >0
        v = n.prefix
        for c in n.childs
            for cchild in joinNode(c)
                push!(toReturn,v*cchild)
            end
        end
        return toReturn
    else
        return [n.prefix]
    end
end

s         = "aaa[fffff[kkkkk;lllll];ooooo;gggg[nnnnnnn;bbbbbbb]]"
rootNode  = parseNode(s);
out       = joinNode(rootNode)
julia> out
5-element Array{String,1}:
 "aaafffffkkkkk"
 "aaaffffflllll"
 "aaaooooo"
 "aaaggggnnnnnnn"
 "aaaggggbbbbbbb"
1 Like

thanks man

thanks bro

thanks bro i was expecting this function kind off solution, thanks it helped me a lot

can u explain u code, caz i am new to julia, it would be easier to understand if u explain like i am lame and i don’t most of ur code, pls

The problem posed seems to be equivalent to the string product:

 "aaa".*["fffff".*["kkkkk";"lllll"];"ooooo";"gggg".*["nnnnnnn";"bbbbbbb"]]

This could be evaluated with metaprogramming after formatting the input as per expression above. See an attempt that seems to be working for type of input indicated:

str = "aaa[ fffff[kkkkk;lllll]; ooooo; gggg[nnnnnnn;bbbbbbb] ]"
s0 = filter(x -> !isspace(x), str)   # remove spaces
s0 = replace(s0,"["=>"\".*[\"")  # add quotes and string product
s0 = replace(s0,";"=>"\";\"")  # add string quotes
s0 = replace(s0,"]"=>"\"]")   # add inner quote before ]
s0 = replace(s0,"]\""=>"]")   # remove quote surplus
s0 = "\"" * s0  # add leading quote
println(s0)  # Julia REPL outputs strings in escaped form, use println to QC
eval(Meta.parse(s0))
1 Like