<
header

Parser

As mentioned before, it transforms a string into a tree. Before we start with the function, let’s see how the tree is supposed to look.

Expression Types

First, we can start with a simple expression like 1 + 2. This is how it looks like as a tree:

  
    graph TD;
        subgraph 12["1 + 2"]

        add(+) --> 1(1);
        add --> 2(2);

        end

There are three main things here: add, 1, and 2. If we generalize this, we get operation, number, and number

Nice! We now know the three things needed for a tree. An object would be perfect for this

type Operation = "add" | "sub" | "mul" | "div";

interface Expression {
    left: number,
    right: number,
    operation: Operation
}

Now we have a union type for the operation, the left, and the right. With all of these together we have an Expression!

This is good, but for a tree like this:

  
    graph TD;
        subgraph 123["1 + 2 + 3"]

        add(+) --> 1(1)
        add(+) --> add2(+)
        add2 --> 2(2)
        add2 --> 3(3)

        end

The right isn’t a number. it’s another add.

...

interface Expression {
    left: Expression,
    right: Expression,
    operation: Operation,
}

That’s better! Now we can have an even bigger tree. But, what about negation? It should be included in Expression as well, but it only has 1 value, and not left and right.

Negation

What if we had a bunch of objects, one for each operation, and one more for Negation? Then, we can make Expression a union type of all of those!

interface Add {
    left: Expression,
    right: Expression,
    operation: "add",
}
interface Sub {
    left: Expression,
    right: Expression,
    operation: "sub",
}
interface Mul {
    left: Expression,
    right: Expression,
    operation: "mul",
}
interface Div {
    left: Expression,
    right: Expression,
    operation: "div",
}
interface Neg {
    val: Expression, // val is short for value
    operation: "neg",
}

type Expression = Add | Sub | Mul | Div | Neg;

Parentheses

Now that negation is here as well, adding parentheses is simple.

interface Add {
    left: Expression,
    right: Expression,
    _tag: "add",
}
interface Sub {
    left: Expression,
    right: Expression,
    _tag: "sub",
}
interface Mul {
    left: Expression,
    right: Expression,
    _tag: "mul",
}
interface Div {
    left: Expression,
    right: Expression,
    _tag: "div",
}
interface Neg {
    val: Expression,
    _tag: "neg",
}
interface Group { // (Parentheses)
    val: Expression,
    _tag: "group",
}

type Expression = Add | Sub | Mul | Div | Neg | Group;

Now that we’ve added the Group interface to Expression, operation doesn’t really fit, because ( and ) aren’t operations. So, I changed operation to _tag. The underscore is just there to easily differentiate it from the other elements in the objects like left, right, or val.

The tag is needed to know which object is which. When a function takes in an expression, it might not know what expression it is. With the tag, we can tell exactly whether it’s Add, or Div, or something else.

Leaf

We’re almost done with the types, there’s just one more interface needed. None of the interfaces have numbers or variables. It’s always an expression. This means that adding a number or variable to the tree would give a type error. Let’s fix that!

...

const _variables = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"] as const;
type Variable = typeof _variables[number];

interface VarLeaf { // short for Variable Leaf
    val: Variable,
    _tag: "var",
}
interface ValLeaf { // short for Value Leaf
    val: number,
    _tag: "val"
}
interface Leaf {
    val: VarLeaf | ValLeaf,
    _tag: "leaf"
}

type Expression = Add | Sub | Mul | Div | Neg | Group | Leaf  | VarLeaf | ValLeaf;

We’ve now made 3 new objects: VarLeaf, ValLeaf, and Leaf. With this structure, we have numbers, variables, expressions, and expressions inside of expressions! Awesome!

as const sets the type of _variables to ["a", "b", "c", ... "y", "z"]. By default, _variables is a string, but after using as const, _variables is only a list of the lower-case letters.

type Variable = typeof _variables[number];

Translates to:

type Variable = "a" | "b" | "c" | ... "y" | "z";

