Brainfuck 解释器(一)


  • 0
    administrators

    Brainfuck,是一种极小化的计算机语言,它是由 Urban Müller 在1993年创建的。由于 fuck 在 英语中是脏话,这种语言有时被称为 Brainf*ck 或 Brainf***,甚至被简称为 BF。

    Müller 的目标是创建一种简单的、可以用最小的编译器来实现的、匹配图灵完全思想的编程语言。这种语言由八种运算符构成, 为 Amiga 机器编写的编译器(第二版)只有 240个 字节大小。

    就象它的名字所暗示的,Brainfuck 程序很难读懂。尽管如此,Brainfuck 图灵机一样可以完成任何计算任务。虽然 Brainfuck 的计算方式如此与众不同,但它确实能够正确运行。

    这种语言基于一个简单的机器模型,除了指令,这个机器还包括:一个以字节为单位、被初始化为零的数组、一个指向该数组的指针(初始时指向数组的第一个字节)、以及用于输入输出的两个字节流。

    下面是这八种状态的描述,其中每个状态由一个字符标识:

    字符 含义
    > 指针加一
    < 指针减一
    + 指针指向的字节的值加一
    - 指针指向的字节的值减一
    . 输出指针指向的单元内容(ASCII码)
    , 输入内容到指针指向的单元(ASCII码)
    [ 如果指针指向的单元值为零,向后跳转到对应的 ] 指令的次一指令处
    ] 如果指针指向的单元值不为零,向前跳转到对应的 [ 指令的次一指令处

    (按照更节省时间的简单说法,] 也可以说成“向前跳转到对应的 [ 状态”。这两解释是一样的。)

    (第三种同价的说法,[ 意思是"向后跳转到对应的 ] ",] 意思是"向前跳转到对应的 [ 指令的次一指令处,如果指针指向的字节非零。")

    你需要实现一个 brainFuck 方法,该方法接收两个参数,第一个参数为 brainFuck 代码,第二个参数为输入内容(字符串),返回值即输出内容。例如:

    brainFuck('++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.', '') // Hello World!
    brainFuck(',[.[-],]', '2333' + String.fromCharCode(0)) // 2333
    brainFuck(',>,<[>[->+>+<<]>>[-<<+>>]<<<-]>>.', String.fromCharCode(2, 3)) //乘法 2 * 3 = 5
    

    (具体例子可以到 Brainfuck 上查看)


  • 0

    const brainFuck = (code, input) => {
    	var cp=0,ip=0,mp=0,m=[0],r='';
    	eval(code
    		.replace(/\]/g,'}')
    		.replace(/\[/g,"while(m[mp]!=0){")
    		.replace(/\++/g,function(x){return 'm[mp]+='+x.length+';'})
    		.replace(/\-+/g,function(x){return 'm[mp]-='+x.length+';'})
    		.replace(/\./g,'r+=String.fromCharCode(m[mp]);')
    		.replace(/,/g,'m[mp]=input.charCodeAt(ip);ip+=1;')
    		.replace(/>+/g,function(x){return 'mp+='+x.length+';while(mp>=m.length)m.push(0);'})
    		.replace(/<+/g,function(x){return 'mp-='+x.length+';'})
    		.replace(/while\(m\[mp\]!=0\)\{m\[mp\]-=1;\}/,'m[mp]=0;')
    	);
    	return r;
    }
    
    function brainFuck(code,input){
    	var cp=0;
    	var op=0;
    	var ip=0;
    	var mp=0;
    	var m=[0];
    	var r='';
    	var g=0;
    	var j={};
    	for(cp=0;cp<code.length;cp++){
    		switch(code[cp]){
    			case '>':
    				mp+=1;
    				if(m.length==mp)m.push(0);
    				break;
                case '<':
    				mp-=1;
    				break;
                case '+':
    				m[mp]+=1;
    				break;
                case '-':
    				m[mp]-=1;
    				break;
                case '.':
    				r+=String.fromCharCode(m[mp]);
    				break;
                case ',':
    				m[mp]=input.charCodeAt(ip);
    				ip+=1;
    				break;
                case '[':
    				if(m[mp]==0){
                        if(j[cp]==undefined){
                            op=cp;
                            g=1;
                            while(g!=0){
                            	if(code[cp+1]==']')g-=1;if(code[cp+1]=='[')g+=1;cp++;
    						};
    						j[op]=cp;
                        }
    					else{cp=j[cp];}
                    }
    				break;
                case ']':
    				if(m[mp]!=0){
                        if(j[cp]==undefined){
                            op=cp;
                            g=1;
                            while(g!=0){
    							if(code[cp-1]=='[')g-=1;if(code[cp-1]==']')g+=1;cp--;
    						};
    						j[op]=cp;
                        }
    					else{cp=j[cp];}
                    }
    				break;	
    		}
    	}
    	return r;
    }
    

    一堆case加中括号对应查找超时我可以理解
    正则替换+eval超时无法理解了
    本地测试一切OK

    const brainFuck = (code, input) => {
    	var cp=0,ip=0,mp=0,m=[0],r='';
    	eval(code.replace(/(\[-\]|\[|\]|\++|\-+|\.|\,|>+|<+)/g,
    		(x)=>{
    			if(x[0]=='>')return 'mp+='+x.length+';while(mp>=m.length)m.push(0);';
    			if(x[0]=='<')return 'mp-='+x.length+';';
    			if(x[0]=='+')return 'm[mp]=(m[mp]+'+x.length+')&255;';
    			if(x[0]=='-')return 'm[mp]=(m[mp]-'+x.length+')&255;';
    			if(x=='.')return 'r+=String.fromCharCode(m[mp]);';
    			if(x==',')return 'm[mp]=input.charCodeAt(ip++);'
    			if(x=='[')return "while(m[mp]){";
    			if(x==']')return "}";
    			if(x=='[-]')return 'm[mp]=0;';
    		})
    	);
    	return r;
    }
    

    坑爹的1byte数组


  • 1

    终于找到问题了,坑


  • 0
    administrators

    @elfish 第一个做出这道题的人


  • 0

    expected 'Q57a-:&C9qnlai3ÿ' to deeply equal 'Q57a-:&C9qnlai3'

    expected '3Q_VB>R\'}-LmIdvÿ' to deeply equal '3Q_VB>R\'}-LmIdv'

    这种错误信息根本没法调试啊?

    直接帖答案吧,自测的示例都通过了,用 Proxy 提示超时,可以改一下不用 Proxy,注释里是犯懒的写法,大哈帮忙看下怎么才能通过 @ScriptOJ :

    // solution.ts
    
    const closePos = (str: string, start: number = 0, depth = 0): number => {
      for (let [i, s] of str.slice(start).split('').entries()) {
        if (s === ']') return depth ? closePos(str, start + i + 1, depth - 1) : start + i
        if (s === '[') return closePos(str, start + i + 1, depth + 1)
      }
      return -1
    }
    
    const openPos = (str: string, end: number = str.length, depth = 0): number => {
      for (let [i, s] of str.slice(0, end).split('').reverse().entries()) {
        if (s === '[') return depth ? openPos(str, end - i - 1, depth - 1) : end - i - 1
        if (s === ']') return openPos(str, end - i - 1, depth + 1)
      }
      return -1
    }
    
    const brainFuck = (code: string, input: string) => {
      const memory = new Proxy<Array<number>>([], {
        get (target, index: number) {
          return target[index] || 0
        }
      })
      // Without Proxy: const memory = new Array(100).fill(0)
      let cursor = 0
      let inputCursor = 0
      let output: Array<number> = []
    
      for (let i = 0, len = code.length; i < len;) {
        switch (code[i]) {
          case '.': output.push(memory[cursor]); i++; break
          case ',': memory[cursor] = input.charCodeAt(inputCursor++); i++; break
          case '+': memory[cursor]++; i++; break
          case '-': memory[cursor]--; i++; break
          case '>': cursor++; i++; break
          case '<': cursor--; i++; break
          case '[': i = memory[cursor] ? i + 1 : closePos(code, i + 1); break
          case ']': i = memory[cursor] ? openPos(code, i) : i + 1; break
          default: i++
        }
      }
    
      return output.map(v => String.fromCharCode(v)).join('')
    }
    

登录后回复
 

与 ScriptOJ 的连接断开,我们正在尝试重连,请耐心等待