Парсим математические выражения на чистом Javascript. Часть 3: алгоритм сортировочной станции

3 + 4 * 8 / (5 - 3)^2^3

3 4 8 * 5 3 - 2 3 ^ ^ / +

3 + 4 * 8 / (5 - 3)^2

2 * 9 / 2.5 + cos(pi) * max(3^2 * (7 - 1), x)

class ShuntingYardParser {
    constructor() {
        this.operators = {
            "+": {precedence: 1, associative: "left"},
            "-": {precedence: 1, associative: "left"},
            "*": {precedence: 2, associative: "left"},
            "/": {precedence: 2, associative: "left"},
            "^": {precedence: 3, associative: "right"},
            "~": {precedence: 3, associative: "right"}
        }
    }
}

parse(tokens) {
    const stack = []
    const rpn = []

    for (const token of tokens) {
        if (token.type === "number" || token.type === "constant" || token.type === "variable") {
            rpn.push(token)
        }
        else if (token.type === "function") {
            stack.push(token)
        }
        else if (token.type === "delimeter") {
            while (stack.length && stack[stack.length - 1].type !== "left_parenthesis")
                rpn.push(stack.pop())

            if (stack.length === 0)
                throw new Error(`"${token.value}" outside a function or without "(" (${token.start}:${token.end})`)
        }
        else if (token.type === "operator") {
            while (stack.length && this.isMorePrecedence(stack[stack.length - 1], this.operators[token.value]))
                rpn.push(stack.pop())

            stack.push(token)
        }
        else if (token.type === "left_parenthesis") {
            stack.push(token)
        }
        else if (token.type === "right_parenthesis") {
            while (stack.length && stack[stack.length - 1].type !== "left_parenthesis")
                rpn.push(stack.pop())

            if (stack.length === 0)
                throw new Error(`"(" missing before "${token.value}" (${token.start}:${token.end})`)

            stack.pop()

            if (stack.length && stack[stack.length - 1].type === "function")
                rpn.push(stack.pop())
        }

        prev = token
    }

    while (stack.length) {
        const token = stack.pop()

        if (token.type === "left_parenthesis")
            throw new Error(`the brackets are disbalanced (${token.start}:${token.end})`)

        rpn.push(token)
    }

    return rpn
}

isMorePrecedence(top, operator) {
    if (top.type != "operator")
        return false

    if (operator.associative === "right")
        return this.operators[top.value].precedence > operator.precedence

    return this.operators[top.value].precedence >= operator.precedence
}

const tokenizer = new ExpressionTokenizer({
    functions: ["sin", "cos", "tan", "max"],
    constants: ["pi", "e"]
})

const parser = new ShuntingYardParser()

parser.parse(tokenizer.tokenize("3 + 4")) // 3 4 +
parser.parse(tokenizer.tokenize("1 + 2 * 3")) // 1 2 3 * +
parser.parse(tokenizer.tokenize("3 + 4 * 8 / (5 - 3)^2")) // 3 4 8 * 5 3 - 2 ^ / +
parser.parse(tokenizer.tokenize("max(sin(x), cos(y))")) // x sin y cos max

// может ли токен быть унарным
isUnary(prev) {
    return prev === null || prev.type === "operator" || prev.type === "delimeter" || prev.type === "left_parenthesis"
}

parse(tokens) {
    const stack = []
    const rpn = []
    let prev = null // предыдущий токен

    for (token of tokens) {
        ...
        else if (token.type === "operator") {
            // если токен - является унарным, заменяем его на ~
            if (token.value === "-" && this.isUnary(prev))
                token.value = "~"

            ...
        }

        prev = token // запоминаем обработанный токен
    }

    ...
}

parser.parse(tokenizer.tokenize("-1")) // 1 ~
parser.parse(tokenizer.tokenize("-(1+4)")) // 1 4 + ~
parser.parse(tokenizer.tokenize("2 - -3")) // 2 3 ~ -
parser.parse(tokenizer.tokenize("-----5")) // 5 ~ ~ ~ ~ ~
parser.parse(tokenizer.tokenize("max(-4, -5)")) // 4 ~ 5 ~ max
parser.parse(tokenizer.tokenize("-4^-2^-3")) // 4 2 3 ~ ^ ~ ^ ~