The names ValLeaf and VarLeaf are a little bit confusing, but it isn’t too hard to get the hang of it.

You might be wondering why ValLeaf wasn’t named something like NumLeaf. Even if you weren’t, it’s because all of the types will be generalized. They don’t have to be used only for numbers and variables, but also for other things. Calling it NumLeaf means it only applies to numbers, which it doesn’t.

Generic Types

Speaking of generalization, we can use generic types for all the objects.

A generic type is like an “input” to a type.

interface ValLeaf<T> {
    val: T,
    _tag: "val"
}

Here, T is the input type. If we want to use numbers, we would write ValLeaf<number>. Or maybe we want to use a list of numbers, then it would be ValLeaf<number[]>.

Let’s generalize all the previous types:

interface Add<T> {
    left: Expression<T>,
    right: Expression<T>,
    _tag: "add"
}

...

interface VarLeaf {
    val: Variable,
    _tag: "var"
}
interface ValLeaf<T> {
    val: T,
    _tag: "val"
}
interface Leaf<T> {
    val: VarLeaf | ValLeaf<T>,
    _tag: "leaf"
}

type Expression<T> = Add<T> | Sub<T> | ... ;

And we’re finished with Expression! We can finally move on

The 3 boxes

Okay, now that we’ve got the expression itself taken care of, we can go a bit deeper into the writing the function. Although, we aren’t done with types just yet. For our parser, one method to use is to go character-by-character, which means we use the .split() function for the input string, and go from there.

Let’s look at an example for a + b, and try to see what information we need to store in boxes (lets) in each cycle:

Character 1: a

a is a variable. Remember how we added VarLeaf to Expression? That means it’s an expression on it’s own. We need somewhere to store a, so let’s create our first box, parsed:

let parsed: Expression<number> = {
    _tag: "leaf",
    val: {
        _tag: "var",
        val: "a"
    }
}

Here’s how parsed looks so far:

  
    graph TD;
        subgraph graph[" "];

        a(a);

        end

Character 2: +

+ is an operator. We can’t really do anything with this right now though, since we don’t know whats on the right yet. We’ll just create our second box to store things like operators which need more information before it can be parsed. Let’s call it waiting.

let parsed: Expression<number> = {
    ...
}

let waiting = "+";

Character 3: b

b is another variable. There’s already a variable in parsed and an operator in waiting, let’s combine these and make a new Expression. We have the left and right, a and b. The operator inside waiting is +. So, we can create a new Add!

parsed = {
    _tag: "add",
    left: {
        _tag: "leaf",
        val: {
            _tag: "var",
            val: "a",
        }
    },
    right: {
        _tag: "leaf",
        val: {
            _tag: "var",
            val: "b",
        }
    }
}

waiting = null;

parsed now looks like this:

  
    graph TD;
        subgraph ab["a + b"]

        add(+) --> a(a);
        add --> b(b);

        end

Nice, now we know what we need, one box for the parsed values, and another box for the elements that need more information before they can be parsed.

The waiting box is still a little incomplete. Imagine if the expression was a + -b instead. After we put + in the waiting, the - also needs to be stored somewhere. We could create another box for this, but since - is also waiting for more information, let’s add a new element to our Waiting object:

interface Waiting<Operator> {
    operator: Operator,
    negate: boolean,
}

negate is a boolean because there are only two options for it: negate or don’t negate.

The example we used before is pretty simple, but what about something like a + (b * c)?

The parentheses makes everything a lot more complicated, but one nice method is to just keep b * c stored in the waiting let as a string, and then parse that bit separately by calling our parser again. Let’s add another element to the Waiting object:

interface Grouped {
    _tag: "grouped",
    exp: string,
}
interface UnGrouped {
    _tag: "ungrouped",
    exp: null,
}
type GroupWait = Grouped | UnGrouped;

interface Waiting {
    operator: Operator,
    negate: boolean,
    group: GroupWait,
}

Perfect!

