Expression parser

expression-parser-multi-line.js

// 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

expression-parser.js

/**
 * 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));