parser.parse(tokenizer.tokenize("1 2 +")) // 1 2 +
parser.parse(tokenizer.tokenize("5 + + 7")) // 5 + 7 +
parser.parse(tokenizer.tokenize("1 2 3 + (,) - * / 4 5 6 (^)")) // 1 2 3 + * 4 5 6 ^ / -
parser.parse(tokenizer.tokenize("sin cos 2 max 7")) // 2 7 max cos sin
parser.parse(tokenizer.tokenize("max(,)")) // max
parser.parse(tokenizer.tokenize("5 + 6 +")) // 5 6 + +

parse(tokens) {
    const stack = []
    const rpn = []
    let prev = null
    let expect = "operand"

    for (const token of tokens) {
        if (token.type === "number" || token.type === "constant" || token.type === "variable") {
            expect = this.parseOperand(token, rpn, expect)
        }
        else if (token.type === "function") {
            expect = this.parseFunction(token, stack, expect)
        }
        else if (token.type === "delimeter") {
            expect = this.parseDelimeter(token, stack, rpn, expect)
        }
        else if (token.type === "operator" && token.value === "-" && this.isUnary(prev)) {
            expect = this.parseUnary(token, stack, expect)
        }
        else if (token.type === "operator") {
            expect = this.parseOperator(token, stack, rpn, expect)
        }
        else if (token.type === "left_parenthesis") {
            expect = this.parseLeftParenthesis(token, stack, expect)
        }
        else if (token.type === "right_parenthesis") {
            expect = this.parseRightParenthesis(token, stack, rpn, expect)
        }
        else
            throw new Error(`got invalid token: "${token.value}" (${token.start}:${token.end})`)

        prev = token
    }

    this.parseLastOperators(stack, rpn, expect)
    return rpn
}

// обработка операции
parseOperand(token, rpn, expect) {
    if (expect !== "operand")
        throw new Error(`expected ${expect}, but got "${token.value}" (${token.start}:${token.end})`)

    rpn.push(token)
    return "operator"
}

// обработка функции
parseFunction(token, stack, expect) {
    if (expect !== "operand")
        throw new Error(`expected ${expect}, but got "${token.value}" (${token.start}:${token.end})`)

    stack.push(token)
    return "("
}

// обработка разделителя аргументов
parseDelimeter(token, stack, rpn, expect) {
    if (expect !== "operator")
        throw new Error(`expected ${expect}, but got "${token.value}" (${token.start}:${token.end})`)

    while (stack.length && stack[stack.length - 1].type !== "left_parenthesis")
        rpn.push(stack.pop())

    if (stack.length === 0)
        throw new Error(`"${token.value}" outside a function or without "(" (${token.start}:${token.end})`)

    return "operand"
}

// обработка унарного минуса
parseUnary(token, stack, expect) {
    if (expect !== "operand")
        throw new Error(`expected ${expect}, but got unary "${token.value}" (${token.start}:${token.end})`)

    token.value = "~"
    stack.push(token)
    return "operand"
}

// обработка операции
parseOperator(token, stack, rpn, expect) {
    if (expect !== "operator")
        throw new Error(`expected ${expect}, but got "${token.value}" (${token.start}:${token.end})`)

    while (stack.length && this.isMorePrecedence(stack[stack.length - 1], this.operators[token.value]))
        rpn.push(stack.pop())

    stack.push(token)
    return "operand"
}

// обработка открывающей скобки
parseLeftParenthesis(token, stack, expect) {
    if (expect === "operator")
        throw new Error(`expected ${expect}, but got "${token.value}" (${token.start}:${token.end})`)

    stack.push(token)
    return "operand"
}

// обработка закрывающей скобки
parseRightParenthesis(token, stack, rpn, expect) {
    if (expect !== "operator")
        throw new Error(`expect ${expect}, but got ")" (${token.start}:${token.end})`)

    while (stack.length && stack[stack.length - 1].type !== "left_parenthesis")
        rpn.push(stack.pop())

    if (stack.length === 0)
        throw new Error(`"(" missing before "${token.value}" (${token.start}:${token.end})`)

    stack.pop()

    if (stack.length && stack[stack.length - 1].type === "function")
        rpn.push(stack.pop())

    return "operator"
}

// обработка оставшихся в стеке операций
parseLastOperators(stack, rpn, expect) {
    while (stack.length) {
        const token = stack.pop()

        if (expect != "operator")
            throw new Error(`expect ${expect}, but got "${token.value}" (${token.start}:${token.end})`)

        if (token.type === "left_parenthesis")
            throw new Error(`the brackets are disbalanced (${token.start}:${token.end})`)

        rpn.push(token)
    }
}