We have two boxes, but what about the third one? The parsed and waiting boxes seem like enough, but there’s just one more box we need. Imagine if someone makes a typo and types a ++ b instead of a + b. We can’t parse that. After +, we’re expecting either parentheses, a negative sign, or a variable/number. We need to send an error for that. Let’s create a box for what we expect, and if the character doesn’t match out expectations, we throw an error.

type ExpectedNum = "number" | "variable" | "operator" | "neg" | "group";

The ExpectedNum has all the things we could expect. We can just make a list of ExpectedNums for our third and final box, nextExpected!

let nextExp: ExpectedNum[] = [...] // the expectations in each cycle

Now that we officially have 3 boxes, let’s make the parser!

The parser function

Let’s start out by defining the function:

function parseInput(input: string): Expression<number> | null {

}

The return type could be null if the input is "" (empty string).

Preparing the input

Before we add our 3 boxes into the function, let’s tweak the input a tiny bit to make it easier for us. Since we’re going character by character, we can use the .split("") function to make the string into a list.

But, when someone types in 1 + a, we only need 3 things: 1, +, and a. When we use split, we get ["1", " ", "+", " ", "a"]. All of those spaces are not needed, so let’s just get rid of it using .replaceAll():

function parseInput(input: string): Expression<number> | null {
    const withoutSpaces = input.replaceAll(" ", "");
    const splitInp = withoutSpaces.split("");
}

All the unnecessary spaces have been removed! But, if someone types in an expression with a 2 digit number, like 10 + a, it will result in ["1", "0", "+", "a"]. But we don’t want ["1", "0", ...], we want ["10", ...]. Let’s write a new function to join them together:

Join Similarities

function joinSimilarities(list: string[], similarities: string[]): string[] {
    return list.reduce((prev: string[], current: string) => prev.length === 0
        ? [current]
        : similarities.includes(current)
            ? similarities.includes(prev[prev.length - 1][0])
                ? [...prev.slice(0, prev.length - 1), prev[prev.length - 1] + current]
                : [...prev, current]
            : [...prev, current],
        []
    )
}

It takes in a list that needs to be compressed (["1", "0", "+", "a"], for example), and another list for the “similar” things. For us, the similar things would be ["0", "1", "2", "3", "4", "5", "7", "8", "9"].

joinSimilarities uses the reduce() function to go through each element. It’s basically like a for loop, but it has a previousValue and a currentValue. In our case, if both of them are numbers, the function will join it together.

The part inside the reduce function has a lot of ternary operator branches, so here is how it is with english mixed in with the code:

if prev.length === 0

    ? [current]

    : if the current value is in the list of similarities,

        ? if the similarities also includes the value just before this current value,

            ? create a new list with the all of the previous value's elements except the very last one, join the last one and the current value, and put it into the list.

            : just add the current value to the previous value list

        : just add the current value to the previous value list

It’s a little bit complicated, but all it does is transform an expression like ["1", "0", "+", "a"] to ["10", "+", "a"].

And with everything put together, the code looks like this:

function joinSimilarities(list: string[], similarities: string[]): string[] {
    return list.reduce((prev: string[], current: string) => prev.length === 0
        ? [current]
        : similarities.includes(current)
            ? similarities.includes(prev[prev.length - 1][0])
                ? [...prev.slice(0, prev.length - 1), prev[prev.length - 1] + current]
                : [...prev, current]
            : [...prev, current],
        []
    )
}

function parseInput(input: string): Expression<number> | null {
    const splitInp = input.split("");
    const withoutSpaces = listed.replaceAll(" ", "");
    const listed = joinSimilarities(withoutSpaces, "0123456789".split(""));
}

Using the boxes

Now that the input is ready to go, it’s time to add the boxes we made earlier!

...

type NumberOperator = "+" | "*" | "-" | "/";
type ExpectedValue = "number" | "variable" | "operator" | "group" | "neg";

function parseInput(input: string): Expression<number> | null {
    ...

    let parsed: Expression<number> | null = null;
    let waiting: Waiting<NumberOperator> = {
        operator: null,
        negate: false,
        group: {
            _tag: "ungrouped", 
            exp: null
        }
    }
    let nextExp: ExpectedValue[] = ["number", "variable", "group", "neg"];
}

