用 Javascript 實(shí)現(xiàn)一個(gè)簡(jiǎn)易 BrainF**k 解釋器

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

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

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

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

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

話嘮一下

　　高中的時(shí)候就跟 @MatRush 發(fā)現(xiàn)了一個(gè)名字超級(jí)好玩的編程語(yǔ)言叫 BrainF**k，它比較搞腦筋，因?yàn)樗械木幊滩僮鞫际羌显诓僮鞣锩?，然后控制指針偏移和?nèi)存值的修改來(lái)進(jìn)行一系列操作。

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

問(wèn)題描述

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

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

>: 指針右移一位。

<: 指針左移一位。

+: 當(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 碼所對(duì)應(yīng)的字符。

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

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

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

　　舉個(gè)例子：

,+[-.,+]

　　上面的句子大致就是說(shuō)：

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

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

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

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

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

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

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

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

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

開始實(shí)現(xiàn)

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

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

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

前趨工作

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

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

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

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

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

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

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

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

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

括號(hào)匹配函數(shù)

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

　　碰到前括號(hào)就把這個(gè)前括號(hào)的下標(biāo)入棧；碰到后括號(hào)，就把棧頂元素即前括號(hào)的下標(biāo)推出，這個(gè)時(shí)候括號(hào)匹配數(shù)組的這個(gè)前括號(hào)下標(biāo)的值就是當(dāng)前后括號(hào)的下標(biāo)，而后括號(hào)下標(biāo)的值就是前括號(hà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;
}

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

各種指令的處理

　　要處理指令的話實(shí)際上就是一個(gè) while 語(yǔ)句不斷循環(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ù)組還沒(méi)當(dāng)前指針位置的值的話 push 一個(gè) 0 就好了：

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

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

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

　　沒(méi)什么好說(shuō)的，內(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 存進(jìn)當(dāng)前指針，然后輸入位置加一就好了。

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

[

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

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

]

　　同上，只不過(guò)條件改一下而已。

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

善后工作

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

return output;

肢體組裝

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

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

題后語(yǔ)

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

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