parser.parse(tokenizer.tokenize("1 2 +")) // Error: expected "operator", but got "2" (2:3)
parser.parse(tokenizer.tokenize("5 + + 7")) // Error: expected operand, but got "+" (4:5)
parser.parse(tokenizer.tokenize("1 2 3 + (,) - * / 4 5 6 (^)")) // expected "operator", but got "2" (2:3)
parser.parse(tokenizer.tokenize("sin cos 2 max 7")) // Error: "(", but got "cos" (4:7)
parser.parse(tokenizer.tokenize("max(,)")) // Error: expected operand, but got "," (4:5)
parser.parse(tokenizer.tokenize("5 + 6 +")) // Error: expect operand, but got "+" (6:7)
parser.parse(tokenizer.tokenize("1 + (2")) // Error: the brackets are disbalanced (4:5)
parser.parse(tokenizer.tokenize("sin(7))")) // Error: "(" missing before ")" (6:7)

// а вот тут не всё в порядке
parser.parse(tokenizer.tokenize("sin(1, 2, 3, 4)")) // 1 2 3 4 sin
parser.parse(tokenizer.tokenize("max(sin(1, 2))")) // 1 2 sin max
parser.parse(tokenizer.tokenize("max(1)")) // 1 max

constructor(functions) {
    this.functions = functions
    ...
}

parse(tokens) {
    ...
    const argsCount = []

    for (const token of tokens) {
        ...
        else if (token.type === "function") {
            expect = this.parseFunction(token, stack, argsCount, expect)
        }
        else if (token.type === "delimeter") {
            expect = this.parseDelimeter(token, stack, rpn, argsCount, expect)
        }
        else if (token.type === "right_parenthesis") {
            expect = this.parseRightParenthesis(token, stack, rpn, argsCount, expect)
        }
        ...
    }
    ...
}

parseFunction(token, stack, argsCount, expect) {
    ...
    argsCount.push(1)
    return "("
}

parseDelimeter(token, stack, rpn, argsCount, expect) {
    ...

    if (argsCount.length === 0)
        throw new Error(`"${token.value}" outside a function (${token.start}:${token.end})`)

    argsCount[argsCount.length - 1]++
    return "operand"
}

parseRightParenthesis(token, stack, rpn, argsCount, expect) {
    ...

    if (stack.length && stack[stack.length - 1].type === "function") {
        const func = this.functions[stack[stack.length - 1]]
        const args = argsCount.pop()

        if (args != func.args)
            throw new Error(`invalid "${func.value}" arguments count: expected ${func.args}, got ${args} "${token.value}" (${token.start}:${token.end})`)

        rpn.push(stack.pop())
    }

    return "operator"
}

parser.parse(tokenizer.tokenize("sin(1, 2, 3, 4)")) // Error: invalid "sin" arguments count: expected 1, got 4 ")" (14:15)
parser.parse(tokenizer.tokenize("max(sin(1, 2))")) // Error: invalid "sin" arguments count: expected 1, got 2 ")" (12:13)
parser.parse(tokenizer.tokenize("max(1)")) // Error: invalid "max" arguments count: expected 2, got 1 ")" (5:6)

class ExpressionParser {
    constructor(expression) {
        const functions = this.initFunctions()
        const constants = this.initConstans()
        const operators = this.initOperators()

        const tokenizer = new ExpressionTokenizer({
            functions: Object.keys(functions),
            constants: Object.keys(constants)
        })

        const parser = new ShuntingYardParser(functions)

        this.evaluator = new ExpressionEvaluator({constants, functions, operators})
        this.rpn = parser.parse(tokenizer.tokenize(expression))
        this.variables = {}
    }

    setVariable(name, value) {
        this.variables[name] = value
    }

    evaluate() {
        return this.evaluator.evaluate({rpn: this.rpn, variables: this.variables})
    }

    initFunctions() {        
        return {
            "sin": {args: 1, evaluate: Math.sin},
            "cos": {args: 1, evaluate: Math.cos},
            "tan": {args: 1, evaluate: Math.tan},
            "max": {args: 2, evaluate: Math.max},
            // и многие многие другие
        }
    }

    initConstans() {
        return {
            "pi": Math.PI,
            "e": Math.E
        }
    }

    initOperators() {
        return {
            "+": {args: 2, evaluate: (arg1, arg2) => arg1 + arg2},
            "-": {args: 2, evaluate: (arg1, arg2) => arg1 - arg2},
            "*": {args: 2, evaluate: (arg1, arg2) => arg1 * arg2},
            "/": {args: 2, evaluate: (arg1, arg2) => arg1 / arg2},
            "^": {args: 2, evaluate: (arg1, arg2) => arg1 ** arg2},
            "~": {args: 1, evaluate: (arg) => -arg}
        }
    }
}