Since all of that is out of the way, let’s start with the loop!

The Parser Loop

Let’s use a for loop to go through each character. The first thing we need to do in the for loop is to check if the value is expected, if it isn’t then the whole loop has to stop immediately.

...

function parseInput(input: string): Expression<number> | null {
    ...
    for(let idx = 0; idx < listed.length; idx++) {
        const curVal: string = listed[idx];
        
        if(!isExpected(curVal, nextExp)) {
            throw "Error: Unexpected value"l
        }
    }
}

The isExpected function just checks if the value is a part of the nextExp.

We already know the possible types of characters that come in each loop (neg, number, group, variable, operator), so we can use if to decide what to do. Before we actually make it do anything, let’s plan out the structure:

...

type NumberOperator = "+" | "-" | "*" | "/";
const numberOperators = ["+", "-", "*", "/"];

...

const numberOperators: NumberOperator[] = ["+"]

function parseInput(input: string): Expression<number> | null {
    ...
    for(let idx = 0; idx < listed.length; idx++) {
        const curVal: string = listed[idx];
        
        if(!isExpected(curVal, nextExp)) {
            throw "Error: Unexpected value"l
        }

        const shouldHandleGroup = waiting.group._tag === "grouped" || curVal === "(" || curVal === ")";

        if(shouldHandleGroup) {

        }

        const shouldHandleNeg = curVal === "-" && (waiting.operator !== null || parsed === null);
        // if waiting.operator is null, and parsed is not null, it means that curVal is for subtraction and not negation.

        if(shouldHandleNeg) {

        }

        if((numberOperators as string[]).includes(curVal)) { // if curVal is an operator

        }

        if((variables as string[]).includes(curVal)) {

        }
        
        // if none of the above, curVal is a number.
    }
    return parsed;
}

Instead of actually handling each one of those inside the if block, let’s create functions to handle them, and call those function inside the ifs.

Value handlers

Each of the functions will do some of these 3 things:

First, the number handler!

interface ParsedWaitNext<T, Op, NE> {
    parsed: Expression<T>,
    waiting: Waiting<Op>,
    next: NE[],
}

function valueIsNumber(
    value: number, 
    parsed: Expression<number> | null, 
    waiting: Waiting<NumberOperator>
): ParsedWaitNext<number, NumberOperator, ExpectedValue> {
    if(waiting.negate) {

    }
}

The ParsedWaitNext interface is needed because we need our main parseInput function to get all the 3.

We’ve stopped here because we are going to be changing parsed a lot. It’s pretty tiring to keep typing all the curly braces over and over, so why don’t we just make a function that does it for us?

function makeNumExp(
    leftOrValue: Expression<number>,
    right: Expression<number> | null,
    tag: NumberOperator | "neg" | "group",
): Expression<number> {
    ...
}

function makeLeaf(val: T | Variable): Leaf<T> {
    ...
}

If you want to check out the contents of the functions, click here to see it on github.

makeLeaf is pretty straightforward, it takes a T or a Variable, makes a VarLeaf or a ValLeaf<T> from it, and then puts that into a Leaf.

makeNumExp takes a left, right, and a tag. If tag is "neg" or "group", the left is the value and right is null. All it does is create a new Expression with the inputs. For example,

const exp = makeNumExp(
    {
        _tag: "leaf",
        val: {
            _tag: "var",
            val: "a",
        }
    },
    {
        _tag: "leaf",
        val: {
            _tag: "var",
            val: "b",
        }
    },
    "*"
)

const result = {
    _tag: "mul",
    left: {
        _tag: "leaf",
        val: {
            _tag: "var",
            val: "a",
        }
    },
    right: {
        _tag: "leaf",
        val: {
            _tag: "var",
            val: "b",
        }
    }
}

exp and result are equal.

And now, to pick up where we left off:

