Calculator

let fs = require("fs");

function start() {
    //let program = fs.readFileSync("/dev/stdin", "utf-8");
    let program = "- 40 + 2 * ( 3 - 20 )";
    
    let tokens = lex(program);
    //console.log(tokens);
    
    let ast = parse(tokens);
    //console.log(JSON.stringify(ast, null, 2));
    
    let output = run(ast);
    console.log(output);
}

function lex(program) {
    let result = [];
    
    let splitProgram = program
        .split(" ");
    
    for (let text of splitProgram) {
        let number = parseFloat(text);
        let token = {};
        if (!isNaN(number)) {
            token = {
                type: "number",
                value: number,
            };
        } else if (text == "+") {
            token = {
                type: "+",
            };
        } else if (text == "-") {
            token = {
                type: "-",
            };
        } else if (text == "*") {
            token = {
                type: "*",
            };
        } else if (text == "/") {
            token = {
                type: "/",
            };
        } else if (text == "(") {
            token = {
                type: "(",
            };
        } else if (text == ")") {
            token = {
                type: ")",
            };
        } else {
            console.log(`Lex: token "${text}" is not recognized`);
            throw "";
        }
        
        result.push(token);
    }
    
    
    result.push({
        type: "EOF",
    });
    
    return result;
}

function parse(tokens) {
    let i = 0;
    let stream = {
        pop: () => {
            let result = tokens[i];
            i += 1;
            return result;
        },
        peek: () => {
            let result = tokens[i];
            return result;
        },
        consume: () => {
            i += 1;
        },
    };
    
    let result = parseExpr(stream, 9999);
    
    return result;
}

function parseExpr(stream, prevPrecedence) {
    let t = stream.pop();
        
    let left;
    
    if (t.type == "number") {
        left = {
            type: t.type,
            value: t.value,
        };
    } else if (t.type == "-") {
        let expr = parseExpr(stream, 30);
        left = {
            type: "u-",
            expr: expr,
        };
    } else if (t.type == "(") {
        let expr = parseExpr(stream, 90);
        let closingToken = stream.pop();
        if(closingToken.type != ")") {
            console.log(`Parse: Expected ")", found: ${closingToken.type}`);
        }
        
        left = {
            type: "()",
            expr: expr,
        };
    } else {
        console.log(`Parse: Expected operand, found: ${t.type}`);
        throw "";
    }
    
    while(true) {
        let operator = stream.peek();
        if (isClosing(operator)) {
            return left;
        }
        
        let precedence = getPrecedence(operator);
        if (precedence >= prevPrecedence) {
            return left;
        }
        stream.consume();
        
        let right = parseExpr(stream, precedence);
        
        left = {
            type: operator.type,
            left: left,
            right: right,
        };
    }
}

function isClosing(operator) {
    switch(operator.type) {
        case ")": return true;
        case "EOF": return true;
    }
    
    return false;
}

function getPrecedence(operator) {
    switch(operator.type) {
        case "+": return 60;
        case "-": return 60;
        case "*": return 40;
        case "/": return 40;
    }
    
    console.log(`Parse: No precedence for operator "${operator.type}"`);
    throw "";
}

function run(ast) {
    let result = calculate(ast);
    
    return result;
}

function calculate(ast) {
    if (ast.type == "number") {
        return ast.value;
    } else if (ast.type == "+") {
        let left = calculate(ast.left);
        let right = calculate(ast.right);
        let result = left + right;
        return result;
    } else if (ast.type == "-") {
        let left = calculate(ast.left);
        let right = calculate(ast.right);
        let result = left - right;
        return result;
    } else if (ast.type == "*") {
        let left = calculate(ast.left);
        let right = calculate(ast.right);
        let result = left * right;
        return result;
    } else if (ast.type == "/") {
        let left = calculate(ast.left);
        let right = calculate(ast.right);
        let result = left / right;
        return result;
    } else if (ast.type == "()") {
        let result = calculate(ast.expr);
        return result;
    } else if (ast.type == "u-") {
        let expr = calculate(ast.expr);
        let result = -expr;
        return result;
    } else {
        console.log(`Run: Unxepected type: ${ast.type}`);
        throw "";
    }
}

start();