function TestParser(expression, expected, variables = {}, eps = 1e-15) {
    try {
        const parser = new ExpressionParser(expression)

        for (const [variable, value] of Object.entries(variables))
            parser.setVariable(variable, value)

        const result = parser.evaluate()

        if (Math.abs(result - expected) < eps)
            console.log(`%c${expression} = ${result}`, "color: green")
        else
            console.log(`%c${expression} = ${result}, but expected ${expected}`, "color: red")
    }
    catch (error) {
        console.log(`%c"${expression}" is invalid: ${error.message}`, expected === null ? "color: green" : "color: red")
    }
}

// проверяем корректные выражения
TestParser("1", 1) // 1 = 1
TestParser("1 + 2 * 3", 7) // 1 + 2 * 3 = 7
TestParser("-(1 + 2) * 3 - 4", -13) // -(1 + 2) * 3 - 4 = -13
TestParser("-2^2", -4) // -2^2 = -4
TestParser("(-2)^2", 4) // (-2)^2 = 4
TestParser("-2^-2", -0.25) // -2^-2 = -0.25
TestParser("(-2)^-2", 0.25) // (-2)^-2 = 0.25
TestParser("max(5 + 2^3, -7 * -9)", 63) // max(5 + 2^3, -7 * -9) = 63
TestParser("cos(7 - 5)^2 + sin(4^0.5)^2", 1) // cos(7 - 5)^2 + sin(4^0.5)^2 = 1
TestParser("sin(x) * (pi/-x - 5)^2", -9, {"x": -Math.PI / 2}) // sin(x) * (pi/-x - 5)^2 = -9

// проверяем некорректные выражения
TestParser("()", null) // "()" is invalid: expect operand, but got ")" (1:2)
TestParser("max(1)", null) // "max(1)" is invalid: invalid "max" arguments count: expected 2, got 1 ")" (5:6)
TestParser("sin(1, 5)", null) // "sin(1, 5)" is invalid: invalid "sin" arguments count: expected 1, got 2 ")" (8:9)
TestParser("sin cos 2 max 7", null) // "sin cos 2 max 7" is invalid: expected (, but got "cos" (4:7)

rpn = [] // выражение в обратной польской записи
stack = [] // стек
args = [] // стек количества аргументов функций
expect = "operand" // ожидаемое состояние
prev = null // прошлый токен

for token in tokens:
    if token is a constant, number or variable:
        assert expect is "operand"
        rpn.push(token)
        expect = "operator"

    elif token is a function:
        assert expect is "operand"
        stack.push(token)
        args.push(1)
        expect = "("

    elif token is delimeter:
        assert expect is "operator"
        while stack.top is not "(":
            rpn.push(stack.pop())

        assert stack is not empty and args is not empty
        args.top++ // увеличиваем количество аргументов функции
        expect = "operand"

    elif token is "-" operator and prev is null, operator, delimeter or "(":
        assert expect is "operand"
        stack.push("~") // меняем токен на унарный
        expect = "operand"

    elif token is operator:
        assert expect is "operator"
        while stack.top is operator and is_more_precedence(stack.top, token):
            rpn.push(stack.pop())

        stack.push(token)
        expect = "operand"

    elif token is "(":
        assert expect is "(" or "operand"
        stack.push(token)
        expect = "operand"

    elif token is ")":
        assert expect is "operator"

        while stack.top is not "(":
            rpn.push(stack.pop())

        assert stack is not empty
        stack.pop()

        if stack.top is function:
            assert args.pop() is equal to function arguments count // проверяем совпадение количества аргументов
            rpn.push(stack.pop())

        expect = "operator"

    prev = token

while stack is not empty:
    assert expect is operator and not "("
    rpn.push(stack.pop())

class ShuntingYardParser {
    constructor(functions) {
        this.functions = functions
        this.operators = {
            "+": {precedence: 1, associative: "left"},
            "-": {precedence: 1, associative: "left"},
            "*": {precedence: 2, associative: "left"},
            "/": {precedence: 2, associative: "left"},
            "^": {precedence: 3, associative: "right"},
            "~": {precedence: 3, associative: "right"}
        }
    }