function valueIsNumber(
    value: number, 
    parsed: Expression<number> | null, 
    waiting: Waiting<NumberOperator>
): ParsedWaitNext<number, NumberOperator, ExpectedValue> {
    if(waiting.negate) {

    }
}

Let’s use makeNumExp!

function valueIsNumber(
    value: number, 
    parsed: Expression<number> | null, 
    waiting: Waiting<NumberOperator>
): ParsedWaitNext<number, NumberOperator, ExpectedValue> {
    const leafed = makeLeaf(value);

    const newBranch: Expression<number> = waiting.negate
        ? makeNumExp(leafed, null, "neg")
        : value
    
    const newParsed: Expression<number> = parsed === null
        ? newBranch
        : makeNumExp(parsed, newBranch, waiting.operator as NumberOperator)

    const newNext: ExpectedValue[] = ["operator", "group"];
    const newWaiting: Waiting<NumberOperator> = {
        operator: null,
        negate: false,
        group: {
            _tag: "ungrouped",
            exp: null,
        }
    }
    return {
        parsed: newParsed,
        waiting: newWaiting,
        next: newNext,
    }
}

What the code above is doing is, first it checks if waiting.negate is true. If it is, it means value needs to be negated, so it makes a new Neg for the value. If waiting.negate is false, it just sets the value as the branch.

Then, for the parsed, if parsed is null, it means that this number is the first part of the expression. Which means nothing needs to be done, so newParsed gets set to newBranch. If it isn’t null, though, parsed and newBranch need to be combined using the operator in waiting.

The next expected from here is only ["operator", "group"]. Other than an operator, or a ) (closed parentheses), nothing else can come after a number.

newWaiting is just the default Waiting.

Now let’s write a valueIsVariable function.

function valueIsVariable(
    value: Variable, 
    parsed: Expression<number> | null, 
    waiting: Waiting<NumberOperator>
): ParsedWaitNext<number, NumberOperator, ExpectedValue> {
    const leafed = makeLeaf(value);

    const newBranch: Expression<number> = waiting.negate
        ? makeNumExp(leafed, null, "neg")
        : value
    
    const newParsed: Expression<number> = parsed === null
        ? newBranch
        : makeNumExp(parsed, newBranch, waiting.operator as NumberOperator)

    const newNext: ExpectedValue[] = ["operator"];
    const newWaiting: Waiting<NumberOperator> = {
        operator: null,
        negate: false,
        group: {
            _tag: "ungrouped",
            exp: null,
        }
    }
    return {
        parsed: newParsed,
        waiting: newWaiting,
        next: newNext,
    }
}

The valueIsVariable and valueIsNumber functions are exactly the same, except for in the 2nd line:

