Skip to content

Instantly share code, notes, and snippets.

@motss
Last active October 19, 2023 11:50
Show Gist options
  • Save motss/5abe0842bfe99ab6b1b7d482f2151970 to your computer and use it in GitHub Desktop.
Save motss/5abe0842bfe99ab6b1b7d482f2151970 to your computer and use it in GitHub Desktop.
Expression parser
// a = 1; b = a - 1; b = b - 100; b * a - 100
// split('; ');
// a=1
// b=a-1
// b=b-100
// b*a-100
// a=1
// a 1 =
// b=a-1
// b a 1 - =
// b=b-100
// b b 100 - =
// b*a-100
// b a * 100 -
// a 1 =
// b a 1 - =
// b b 100 - =
// b a * 100 -
// a 1
// =
// assign(a, 1)
// b a 1 - =
// b {get(a) - 1}
// =
// assign(b, get(a) - 1)
// b b 100 - =
// b (get(b) - 100)
// =
// assign(b, get(b) - 100)
// b a * 100 -
// {b*a} 100
// -
// b*a - 100
function isToken2(n) {
return ['+', '-', '*', '='].some(v => n === v);
}
// parse(str)
function parse(str) {
const stk = [];
const tkn = [];
for (const n of str.split(' ')) {
if (isToken2(n)) {
const t2 = tkn.at(-1);
if (t2 === '*') {
while (tkn.length) {
stk.push(tkn.pop());
}
}
tkn.push(n);
} else {
stk.push(n);
}
}
while (tkn.length) {
stk.push(tkn.pop());
}
return stk;
}
const map = new Map;
function getVal(token) {
if (token === 'a' || token === 'b') return map.get(token);
return token;
}
// evaluate(arr)
function eval2(arr) {
debugger;
const stk = [];
const tkn = [];
const eval3 = (n) => {
if (n === '*') {
const r = getVal(stk.pop());
const l = getVal(stk.pop());
stk.push(l * r);
} else if (n === '-') {
const r = getVal(stk.pop());
const l = getVal(stk.pop());
stk.push(l - r);
} else if (n === '=') {
const r = getVal(stk.pop());
const l = stk.pop();
map.set(l, r);
}
};
for (const n of arr) {
if (isToken2(n)) {
eval3(n);
} else {
stk.push(n);
}
}
while (tkn.length) {
eval3(tkn.pop());
}
return stk.pop();
}
const input = `a = 1; b = a - 1; b = b - 100; b * a - 100`;
const res = input.split('; ').map(n => {
const parsed = parse(n);
const res = eval2(parsed);
return res;
});
console.debug(res); // -200
/**
* Approach:
* 1. 1st pass - parse the tokens using RPNE
* 2. 2nd pass - traverse the tokens for evaluation/ computation
* 3. Pop the final value from the stack.
*
* Time completixy: O(n) where n is the number of tokens
* Space complexity: O(n) where n is the number of tokens
*/
fn = (str) => {
const tkn = [];
const stk = [];
const isToken2 = (n) => Number.isNaN(parseFloat(n));
// parse (Reverse Polish Notation Evaluator)
for (const n of str) {
if (n === ' ') continue;
const isToken = isToken2(n);
if (isToken) {
const t2 = tkn.at(-1);
if (t2 == null) {
tkn.push(n);
} else if (t2 === '*' || t2 === '/') {
while (tkn.length) {
stk.push(tkn.pop());
}
tkn.push(n);
} else {
if (n !== '*' && n !== '/') {
while (tkn.length) {
stk.push(tkn.pop());
}
}
tkn.push(n);
}
} else {
stk.push(parseFloat(n));
}
}
while (tkn.length) {
const t2 = tkn.pop();
stk.push(t2);
}
// evaluate
const num = [];
let res = 0;
for (const n of stk) {
const isToken = isToken2(n);
if (isToken) {
const r = num.pop();
const l = num.pop();
switch (n) {
case '+': {
num.push(l + r);
break;
}
case '-': {
num.push(l - r);
break;
}
case '*': {
num.push(l * r);
break;
}
case '/': {
num.push(l / r);
break;
}
case '^': {
num.push(l ^ r);
break;
}
default:
}
} else {
num.push(n);
}
}
return [stk, num.pop()];
};
['1 + 2 * 3 - 4', '5 * 4 - 3 - 5 ^ 3', '1 + 2 - 3'].map(n => fn(n));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment