算法

一些算法问题的汇总(3)

  Ever tried. Ever failed.

  No matter. Try again.

  Fail again. Fail better.

       --Peter Dinklage

brainFuck语法编译器

brainFuck语言是一门非常简单的基于栈的语言，只有以下几种操作符
"+": 指针指向单元数值自增1
"-": 指针指向单元数值自减1
">": 指针向右移动一格
"<": 指针向左移动一格
".": 输出指针指向的数值（ASCII码形式）
",": 接受输入的数值

前言

  虽然本算法称为编译器，但其实仅仅只是将原本的brainFuck语言转换成了javascript语言，并做了一些缩进，其目的只是为了好玩。利用这个brainFuck编译器，你可以写自己的brainFuck语言，比如一个“Hello World！”就可以是“++++++++++[>+>+++>+++++++>++++++++++<<<<-]>>>++.>+.+++++++..+++.<<++.>+++++++++++++++.>.+++.------.--------.<<+.<.”这么长的奇怪代码。当然，要自己写一个这样像密码一般的字符串也不是一件容易的事，或许真的是件brainFuck！的事。权当娱乐，重在开心。

代码如下:

function Compile(syntax, params) {
    'use strict';
    const MAXSIZE = 40;
    let cache = [], count = 0, code = undefined, i, memory = MAXSIZE;
    if (params && params.hasOwnProperty("memory") && params.memory > 0) {
        memory = params.memory;
    } else if (params) {
        for (i=0; i<params.length; i++)
            params[i] = paraseInt(params[i]) | 0;
    }
    let canDo = (x) => x == ">" || x == "<" || x == "+" || x == "-";
    let addp = (x) => "pointer+=" + x + ";";
    let subp = (x) => "pointer-=" + x + ";";
    let adder = (x) => "stack[pointer]+=" + x + ";";
    let suber = (x) => "stack[pointer]-=" + x + ";";
    let output = "output.push(stack[pointer]);";
    let input = (x) => "stack[pointer]=JSON.parse(" + JSON.stringify(x) + ");";
    let whs = "while(stack[pointer]){";
    let whe = "}";
    let debug = (x) => "console.log('stack memory:' + stack.join('|') + ' current pointer:' + pointer + ' at:' + " + x + ");";
    let record = { operating: NaN, count: NaN };
    syntax += "#";
    cache.push("let stack=[];");
    cache.push("stack.length=" + memory + ";");
    cache.push("stack.fill(0);");
    cache.push("let pointer=0;");
    cache.push("let output=[];");
    for (i = 0; i < syntax.length; i++) {
        if (record.operating == syntax[i]) {
            record.count++;
            continue;
        } else if (!!record.operating) {
            switch (record.operating) {
                case ">": cache.push(addp(record.count)); break;
                case "<": cache.push(subp(record.count)); break;
                case "+": cache.push(adder(record.count)); break;
                case "-": cache.push(suber(record.count)); break;
            }
        }
        if (canDo(syntax[i])) {
            record.operating = syntax[i];
            record.count = 1;
        } else {
            record.operating = record.count = NaN;
        }
        switch (syntax[i]) {
            case ",": cache.push(input(params[count++])); break;
            case "[": cache.push(whs); break;
            case "]": cache.push(whe); break;
            case ".": cache.push(output); break;
        }
        if (params &&
            params.hasOwnProperty("debug") &&
            params.debug &&
            (syntax[i] == "+" || syntax[i] == "-")) {
            cache.push(debug(i + 1));
        }
    }
    cache.push("for(let i=0;i<output.length;i++){output[i]=String.fromCharCode(output[i]);}");
    cache.push("console.log(output.join(''));");
    return {
        brainFuck: new Function(cache.join("")),
        codeLength: cache.length
    };
}
// Hello World!
var helloworld = Compile("++++++++++[>+>+++>+++++++>++++++++++<<<<-]>>>++.>+.+++++++..+++.<<++.>+++++++++++++++.>.+++.------.--------.<<+.<.");
helloworld.brainFuck();

计算公式转逆波兰式（计算器原理）

  逆波兰式也叫也叫后缀表达式，之所以要转换为后缀表达式，原因就在于这个简单是相对人类的思维结构来说的，对计算机而言中序表达式是非常复杂的结构。相对的，逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序。
  所以，在计算机中运算这样的一个公式(123+abc)*d-(a+b)/e，我们一般先转化为逆波兰式，再在栈中求解计算。

代码如下:

var classes = new Map();
classes.set('+', [5,  6]);
classes.set('-', [7,  8]);
classes.set('*', [1,  2]);
classes.set('/', [3,  4]);
classes.set('(', [11, 0]);
classes.set(')', [13, 12]);
classes.set('#', [14, 14]);
function check(sign) {
    if (sign == "#" || sign == "(" || sign == ")") {
        return false;
    }
    return true;
}
/**
 * 编译成逆波兰式
 * 
 * @param {*} str 计算公式 
 */
function compile(str) {
    let stack = [], output = "", pointer = 0, sign, pushIcon;
    str = "#"+str+"#";
    for (let i=0; i<str.length; i++) {
        if (!!classes.get(str[i])) {
            pushIcon = true;
            for(let j=stack.length-1; j>=0; j--) {
                let inLevel = classes.get(stack[stack.length - 1])[0];
                let outLevel = classes.get(str[i])[1];
                if (stack[stack.length - 1] == "(" && str[i] == ")") {
                    stack.pop();
                    pushIcon = false;
                    break;
                }
                if (inLevel < outLevel)
                    output += " " + stack.pop();
                else 
                    break;
            }
            if (stack[stack.length - 1] == "#" && str[i] == "#")
                 return output.split(" ").filter((x) => x!=="").join(" ");
            if (pushIcon) {
                stack.push(str[i]);
                output += " ";
            }
        } else {
            output+=str[i];
        }
    }
    console.err("equation is error!");
}
/**
 * 运算逆波兰式 
 * 
 * @param {*} equation 逆波兰式
 * @param {*} params 参数
 */
function run(equation, params) {
    let machine = equation.split(" ");
    let stack = [];
    for (let element of machine) {
        if (classes.get(element)) {
            let after = stack.pop();
            let before = stack.pop();
            switch(element) {
                case "+": stack.push(before + after);break;
                case "-": stack.push(before - after);break;
                case "*": stack.push(before * after);break;
                case "/": stack.push(before / after);break;
                default:
                     return new Error("can't calculate it!!!");
            }
        } else if (isNaN(element)) {
            if (params && params.hasOwnProperty(element))
                stack.push(params[element]);
            else
                return new Error("no this params!!!");
        } else
            stack.push(parseFloat(element));
    }
    return stack.pop();
}
var result = compile("(123+abc)*d-(a+b)/e");
console.log(result);
var value = run(result, {abc: 1, d: 1, a: 1, b: 1, e: 1});
console.log(value);