function valueIsVariable(
    value: Variable, // <-- number or Variable
    parsed: Expression<number> | null,
    
    ...

So, why don’t we just combine them?

function valueIsNumOrVar(
    value: number | Variable, 
    parsed: Expression<number> | null, 
    waiting: Waiting<NumberOperator>
): ParsedWaitNext<number, NumberOperator, ExpectedValue> {

    ...

Awesome! Let’s see how this looks when implemented in parseInput.

function valueIsNumOrVar(
    value: number | Variable, 
    parsed: Expression<number> | null, 
    waiting: Waiting<NumberOperator>
): ParsedWaitNext<number, NumberOperator, ExpectedValue> {
    const leafed = makeLeaf(value);

    const newBranch: Expression<number> = waiting.negate
        ? makeNumExp(leafed, null, "neg")
        : value
    
    const newParsed: Expression<number> = parsed === null
        ? newBranch
        : makeNumExp(parsed, newBranch, waiting.operator as NumberOperator)

    const newNext: ExpectedValue[] = ["operator"];
    const newWaiting: Waiting<NumberOperator> = {
        operator: null,
        negate: false,
        group: {
            _tag: "ungrouped",
            exp: null,
        }
    }
    return {
        parsed: newParsed,
        waiting: newWaiting,
        next: newNext,
    }
}

function parseInput(input: string): Expression<number> | null {
    const splitInp = input.split("");
    const withoutSpaces = listed.replaceAll(" ", "");
    const listed = joinSimilarities(withoutSpaces, "0123456789".split(""));

    let parsed: Expression<number> | null = null;
    let waiting: Waiting<NumberOperator> = {
        operator: null,
        negate: false,
        group: {
            _tag: "ungrouped", 
            exp: null
        }
    }
    let nextExp: ExpectedValue[] = ["number", "variable", "group", "neg"];

    for(let idx = 0; idx < listed.length; idx++) {
        const curVal: string = listed[idx];
        
        if(!isExpected(curVal, nextExp)) {
            throw "Error: Unexpected value"l
        }

        const shouldHandleGroup = waiting.group._tag === "grouped" || curVal === "(" || curVal === ")";

        const shouldHandleNeg = curVal === "-" && (waiting.operator !== null || parsed === null);

        const pwn: ParsedWaitNext< ... > = shouldHandleGroup
            ? // valueIsGroup()
            : shouldHandleNeg
                ? // valueIsNeg()
                : (numberOperators as string[]).includes(curVal)
                    ? // valueIsOperator()
                    : valueIsNumOrVar(
                        (variables as string[]).includes(curVal)
                            ? curVal
                            : JSON.parse(curVal) // converts a string like "10" into the actual number 10
                        parsed,
                        waiting
                    )
        
        parsed = pwn.parsed;
        waiting = pwn.waiting;
        nextExp = pwn.next;
    }
    return parsed;
}

The ifs have also been changed to ternary operators since it looks more compact now. curVal is always a string, so I had to use JSON.parse() to make it a number.

Everything’s looking pretty good so far! 3 more handler functions to go!

Let’s write the valueIsNeg() function, it shouldn’t be too complicated.

function valueIsNeg(
    parsed: Expression<number> | null, 
    waiting: Waiting<NumberOperator>
    ): ParsedWaitNext<number, NumberOperator, ExpectedNumVal> {
        const newWaiting: Waiting<NumberOperator> = {...waiting, negate: true};
        const nextExp: ExpectedNumVal[] = ["number", "group", "variable"];
        return {parsed, waiting: newWaiting, next: nextExp};
}

Since parsed doesn’t change, all that needs to happen is to set waiting.negate to true and update nextExp.

And now valueIsOperator():

export function valueIsOperator(
    value: NumberOperator, 
    parsed: Expression<number>, 
    waiting: Waiting<NumberOperator>
    ): ParsedWaitNext<number, NumberOperator, ExpectedNumVal> {
        const newWaiting: Waiting<NumberOperator> = {...waiting, operator: value};
        const nextExp: ExpectedNumVal[] = ["neg", "number", "group", "variable"];
        return {parsed, waiting: newWaiting, next: nextExp};
}

Again, nothing complex since we just had to put the operator in waiting.

Finally, valueIsGroup(). This one is a bit complicated, though.

There are many things that could happen. The value could be (, or ). Actually, it could also be anything else. If waiting.group._tag is grouped, it means the value needs to be added into waiting.group.exp. If the value is ), it means we have to parse waiting.group.exp, and combine that with our original parsed.

But that’s not all, what about nested parentheses? An expression like a + (b * (c - d)) will result in, b * (c - d being added into waiting.group.exp, and then it’ll stop after d because of the closing parentheses. We don’t want this though, we want b * (c - d) to be added, and stop after that.

Let’s take care of the nested parentheses problem. What we need is an extra closing parentheses. In b * (c - d), the number of closing parentheses is the same as the number of opening parentheses. But, with b * (c - d)), We have an extra closing parentheses! This means we can stop now, parse the expression, and add it to parsed.

Okay, we need to write a function that checks if there are more of ) than (.

function shouldParseGroup(exp: string): boolean {
    const listed = exp.split("");

    const openParentheses = listed.filter((c) => c === "(");
    const closedParentheses = listed.filter((c) => c === ")");

    return closedParentheses.length > openParentheses.length;
}

What this function does is it filters out all of the (s from the expression, and all of the )s, then sees which one has more. If there are more )s, it returns true, meaning we have to parse the expression. If it returns false, we add it to waiting.group.exp.