    parse(tokens) {
        const stack = []
        const argsCount = []
        const rpn = []
        let prev = null
        let expect = "operand"

        for (const token of tokens) {
            if (token.type === "number" || token.type === "constant" || token.type === "variable") {
                expect = this.parseOperand(token, rpn, expect)
            }
            else if (token.type === "function") {
                expect = this.parseFunction(token, stack, argsCount, expect)
            }
            else if (token.type === "delimeter") {
                expect = this.parseDelimeter(token, stack, rpn, argsCount, expect)
            }
            else if (token.type === "operator" && token.value === "-" && this.isUnary(prev)) {
                expect = this.parseUnary(token, stack, expect)
            }
            else if (token.type === "operator") {
                expect = this.parseOperator(token, stack, rpn, expect)
            }
            else if (token.type === "left_parenthesis") {
                expect = this.parseLeftParenthesis(token, stack, expect)
            }
            else if (token.type === "right_parenthesis") {
                expect = this.parseRightParenthesis(token, stack, rpn, argsCount, expect)
            }
            else
                throw new Error(`got invalid token: "${token.value}" (${token.start}:${token.end})`)

            prev = token
        }

        this.parseLastOperators(stack, rpn, expect)
        return rpn
    }

    isUnary(prev) {
        return prev === null || prev.type === "operator" || prev.type === "delimeter" || prev.type === "left_parenthesis"
    }

    isMorePrecedence(top, operator) {
        if (top.type !== "operator")
            return false

        if (operator.associative === "right")
            return this.operators[top.value].precedence > operator.precedence

        return this.operators[top.value].precedence >= operator.precedence
    }

    parseOperand(token, rpn, expect) {
        if (expect !== "operand")
            throw new Error(`expected ${expect}, but got "${token.value}" (${token.start}:${token.end})`)

        rpn.push(token)
        return "operator"
    }

    parseFunction(token, stack, argsCount, expect) {
        if (expect !== "operand")
            throw new Error(`expected ${expect}, but got "${token.value}" (${token.start}:${token.end})`)

        stack.push(token)
        argsCount.push(1)
        return "("
    }

    parseDelimeter(token, stack, rpn, argsCount, expect) {
        if (expect !== "operator")
            throw new Error(`expected ${expect}, but got "${token.value}" (${token.start}:${token.end})`)

        while (stack.length && stack[stack.length - 1].type !== "left_parenthesis")
            rpn.push(stack.pop())

        if (stack.length === 0)
            throw new Error(`"${token.value}" outside a function or without "(" (${token.start}:${token.end})`)

        if (argsCount.length === 0)
            throw new Error(`"${token.value}" outside a function (${token.start}:${token.end})`)

        argsCount[argsCount.length - 1]++
        return "operand"
    }

    parseUnary(token, stack, expect) {
        if (expect !== "operand")
            throw new Error(`expected ${expect}, but got unary "${token.value}" (${token.start}:${token.end})`)

        token.value = "~"
        stack.push(token)
        return "operand"
    }

    parseOperator(token, stack, rpn, expect) {
        if (expect !== "operator")
            throw new Error(`expected ${expect}, but got "${token.value}" (${token.start}:${token.end})`)

        while (stack.length && this.isMorePrecedence(stack[stack.length - 1], this.operators[token.value]))
            rpn.push(stack.pop())

        stack.push(token)
        return "operand"
    }

    parseLeftParenthesis(token, stack, expect) {
        if (expect === "operator")
            throw new Error(`expected ${expect}, but got "${token.value}" (${token.start}:${token.end})`)

        stack.push(token)
        return "operand"
    }

    parseRightParenthesis(token, stack, rpn, argsCount, expect) {
        if (expect !== "operator")
            throw new Error(`expect ${expect}, but got ")" (${token.start}:${token.end})`)

        while (stack.length && stack[stack.length - 1].type !== "left_parenthesis")
            rpn.push(stack.pop())

        if (stack.length === 0)
            throw new Error(`"(" missing before "${token.value}" (${token.start}:${token.end})`)

        stack.pop()

        if (stack.length && stack[stack.length - 1].type === "function") {
            const func = this.functions[stack[stack.length - 1].value]
            const args = argsCount.pop()

            if (args != func.args)
                throw new Error(`invalid "${stack[stack.length - 1].value}" arguments count: expected ${func.args}, got ${args} "${token.value}" (${token.start}:${token.end})`)

            rpn.push(stack.pop())
        }

        return "operator"
    }

    parseLastOperators(stack, rpn, expect) {
        while (stack.length) {
            const token = stack.pop()

            if (expect != "operator")
                throw new Error(`expect ${expect}, but got "${token.value}" (${token.start}:${token.end})`)

            if (token.type === "left_parenthesis")
                throw new Error(`the brackets are disbalanced (${token.start}:${token.end})`)

            rpn.push(token)
        }
    }
}