Functional Programming: Expressi

Question

from lintcode
Given an expression s includes numbers, letters and brackets. Number represents the number of repetitions inside the brackets(can be a string or another expression)．Please expand expression to be a string.

Example
s = abc3[a] return abcaaa
s = 3[abc] return abcabcabc
s = 4[ac]dy, return acacacacdy
s = 3[2[ad]3[pf]]xyz, return adadpfpfpfadadpfpfpfadadpfpfpfxyz

Idea

This time I am gonna go through the solution with TypeScript but not Java. Why? Cuz I want the code to be clear and easy to understand without being bothered by Java's verbose syntax.

Let's imagine how would you solve this question manually:

You start reading from left and putting down alphabets on the paper.
When you see a number N, you memorize this number, and you look into the string inside the []. You then put down N copies of that string. And then you repeat the same process for the remaining characters after the []

Let's say s = 4[ac]dy
You see 4
  you look into the `[ac]`
      so you write 4 times of `ac`: acacacac
  now you look at letters after the `[ac]`, which is dy
      so you write `dy`
After all, you get `acacacacdy`

What if there are nested []? Like [a3[er]c]. Well, you just have to do the same thing again for the inner block, i.e. you treat a3[er]c as a string and walk through the process first.

How do we code that?

Think of it, each time you see a [] block, you enter a transaction and restart the process. Actually, you can think that the source string is just a string surrounded by a pair of unseen []

So all you have to do is to write a recursive function mimicking this process. Let's give it a name expand.

// pseudo code
given str
expand = f(0).output
where 
f(i) = 
  if str[i] is digit
    {N, digitStopAt} = scanNumber(i)
    trunk = N times of f(digitStopAt + 1).output
    remain = f(f(digitStopAt+ 1).stopAt + 1)
    return { output = trunk + remain.output, stopAt = remain.stopAt }
  else if str[i] is '['
    return { output = f(i + 1).output, stopAt = f(i + 1).stopAt }
  else if str[i] is alphabet
    return { output = str[i] + f(i + 1).output, stopAt = f(i + 1).stopAt }
  else if str[i] is ']'
    return { output = empty string, stopAt = i }
where
scanNumber(i) = { 
  N = integer converted from scanned digit characters from position `i to j`
  digitStopAt = j
}

And below is the solution in TypeScript:

const expressionExpand = function (s) {
    return expand(s, 0).output;
}

function expand(src: string,  position: number): Result {
    if (position >= src.length) {
        return {
            output: empty,
            stopAt: position
        }
    }

    const c = src[position];

    if (c == '[') {
        return expand(src, position + 1);
    } else if (c == ']') {
        return {
            output: empty,
            stopAt: position
        }        
    } else {
        const numTest = scanNum(src, position);
        if (numTest.success) {
            const group = expand(src, numTest.stopAt + 1);
            const remain = expand(src, group.stopAt + 1);
            return {
                output: times(numTest.num, group.output) + remain.output,
                stopAt: remain.stopAt
            }
        } else {
            const remain = expand(src, position + 1);
            return {
                output: c + remain.output,
                stopAt: remain.stopAt
            }
        }
    }
}

interface Result {
    output: string;
    stopAt: number;
}

const empty = '';

function times(t: number, str: string): string {
    let s = ''
    for (let i = 0; i < t; i++)
        s += str
    return s;
}

interface NumScan {
    success: boolean;
    num: number;
    stopAt: number;
}

function scanNum(src: string, position: number): NumScan {
    const c = src[position];
    const isNum = (n) => !isNaN(Number(n))
    if (!isNum(c)) {
        return {
            success: false,
            num: NaN,
            stopAt: position
        }
    } else {
        let numPosEnd = position + 1;
        while (numPosEnd < src.length &&
            isNum(src[numPosEnd])) {
            numPosEnd++;
        }
        return {
            success: true,
            num: Number(src.substring(position, numPosEnd)),
            stopAt: numPosEnd - 1
        }
    }
}



const tests = ['3[2[ad]3[pf]]xyz', '5[10[abcd]Ac20[abcde]]'];
tests.forEach(s => {
    console.log(expressionExpand(s));
})