function valueIsOrInGroup(
    parsed: Expression<number> | null,
    waiting: Waiting<NumberOperator>,
    value: string
): ParsedWaitNext<number, NumberOperator, ExpectedNumVal> {
    if(value === ")") {
        // if closed parentheses
    } else if(waiting.group._tag === "grouped") {
        // if _tag is "grouped" then it can't be open parentheses
        // (unless it's nested)
    } else {
        // open parentheses
    }
}

Since there are 3 options here, let’s just create 3 more functions: valueIsClosedGroup, valueIsOpenGroup, and valueIsInGroup.

For valueIsInGroup, the only things we need to do is add the value to waiting.group.exp and update nextExp. Easy!

function valueIsInGroup(
    parsed: Expression<number> | null,
    waiting: Waiting<NumberOperator>,
    value: string
): ParsedWaitNext<number, NumberOperator, ExpectedNumVal> {
    return {
        parsed,
        waiting: {
            ...waiting, 
            group: {
                ...waiting.group,
                exp: waiting.group.exp + value,
            }
        },
        next: ["neg", "number", "group", "operator", "variable"]
    }
}

valueIsOpenParentheses() is also pretty easy:

function valueIsOpenParentheses(
    parsed: Expression<number> | null,
    waiting: Waiting<NumberOperator>
): ParsedWaitNext<number, NumberOperator, ExpectedNumVal> {
    return {
        parsed,
        waiting: {
            ...waiting,
            group: {_tag: "grouped", exp: ""}
        },
        next: ["neg", "number", "variable", "group"]
    }
}

And finally, valueIsClosedParentheses():

function shouldParseGroup(exp: string): boolean {
    const listed = exp.split("");

    const openParentheses = listed.filter((c) => c === "(");
    const closedParentheses = listed.filter((c) => c === ")");

    return closedParentheses.length > openParentheses.length;
}

function valueIsClosedParentheses(
    parsed: Expression<number> | null,
    waiting: Waiting<NumberOperator>
): ParsedWaitNext<number, NumberOperator, ExpectedNumVal> {
    const exp = waiting.group.exp;

    if(shouldParseGroup(exp)) {
        const parsedExpNoNeg = parseInput(exp);
        const parsedExp = waiting.negate 
            ? makeNumExp(parsedExpNoNeg, null, "neg") 
            : parsedExpNoNeg
        return {
            parsed: parsed === null
                ? parsedExp
                : makeNumExp(parsed, parsedExp, waiting.operator),
            waiting: {operator: null, group: {_tag: "ungrouped", exp: null}},
            next: ["operator", "group"]
        }
    }
    return {
        parsed,
        waiting: {
            ...waiting,
            group: {
                _tag: "grouped",
                exp: exp + ")"
            }
        },
        next: ["operator", "group"]
    }
}

First, the function checks if the expression has to be parsed using the function we made before.

If it does have to be parsed, it calls, parseInput() and parses it. It negates it if needed, and then combines it with parsed, if parsed isn’t null.

If it doesn’t have to be parsed, it does the same thing valueIsInGroup() does.

Okay! It’s time to put all of them into valueIsOrInGroup!

function valueIsInGroup(
    parsed: Expression<number> | null,
    waiting: Waiting<NumberOperator>,
    value: string
): ParsedWaitNext<number, NumberOperator, ExpectedNumVal> {
    return {
        parsed,
        waiting: {
            ...waiting, 
            group: {
                ...waiting.group,
                exp: waiting.group.exp + value,
            }
        },
        next: ["neg", "number", "group", "operator", "variable"]
    }
}
function valueIsOpenParentheses(
    parsed: Expression<number> | null,
    waiting: Waiting<NumberOperator>
): ParsedWaitNext<number, NumberOperator, ExpectedNumVal> {
    return {
        parsed,
        waiting: {
            ...waiting,
            group: {_tag: "grouped", exp: ""}
        },
        next: ["neg", "number", "variable", "group"]
    }
}

