Другой подход - превратить вашу строку в массив, который можно оценить как стек, а затем выполнить простую оценку этого стека. Например, мы можем превратить "10 - 20 + 30 * 2 / 10" в [10, 20, "-", 30, "+", 2, "*", 10, "/"], а затем оценить его, последовательно заменив два верхних элемента стека значением текущей операции, примененной к ним.
Этот метод предназначен только для операций слева направо. Он игнорирует приоритет операторов и не может обрабатывать круглые скобки или небинарные операции. Но этого может хватить для ваших нужд.
Вот реализация:
const evalExpr = (ops) => (expr) => expr
.replace (/([-+*\/])(\s)*(\d+)/g, (_, a, b, c) => c + b + a)
.split (/\s+/)
.map (n => Number(n) || n)
.reduce (
(stack, symbol, _, __, op = ops[symbol]) => op
? [... stack.slice(0, -2), op(...stack.slice(-2))]
: [... stack, symbol]
, []
) [0];
const ops = {
'+': (a, b) => a + b,
'-': (a, b) => a - b,
'*': (a, b) => a * b,
'/': (a, b) => a / b,
};
const evalNumericExpr = evalExpr (ops);
// Test
[
"1 + 1",
"1 - 1",
"1 * 1",
"1 / 1",
"2 + 4 + 7",
"5 - 7",
"5 * 2 + 10",
"10 - 20 + 30 * 2 / 10",
"1 + 5 * 2 + 12 * 2 * 2",
"10 + 13 - 5 * 3 + 12 / 3 + 3"
]
.forEach (expr => console .log (`${expr} ==> ${evalNumericExpr (expr)}`))
Шаги replace, split и map вместе превращают эту строку в стек, готовый к обработке. Шаг reduce фактически обрабатывает этот массив, добавляя и удаляя элементы в стеке. Когда "10 - 20 + 30 * 2 / 10" станет [10, 20, "-", 30, "+", 2, "*", 10, "/"], сокращение будет происходить следующим образом:
stack: [], next: 10 // Push 10 onto the stack
stack: [10], next: 20 // Push 20 onto the stack
stack: [10, 20], next: '-' // Pop 10 and 20 from the stack. Push (10 - 20) to it
stack: [-10], next: 30 // Push 30 to the stack
stack: [-10, 30], next: '+' // Pop -10 and 30 from the stack. Push (-10 + 30) to it
stack: [20], next: 2 // Push 2 to the stack
stack: [20, 2], next: '*' // Pop 20 and 2 from the stack. Push (20 * 2) to it
stack: [40], next: 10 // Push 10 to the stack
stack: [40, 10], next: '/' // Pop 40 and 10 from the stack. Push (40 / 10) to it
stack: [4] // For a well-formed expression, the stack now has just
// one element on it, and that's your result.
Есть много способов расширить это. Очевидно, что добавлять новые бинарные операции тривиально. Мы также могли бы добавить к сокращению другие операции с арностью (хотя было бы сложнее преобразовать строку в формат стека), заменив -2 в сокращении на -op.length. Если бы мы хотели обрабатывать десятичные числа, мы могли бы просто изменить регулярное выражение на что-то вроде /([-+*\/])(\s)*(\-?\d+(:?\.\d+)?)/g.
И поздравляю нас. Мы только что написали начало интерпретатора Forth!
Обновлять
В частности, был задан вопрос о том, как это сделать рекурсивно, и я написал рекурсивную версию, которая в целом была проще, чем приведенная выше. Но потом я понял, как его можно легко расширить для обработки круглых скобок и соблюдения приоритета операторов. Это уже не обязательно проще, но это интересный подход, который мы могли бы легко расширить с помощью других операторов и различий уровней приоритета:
// Does not test for well-formedness. Will likely return NaN for
// ill-formed expression strings
const evalNumericExpr = (
expr,
[regex, fn, ops] = [
// parentheses
[/\(([^())]*)\)/, (ops, expr, regex) => evalNumericExpr (expr.replace(regex, (_, e) => evalNumericExpr(e))), {}],
// multiplication and division
[/\s*(\-?\d+)\s*([/*])\s*(\-?\d+)/, (ops, expr, regex) => evalNumericExpr (expr .replace (
regex,
(_, a, op, b) => String(ops[op](Number(a), Number(b)))
)), {'*': (a, b) => a * b, '/': (a, b) => a / b}],
// addition and subtraction
[/\s*(\-?\d+)\s*([+-])\s*(\-?\d+)/, (ops, expr, regex) => evalNumericExpr (expr .replace (
regex,
(_, a, op, b) => String(ops[op](Number(a), Number(b)))
)), {'+': (a, b) => a + b, '-': (a, b) => a - b}],
// everything else
[/.?/, (ops, expr, regex) => Number(expr.trim()), {}]
].find(([regex, fn, ops]) => regex.test(expr))
) => fn(ops, expr, regex)
// Test
; [
"1 + 5",
"7 - 2",
"3 * 5",
"21 / 3",
"2 + 4 + 7",
"5 - 7",
"5 * 2 + 10",
"5 * 2 + (3 * 5)",
"10 - 20 + 30 * 2 / 10",
"10 - ((4 * 5) - (5 * 6)) * 2 / 10",
"10 - ((4 * (2 + 3)) - (5 * 6)) * 2 / 10",
"1 + 5 * 2 + 12 * 2 * 2",
"10 + 13 - 5 * 3 + 12 / 3 + 3"
].forEach (expr => console .log (`${expr} ==> ${evalNumericExpr (expr)}`))
Большим преимуществом этого подхода является то, что его можно легко распространить на любые математические операторы, которые мы выберем. И есть место для дальнейшего упрощения.
Обновление 2
Я был не очень доволен кодом из предыдущего обновления. Эта версия кажется мне более чистой, а также добавляет возведение в степень. Вот первый шаг к этому:
const evalNumericExpr = (() => {
const ops = [
[ // grouping
/\(([^()]+)\)/,
(evaluator, subexpr) => evaluator(subexpr)
], [ //exponentiation
/([-+]?\d+)\s*[\^]\s*([-+]?\d+)([^\^]*)$/,
(_, base, exp, rest) => `${base ** exp}${rest}`
], [ // multiplication, divide, remainder
/([-+]?\d+)\s*([*%\/])\s*([-+]?\d+)/,
((ops) => ((_, a, op, b) => ops [op] (Number (a), Number (b))))(
{'*': (a, b) => a * b, '/': (a, b) => a / b, '%': (a, b) => a % b}
)
], [ // addition, subtraction
/([-+]?\d+)\s*([+-])\s*([-+]?\d+)/,
((ops) => ((_, a, op, b) => ops [op] (Number (a), Number (b))))(
{'+': (a, b) => a + b, '-': (a, b) => a - b}
)
]
]
const evaluator = (expr) => Number(ops .reduce(
(expr, [regex, fn]) => regex .test (expr)
? evaluator(expr .replace (regex, (...args) => fn (evaluator, ...args .slice (1))))
: expr,
expr
))
return evaluator
})()
// Test
; [
"1 + 3",
"7 - 2",
"2 * 6",
"12 / 4",
"2 + 4 + 7",
"5 * 2 + 10",
"10 - 20 + 30 * 2 / 10",
"1 + 5 * 2 + 12 * 2 * 2",
"10 + 13 - 5 * 3 + 12 / 3 + 3",
"10 + (13 - 5) * 3 + 12 / 3 + 3",
"5 * (4 + (2 * (1 + 1 + 1)))",
"5 ^ 2",
"5 ^ 2 * 2",
"2 ^ 3 ^ 2", // Note: should parse as `2 ^ (3 ^ 2)`, not `(2 ^ 3) ^ 2`
"2 ^ 3 ^ 2 + 3 ^ 3 * 2",
]
.forEach (expr => console .log (`${expr} ==> ${evalNumericExpr (expr)}`))
Мы работаем, связывая регулярное выражение с функцией, которая будет использоваться как обратный вызов replace вместе с этим регулярным выражением. Каждая такая пара запускается повторно до тех пор, пока на входе не останется совпадений.
Сначала он обрабатывает группировку с помощью круглых скобок (изнутри наружу), затем возведение в степень, затем умножение, деление и остатки и, наконец, сложение и вычитание. Этот порядок основан на стандартном приоритете операторов JS диаграмма. Группировка скобок повторяется внутри перед продолжением, и все функции повторяются в оставшемся выражении. Обратите внимание, что возведение в степень, которое правильно связывает, требует немного дополнительной работы, включая оставшуюся часть строки в качестве группы захвата, проверяя, что она не включает никаких операторов возведения в степень; это может быть лучше написано с негативным прогнозом, но я не очень разбираюсь в регулярных выражениях. Также обратите внимание, что я использую курсор (^) для оператора возведения в степень; его должно быть достаточно легко заменить на двойную звездочку (**), если это предпочтительнее.
Для сложного выражения это может происходить следующим образом:
2 ^ 3 ^ (4 ^ 2 - 5 * 3 + 1) - (((2 + 2) * (2 * 5) ^ 2) + (2 * 5 * 7))
4 ^ 2 - 5 * 3 + 1 // grouping
16 - 5 * 3 + 1 // exponentiation
16 - 15 + 1 // multiplication
1 + 1 // subtraction
2 // addition
2 ^ 3 ^ 2 - (((2 + 2) * (2 * 5) ^ 2) + (2 * 5 * 7))
2 + 2 // grouping
4 // addition
2 ^ 3 ^ 2 - (( 4 * (2 * 5) ^ 2) + (2 * 5 * 7))
2 * 5 // grouping
10 // multiplication
2 ^ 3 ^ 2 - (( 4 * 10 ^ 2) + (2 * 5 * 7))
4 * 10 ^ 2 // grouping
4 * 100 // exponentiation
400 // multiplication
2 ^ 3 ^ 2 - ( 400 + (2 * 5 * 7))
2 * 5 * 7 // grouping
10 * 7 // multiplication
70 // multiplication
2 ^ 3 ^ 2 - ( 400 + 70)
400 + 70 // grouping
470 // addition
2 ^ 3 ^ 2 - 470
2 ^ 9 - 470 // expoentiation
512 - 470 // exponentiation
42 // subtraction
person
Scott Sauyet
schedule
13.12.2019
