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();
