const assert = require('assert');

const Value = (n) => ({ type: 'value', n });
const Sum = (a, b) => ({ type: 'sum', a, b });
const Prod = (a, b) => ({ type: 'prod', a, b });
const Div = (a, b) => ({ type: 'div', a, b });
const Sub = (a, b) => ({ type: 'sub', a, b });

const sliceLast = (a, n) => a.slice(n > a.length ? 0 : a.length - n, a.length);

const parseValue = (str) => {
  const [n] = sliceLast(str, 1);

  const int = parseInt(n);

  if (Number.isNaN(int)) return undefined;

  return Value(int);
};

const parseSum = (str, [nop]) => {
  const [a, op, b] = sliceLast(str, 3);

  if (!['value', 'prod', 'div', 'sum', 'sub'].includes(a?.type)) {
    return undefined;
  }

  if (op !== '+') return undefined;

  if (!['value', 'prod', 'div', 'sum', 'sub'].includes(b?.type)) {
    return undefined;
  }

  if (nop === '*') return undefined;

  if (nop === '/') return undefined;

  return Sum(a, b);
};

const parseSub = (str, [nop]) => {
  const [a, op, b] = sliceLast(str, 3);

  if (!['value', 'prod', 'div', 'sum', 'sub'].includes(a?.type)) {
    return undefined;
  }

  if (op !== '-') return undefined;

  if (!['value', 'prod', 'div', 'sum', 'sub'].includes(b?.type)) {
    return undefined;
  }

  if (nop === '*') return undefined;

  if (nop === '/') return undefined;

  return Sub(a, b);
};

const parseProd = (str) => {
  const [a, op, b] = sliceLast(str, 3);

  if (!['value', 'prod', 'div'].includes(a?.type)) return undefined;

  if (op !== '*') return undefined;

  if (!['value', 'prod', 'div'].includes(b?.type)) {
    return undefined;
  }

  return Prod(a, b);
};

const parseDiv = (str) => {
  const [a, op, b] = sliceLast(str, 3);

  if (!['value', 'prod', 'div'].includes(a?.type)) return undefined;

  if (op !== '/') return undefined;

  if (!['value', 'prod', 'div'].includes(b?.type)) {
    return undefined;
  }

  return Div(a, b);
};

const reduce = (str, la) => {
  return (
    parseProd(str, la) ||
    parseDiv(str, la) ||
    parseSum(str, la) ||
    parseSub(str, la) ||
    parseValue(str, la)
  );
};

/** @param {string} str */
const parse = (str) => {
  const tbp = str.trim().split('');
  const state = [];

  while (tbp.length) {
    state.push(tbp.shift());

    let i = 1;

    while (i < state.length + 1) {
      const slice = state.splice(state.length - i, state.length);

      const result = reduce(slice, tbp.slice(0, 1));

      i++;

      if (result === undefined) state.push(...slice);
      else if (result === '') {
      } else {
        const shouldBreak = !state.length;

        state.push(result);

        if (shouldBreak) break;

        i = 1;
      }
    }
  }

  if (state.length === 1) return state[0];

  return undefined;
};

const print = (n) => {
  if (n?.type === 'value') return `Value(${n.n})`;
  if (n?.type === 'sum') return `Sum(${print(n.a)}, ${print(n.b)})`;
  if (n?.type === 'sub') return `Sub(${print(n.a)}, ${print(n.b)})`;
  if (n?.type === 'prod') return `Prod(${print(n.a)}, ${print(n.b)})`;
  if (n?.type === 'div') return `Div(${print(n.a)}, ${print(n.b)})`;

  return n;
};

assert(parse('') === undefined);
assert(parse('1+') === undefined);
assert(parse('1-') === undefined);
assert(parse('1*') === undefined);
assert(parse('1/') === undefined);

assert.deepEqual(parse('1'), Value(1));
assert.deepEqual(parse('1+1'), Sum(Value(1), Value(1)));
assert.deepEqual(parse('1+1'), Sum(Value(1), Value(1)));
assert.deepEqual(parse('1-1'), Sub(Value(1), Value(1)));
assert.deepEqual(parse('1*2'), Prod(Value(1), Value(2)));
assert.deepEqual(parse('1/2'), Div(Value(1), Value(2)));
assert.deepEqual(parse('1*1+2'), Sum(Prod(Value(1), Value(1)), Value(2)));
assert.deepEqual(parse('1*1-2'), Sub(Prod(Value(1), Value(1)), Value(2)));
assert.deepEqual(parse('1/1+2'), Sum(Div(Value(1), Value(1)), Value(2)));
assert.deepEqual(parse('1/1-2'), Sub(Div(Value(1), Value(1)), Value(2)));
assert.deepEqual(parse('1-1+2'), Sum(Sub(Value(1), Value(1)), Value(2)));
assert.deepEqual(parse('1-1-2'), Sub(Sub(Value(1), Value(1)), Value(2)));
assert.deepEqual(parse('1+1+2'), Sum(Sum(Value(1), Value(1)), Value(2)));
assert.deepEqual(parse('1+1-2'), Sub(Sum(Value(1), Value(1)), Value(2)));
assert.deepEqual(parse('1+1*2'), Sum(Value(1), Prod(Value(1), Value(2))));
assert.deepEqual(parse('1-1*2'), Sub(Value(1), Prod(Value(1), Value(2))));
assert.deepEqual(parse('1+1/2'), Sum(Value(1), Div(Value(1), Value(2))));
assert.deepEqual(parse('1-1/2'), Sub(Value(1), Div(Value(1), Value(2))));
assert.deepEqual(parse('1+1-2'), Sub(Sum(Value(1), Value(1)), Value(2)));
assert.deepEqual(parse('1-1-2'), Sub(Sub(Value(1), Value(1)), Value(2)));
assert.deepEqual(parse('1+1+2'), Sum(Sum(Value(1), Value(1)), Value(2)));
assert.deepEqual(parse('1-1+2'), Sum(Sub(Value(1), Value(1)), Value(2)));