function shouldParseGroup(exp: string): boolean {
    const listed = exp.split("");

    const openParentheses = listed.filter((c) => c === "(");
    const closedParentheses = listed.filter((c) => c === ")");

    return closedParentheses.length > openParentheses.length;
}

function valueIsClosedParentheses(
    parsed: Expression<number> | null,
    waiting: Waiting<NumberOperator>
): ParsedWaitNext<number, NumberOperator, ExpectedNumVal> {
    const exp = waiting.group.exp;

    if(shouldParseGroup(exp)) {
        const parsedExpNoNeg = parseInput(exp);
        const parsedExp = waiting.negate 
            ? makeNumExp(parsedExpNoNeg, null, "neg") 
            : parsedExpNoNeg
        return {
            parsed: parsed === null
                ? parsedExp
                : makeNumExp(parsed, parsedExp, waiting.operator),
            waiting: {operator: null, group: {_tag: "ungrouped", exp: null}},
            next: ["operator", "group"]
        }
    }
    return {
        parsed,
        waiting: {
            ...waiting,
            group: {
                _tag: "grouped",
                exp: exp + ")"
            }
        },
        next: ["operator", "group"]
    }
}

function valueIsOrInGroup(
    parsed: Expression<number> | null,
    waiting: Waiting<NumberOperator>,
    value: string
): ParsedWaitNext<number, NumberOperator, ExpectedNumVal> {
    let pwn;
    if(value === ")") {
       pwn = valueIsClosedParentheses(parsed, waiting);
    } else if(waiting.group._tag === "grouped") {
        pwn = valueIsInGroup(parsed, waiting, value);
    } else {
        pwn = valueIsOpenParentheses(parsed, waiting);
    }
    return pwn;
}

And here’s how parseInput() looks with all the new functions added into it:


function parseInput(input: string): Expression<number> | null {
    const splitInp = input.split("");
    const withoutSpaces = listed.replaceAll(" ", "");
    const listed = joinSimilarities(withoutSpaces, "0123456789".split(""));

    let parsed: Expression<number> | null = null;
    let waiting: Waiting<NumberOperator> = {
        operator: null,
        negate: false,
        group: {
            _tag: "ungrouped", 
            exp: null
        }
    }
    let nextExp: ExpectedValue[] = ["number", "variable", "group", "neg"];

    for(let idx = 0; idx < listed.length; idx++) {
        const curVal: string = listed[idx];
        
        if(!isExpected(curVal, nextExp)) {
            throw "Error: Unexpected value"l
        }

        const shouldHandleGroup = waiting.group._tag === "grouped" || curVal === "(" || curVal === ")";

        const shouldHandleNeg = curVal === "-" && (waiting.operator !== null || parsed === null);

        const pwn: ParsedWaitNext< ... > = shouldHandleGroup
            ? valueIsOrInGroup(parsed, waiting, curVal)
            : shouldHandleNeg
                ? valueIsNeg(parsed, waiting)
                : (numberOperators as string[]).includes(curVal)
                    ? valueIsOperator(parsed, waiting, curVal)
                    : valueIsNumOrVar(
                        (variables as string[]).includes(curVal)
                            ? curVal
                            : JSON.parse(curVal)
                        parsed,
                        waiting
                    )
        
        parsed = pwn.parsed;
        waiting = pwn.waiting;
        nextExp = pwn.next;
    }
    return parsed;
}

Awesome! We’ve finally finished our parser!!

Go To:

    Visualization

  1. Intro
  2. Order of Operations
  3. Four Modules
  4. Operator Precedence

    5. Code

  5. Code Intro
  6. Parser
  7. Orderer
  8. Evaluator
  9. Simplifier

  10. Logic Tree
  11. Outro
< Code Intro Orderer >