Skip to content

Instantly share code, notes, and snippets.

@shijiezhou1
Last active November 7, 2021 06:25
Show Gist options
  • Save shijiezhou1/0d3d2375379cbc892ba1278940c3eb2f to your computer and use it in GitHub Desktop.
Save shijiezhou1/0d3d2375379cbc892ba1278940c3eb2f to your computer and use it in GitHub Desktop.
calculator.js
var calculate = function (s) {
const stackData = lexer(s);
// console.log({stackData});
return run(stackData);
};
function run(stack) {
let pos = 0;
function match(c) {
// console.log(match.caller, match.arguments);
if (stack[pos] === c) {
pos++;
return true;
}
return false;
}
function factor() {
const oper = match('-') ? -1 : 1;
let num;
if (match('(')) {
num = exp();
match(')');
} else {
num = stack[pos++];
}
return oper + num;
}
function term() {
let num = factor();
while (true) {
if (match('x')) {
num *= factor();
} else if (match('÷')) {
num = (num / factor()) >> 0;
} else {
return num;
}
}
}
function exp() {
let num = term();
while (true) {
if (match('+')) {
num += term();
} else if (match('-')) {
num -= term();
} else {
return num;
}
}
}
return exp();
}
function lexer(s) {
const stack = [];
let i = 0;
while (i < s.length) {
const c = s[i];
if (c === '+' || c === '-' || c === 'x' || c === '÷' || c === '(' || c === ')') {
stack.push(c);
i++;
} else if (c >= '0' && c <= '9') {
let num = Number(s[i++]);
while (s[i] >= '0' && s[i] <= '9') {
num = num * 10 + Number(s[i++]);
}
stack.push(num);
} else {
i++;
}
}
return stack;
}
function infixToPostfix(expression) {
if (typeof expression !== 'string') {
if (expression instanceof String) {
expression = expression.toString();
} else {
return null;
}
}
var result = '';
var stack = [];
var operators = ['*','/','+','-'];
var tokens = expression.match(/(-?(?:\d+\.?\d*|-?\.\d*))|[()+\-*/]/gi);
var containsInvalidChars = /[^()+\-*/0-9.\s]/gi.test(expression);
console.log(tokens, 'is token');
if (Array.isArray(tokens) && !containsInvalidChars) {
for (var i = 0; i < tokens.length; i++) {
var token = tokens[i];
if (operators.indexOf(token) > -1) {
while (stack.length && operators.indexOf(stack[stack.length-1]) > -1) {
var operator = stack.pop();
result += (' ' + operator);
}
stack.push(token);
} else if (token === '(') {
stack.push(token);
} else if (token === ')') {
var item = stack.pop();
while (item !== '(') {
result += (' ' + item);
item = stack.pop();
}
} else if (token) {
result += (' ' + token);
}
}
}
while (stack.length) {
var item = stack.pop();
result += (' ' + item);
}
result = result.trim();
return (result.length >= 1 ? result : null);
}
let s = "((15 ÷ (7 - (1 + 1) ) ) x -3) - (2 + (1 + 1))";
// let s = '((3 * 4) / (2 + 5)) * (3 + 4)';
// let s = '((15 / (7 - (1 + 1) ) ) * -3) - (2 + (1 + 1))';
s = s.replaceAll(' ', ''); // trim
const ans = calculate(s);
// console.log({ ans });
const res = infixToPostfix(s);
console.log(res)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment