摘要：當前指針值減一。當前指令的位置。偽內存塊的值，用一個數組表示，默認一個。

原文地址：http://xcoder.in/2014/10/08/brainf**k/

　　首先祝賀自己在 CodeWars 升級到 3 Kyu，以及感謝 @Bolt_白衣蒼狗 童鞋讓我知道有 CodeWars 這么個好玩的東西。

　　雖然里面水題居多，不過在上班比較空閑的檔口 #帶薪刷題# 的感覺還是蠻不錯的。

　　高中的時候就跟 @MatRush 發現了一個名字超級好玩的編程語言叫 BrainF**k，它比較搞腦筋，因為所有的編程操作都是集合在操作符里面，然后控制指針偏移和內存值的修改來進行一系列操作。

　　這與后面發現的 HVM（Hack Virtual Machine）有異曲同工之妙。其實之前也出過一個“實現一個簡易 HVM 解釋器”的題目，所以在 CodeWars 看到這個題目的時候還感覺蠻親切的。

　　問題很簡單，就是讓你實現一個函數來解釋一句 BrainF**k 的語句，并且根據輸入數據來輸出相應的內容。

　　至于這題所需的 BrainF**k 的語法，大致如下：

>: 指針右移一位。

<: 指針左移一位。

+: 當前指針所指的內存值加一，以 255 為界，溢出為 0，即 255 + 1 = 0。

-: 當前指針所指的內存值減一，以 0 為界，溢出為 255，即 0 - 1 = 255。

.: 輸出當前指針所指的值，即輸出該值 ASCII 碼所對應的字符。

,: 從輸入取一個字符轉為 ASCII 碼存入當前指針所指的內存。

