用 Javascript 實現(xiàn)一個簡易 BrainF**k 解釋器

littleGrow 發(fā)布于2019-08-21 12:30 / 2606人閱讀

摘要：當(dāng)前指針值減一。當(dāng)前指令的位置。偽內(nèi)存塊的值，用一個數(shù)組表示，默認(rèn)一個。

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

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

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

話嘮一下

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

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

問題描述

　　問題很簡單，就是讓你實現(xiàn)一個函數(shù)來解釋一句 BrainF**k 的語句，并且根據(jù)輸入數(shù)據(jù)來輸出相應(yīng)的內(nèi)容。

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

>: 指針右移一位。

<: 指針左移一位。

+: 當(dāng)前指針?biāo)傅膬?nèi)存值加一，以 255 為界，溢出為 0，即 255 + 1 = 0。

-: 當(dāng)前指針?biāo)傅膬?nèi)存值減一，以 0 為界，溢出為 255，即 0 - 1 = 255。

.: 輸出當(dāng)前指針?biāo)傅闹?，即輸出該?ASCII 碼所對應(yīng)的字符。

,: 從輸入取一個字符轉(zhuǎn)為 ASCII 碼存入當(dāng)前指針?biāo)傅膬?nèi)存。

[: 若當(dāng)前指針?biāo)傅闹禐?0，則命令跳到該 [ 匹配的結(jié)束 ] 符號位置的下一位置的指令。

]: 若當(dāng)前指針?biāo)傅闹挡粸?0，則指令向前跳到該 ] 匹配到的 [ 符號位置的下一位置的指令。

　　舉個例子：

,+[-.,+]

　　上面的句子大致就是說：

獲取輸入到當(dāng)前指針。

當(dāng)前指針值加一。

如果當(dāng)前指針的值為 0，那么跳到結(jié)束位置；否則下一步。

當(dāng)前指針值減一。

輸出當(dāng)前指針的值（綜上所述，就是輸出輸入的值）。

獲取輸入到當(dāng)前指針。

當(dāng)前指針值加一。

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

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

開始實現(xiàn)

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

　　CodeWars 給了你一個函數(shù)原型，你在里面實現(xiàn)代碼就好了：

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

前趨工作

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

輸入數(shù)據(jù)當(dāng)前的位置，也就是說讀取幾個之后，這個位置要偏移幾位。

當(dāng)前指令的位置。

當(dāng)前指針的位置。

“偽內(nèi)存塊”的值，用一個數(shù)組表示，默認(rèn)一個 [ 0 ]。

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

某個括號匹配的括號的指令下標(biāo)的這么一個映射數(shù)組。

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

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

括號匹配函數(shù)

　　上面的 getMatchingBra 就是我們要實現(xiàn)的一個括號匹配函數(shù)了，思想就是用棧。

　　碰到前括號就把這個前括號的下標(biāo)入棧；碰到后括號，就把棧頂元素即前括號的下標(biāo)推出，這個時候括號匹配數(shù)組的這個前括號下標(biāo)的值就是當(dāng)前后括號的下標(biāo)，而后括號下標(biāo)的值就是前括號的下標(biāo)了。

/**
 * 你才是 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;
}

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

各種指令的處理

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

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

　　指針右移的話就把指針位置加一，如果內(nèi)存數(shù)組還沒當(dāng)前指針位置的值的話 push 一個 0 就好了：

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

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

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

　　沒什么好說的，內(nèi)存加一就好了。

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

　　減一。

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

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

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

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

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

[

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

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

]

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

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

善后工作

　　上面的函數(shù)體完成之后，我們只需要在最后把 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 看看。

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