[: 若當前指針所指的值為 0，則命令跳到該 [ 匹配的結束 ] 符號位置的下一位置的指令。

]: 若當前指針所指的值不為 0，則指令向前跳到該 ] 匹配到的 [ 符號位置的下一位置的指令。

　　舉個例子：

,+[-.,+]

　　上面的句子大致就是說：

獲取輸入到當前指針。

當前指針值加一。

如果當前指針的值為 0，那么跳到結束位置；否則下一步。

當前指針值減一。

輸出當前指針的值（綜上所述，就是輸出輸入的值）。

獲取輸入到當前指針。

當前指針值加一。

若當前指針值不為 0，那么跳到 [ 后面的位置——即第四步。

　　說白了，就是不斷獲取輸入的值，如果輸入的值是 255，那么就跳出循環，否則原樣輸出。

　　明白了上面的題意之后就可以開始實現了，步驟大致上就是逐位遍歷指令，然后一個 switch 來處理各種指令即可。

　　CodeWars 給了你一個函數原型，你在里面實現代碼就好了：

function brainLuck(code, input){
  return output;
}

　　在開始之前，我們做一些初始化工作，比如申明幾個變量什么的：

輸入數據當前的位置，也就是說讀取幾個之后，這個位置要偏移幾位。

當前指令的位置。

當前指針的位置。

“偽內存塊”的值，用一個數組表示，默認一個 [ 0 ]。

需要 return 的字符串，即輸出的值。

某個括號匹配的括號的指令下標的這么一個映射數組。

　　所以接下去我們要把架子填成這樣：

function brainLuck(code, input) {
    var inputPos = 0;
    var commandPos = 0;
    var pointerPos = 0;
    var bytes = [ 0 ];
    var output = "";
    var matching = getMatchingBra(code);    ///< 人家才不是罩罩呢，我是 Brackets 的縮寫
}

　　上面的 getMatchingBra 就是我們要實現的一個括號匹配函數了，思想就是用棧。

　　碰到前括號就把這個前括號的下標入棧；碰到后括號，就把棧頂元素即前括號的下標推出，這個時候括號匹配數組的這個前括號下標的值就是當前后括號的下標，而后括號下標的值就是前括號的下標了。

/**
 * 你才是 Bra ／/( ???? )＼
 */
function getMatchingBra(code) {
    var stack = [];
    var bra = [];
    for(var i = 0; i < code.length; i++) bra.push(-1);
    for(var i = 0; i < code.length; i++) {
        if(code[i] === "[") {
            stack.push(i);
        } else if(code[i] === "]") {
            bra[i] = stack.pop();
            bra[bra[i]] = i;
        }
    }
    return bra;
}

　　有了這個數組就可以隨便跳了，如果指令第 i 位是一個括號（不管前括號還是后括號），那么它的匹配括號下標就是 matching[i] 了。

　　要處理指令的話實際上就是一個 while 語句不斷循環指令，然后判斷當前指令是什么然后做相應的事，最后指令位置加一就好了：

while(commandPos < code.length) {
    switch(code[commandPos]) {
        case ">": {}
        case "<": {}
        case "+": {}
        case "-": {}
        case ".": {}
        case ",": {}
        case "[": {}
        case "]": {}
    }
    commandPos++;
}

　　指針右移的話就把指針位置加一，如果內存數組還沒當前指針位置的值的話 push 一個 0 就好了：

case ">": {
    if(undefined === bytes[++pointerPos]) bytes.push(0);
    break;
}

　　左移就是減一，如果位置小于 0，那么內存數組從前推入一個值，并讓指針等于 0。

case "<": {
    if(--pointerPos < 0) {
        bytes.unshift(0);
        pointerPos = 0;
    }
    break;
}

　　沒什么好說的，內存加一就好了。

case "+": {
    bytes[pointerPos] = (bytes[pointerPos] + 1) % 256;
    break;
}

　　減一。

case "-": {
    bytes[pointerPos]--;
    if(bytes[pointerPos] < 0) bytes[pointerPos] = 0;
    break;
}

　　輸出的話直接往 output 字符串里面加上當前指針的值就好了，注意要 ASCII 轉變之后的字符。

case ".": {
    output += String.fromCharCode(bytes[pointerPos]);
    break;
}

　　輸入的話就讓 input 當前位置的值變成 ASCII 存進當前指針，然后輸入位置加一就好了。

case ",": {
    bytes[pointerPos] = input.charCodeAt(inputPos++);
    break;
}

　　由于之前已經做好了匹配數組，所以我們只需要判斷當前指針是不是 0，然后如果是就跳到匹配括號處。

case "[": {
    commandPos = !bytes[pointerPos] ? matching[commandPos] : commandPos;
    break;
}

　　同上，只不過條件改一下而已。

case "]": {
    commandPos = bytes[pointerPos] ? matching[commandPos] : commandPos;
    break;
}

　　上面的函數體完成之后，我們只需要在最后把 output 給返回就好了：

return output;

　　完成了上面七零八落的肢體之后，我們要把五馬分尸的代碼給湊回去，所以最后就長這個樣子了：

function getMatchingBra(code) {
    var stack = [];
    var bra = [];
    for(var i = 0; i < code.length; i++) bra.push(-1);
    for(var i = 0; i < code.length; i++) {
        if(code[i] === "[") {
            stack.push(i);
        } else if(code[i] === "]") {
            bra[i] = stack.pop();
            bra[bra[i]] = i;
        }
    }
    return bra;
}

function brainLuck(code, input) {
    var inputPos = 0;
    var commandPos = 0;
    var pointerPos = 0;
    var bytes = [ 0 ];
    var output = "";
    var matching = getMatchingBra(code);

    while(commandPos < code.length) {
        switch(code[commandPos]) {
            case ">": {
                pointerPos++;
                if(undefined === bytes[pointerPos]) {
                    bytes.push(0);
                }
                break;
            }
            case "<": {
                pointerPos--;
                if(0 > pointerPos) {
                    bytes.unshift(0);
                    pointerPos = 0;
                }
                break;
            }
            case "+": {
                bytes[pointerPos] = (bytes[pointerPos] + 1) % 256;
                break;
            }
            case "-": {
                bytes[pointerPos]--;
                if(bytes[pointerPos] < 0) bytes[pointerPos] = 0;
                break;
            }
            case ".": {
                output += String.fromCharCode(bytes[pointerPos]);
                break;
            }
            case ",": {
                var temp = input.charCodeAt(inputPos++);
                bytes[pointerPos] = temp;
                break;
            }
            case "[": {
                if(!bytes[pointerPos]) {
                    commandPos = matching[commandPos];
                }
                break;
            }
            case "]": {
                if(bytes[pointerPos]) {
                    commandPos = matching[commandPos];
                }
                break;
            }
        }
        commandPos++;
    }

    return output;
}

　　艾瑪，忘了放題目鏈接了：http://www.codewars.com/kata/526156943dfe7ce06200063e。以及大家如果有興趣的話也可以去試試看寫個 HVM 看看。

　　實際上本文實現的東西實用性幾乎沒有，只不過是拋磚引玉，讓大家在做一些模擬題邏輯（或者說是簡單模擬邏輯）的時候理清思路、按部就班，切忌自己亂了思路和邏輯。