如何使用递归函数实现内置函数.eval()
How to implement build in function .eval() with recursive function
黑码，
我有一个字符串“1+1”，javascript 内置函数 eval() 我可以执行 eval(“1+1”) 所以 return 值将为 2
但是如果我想在 javascript 中将这个概念实现为递归函数呢？
function evaluate(str) {
}
evaluate("1+1");
evaluate("1-1");
evaluate("1*1");
evaluate("1/1");
我试过的是
function evaluate(str) {
if (str.length === 0) {
return "";
}else{
let angka;
let symbol;
for (let i = 0; i < str.length; i++) {
if (isNaN(str[i])) {
symbol = str[i];
break;
}else{
angka = str[i];
}
}
switch (symbol) {
case "+":
return angka + evaluate(str.slice(1));
case "-":
return angka - evaluate(str.slice(1));
case "/":
return angka / evaluate(str.slice(1));
case "*":
return angka * evaluate(str.slice(1));
default:
return parseInt(str[0]) + evaluate(str.slice(1));
}
}
}
function evaluate(str) {
if (str.length === 0) {
return ""
}
let numbers = "";
let operator = "";
let lastIndex = 0;
for (let i = 0; i <= str.length; i++) {
if (!isNaN(parseInt(str[i]))) {
numbers += parseInt(str[i]);
}else{
operator = str[i];
lastIndex = i;
break;
}
}
// console.log(numbers, " " , operator , " " , lastIndex);
lastIndex = lastIndex < 1 ? 1 : lastIndex;
if (operator === "+") {
return numbers + evaluate(str.slice(lastIndex));
}
}
function evaluate(str) {
if (str.length === 0) {
return 1;
}else{
let numbers = "";
for (let i = 0; i <= str.length; i++) {
if(parseInt(str[i]) >= 0){
numbers = numbers + "+" + str[i];
}else{
let lengthNumbers = numbers.length > 1 ? numbers.length : 1;
let tempNumbers = numbers;
numbers = "";
return tempNumbers + evaluate(str.slice(lengthNumbers))
}
}
}
}
===========
已更新
我是多么笨:)，现在这是我的答案（根据下面的解决方案），谢谢大家
function evaluate(str) {
if(str.match(/[*/+-]/)){
let numbers = "";
for (let i = 0; i < str.length; i++) {
switch (str[i]) {
case "+":
return parseInt(numbers) + evaluate(str.slice(numbers.length+1))
case "*":
return parseInt(numbers) * evaluate(str.slice(numbers.length+1))
case "/":
return parseInt(numbers) / evaluate(str.slice(numbers.length+1))
case "-":
return parseInt(numbers) - evaluate(str.slice(numbers.length+1))
default:
numbers += str[i];
break;
}
}
}else{
return parseInt(str[0]);
}
}
console.log(evaluate('1+2+3+4+5')) // 15
console.log(evaluate('1*2*3*4*5')) // 120
console.log(evaluate('20/4')) // 5
console.log(evaluate('20-6')) // 14
而且没有人工作！我知道 eval 会拯救我的一天，但在这种情况下我需要解决这个问题，谢谢。
你们非常亲密。它需要更复杂一点。
请阅读代码中的注释以了解其工作原理：
function evaluate(str) {
if (str.length === 0) {
return ""
}
// Function to apply the operator from right to left
const applyOperator = (operator, left, right) => {
result = left;
switch(operator) {
case '+':
result += right;
break;
case '-':
result -= right;
break;
case '*':
result *= right;
break;
case '/':
// Avoid division by zero
if(right !== 0) {
result /= right;
}
break;
}
return result;
}
let result = 0;
let numbers = "";
let operator = null;
for (let i = 0; i < str.length; i++) {
let c = str[i]; // Isolate the character
let isLast = i === str.length - 1; // Flag to check if we're on the last character
// Ignore spaces or tabs
if (c === ' ' || c === '\t') {
continue;
}
// Check if c is a number
if (!isNaN(parseInt(c))) {
// If it's a number add it to the number builder
numbers += c;
// If it's not the last character then continue to the next character
if(!isLast) {
continue;
}
}
// Convert the numbers stack into an integer and reset the stack
let number = parseInt(numbers);
numbers = '';
// If there was no operator before,
// then just set the result with the number and store the operator for the next calculation
if(operator === null) {
result = number;
operator = c;
} else {
// Apply the previous operator the the result using the number
result = applyOperator(operator, result, number);
// Store the current operator for the next calculation
operator = c;
}
}
return result;
}
document.getElementById('results').textContent =
[
"1 + 1",
"1 - 1",
"1 * 1",
"1 / 1",
"2 + 4 + 7",
"5 - 7",
"5 * 2 + 10",
"10 - 20 + 30 * 2 / 10"
].map(exp => `${exp} = ${evaluate(exp)}`).join('\n');
<pre id="results"></pre>
编辑
我不认为我们试图在这里实现某种 compiling/interpreting 引擎，但为了测试结果，这里是一个以正确顺序执行每个算术运算的版本 *, /, -, +:
function evaluate(str) {
if (str.length === 0) {
return ""
}
// Function to apply the operator from right to left
const applyOperator = (operator, left, right) => {
result = left;
switch(operator) {
case '+':
result += right;
break;
case '-':
result -= right;
break;
case '*':
result *= right;
break;
case '/':
// Avoid division by zero
if(right !== 0) {
result /= right;
}
break;
}
return result;
}
const passApply = (exp, opApply) => {
let result = 0;
let numbers = "";
let operator = null;
let prevWasOp = false;
let sign = '';
let parsed = '';
for (let i = 0; i < exp.length; i++) {
let c = exp[i]; // Isolate the character
let isLast = i === exp.length - 1; // Flag to check if we're on the last character
// Ignore spaces or tabs
if (c === ' ' || c === '\t') {
continue;
}
// Check if c is a number
if (!isNaN(parseInt(c))) {
// If it's a number add it to the number builder
numbers += c;
prevWasOp = false;
// If it's not the last character then continue to the next character
if(!isLast) {
continue;
}
} else if(prevWasOp || i === 0) {
// Checked for signed number
if(/[\+-]/.test(c)) {
sign = c;
continue;
}
prevWasOp = false;
}
// Convert the numbers stack into an integer and reset the stack
let number = parseInt(`${sign}${numbers}`);
// Reset the sign if there was any
sign = '';
// If there was no operator before,
// then just set the result with the number and store the operator for the next calculation
if(operator === null) {
result = number;
operator = c;
if(opApply !== operator) {
parsed += `${numbers}${operator}`;
result = 0;
}
} else {
if(opApply === operator) {
// Apply the previous operator the the result using the number
result = applyOperator(operator, result, number);
// Store the current operator for the next calculation
if(c !== opApply) {
parsed += `${result}`;
if(!isLast) {
parsed += `${c}`;
}
result = 0;
}
operator = c;
} else {
if(c !== opApply) {
parsed += `${numbers}`;
if(!isLast) {
parsed += `${c}`;
}
}
operator = c;
result = number;
}
}
numbers = '';
prevWasOp = ['+', '-', '*', '/'].indexOf(c) >= 0;
}
return parsed;
}
// Exeture each operator pass
const mulPass = passApply(str, '*');
const divPass = passApply(mulPass, '/');
const subPass = passApply(divPass, '-');
const addPass = passApply(subPass, '+');
// Convert result to int and return the result
return parseInt(result);
}
document.getElementById('results').textContent =
[
"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"
].map(exp => {
const result = evaluate(exp);
return `${exp} = ${result} eval(${result === eval(exp) ? 'OK' : 'ERROR'})`;
}).join('\n');
<pre id="results"></pre>
另一种方法是将您的字符串变成一个可以作为堆栈计算的数组，然后对该堆栈进行简单的计算。例如，我们可以将 "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 interpreter!
的开头
更新
题目具体问的是如何递归的，我写了一个递归的版本，总体上比上面的简单。但后来我意识到如何轻松扩展它以处理括号并尊重运算符优先级。它不再一定更简单，但它是一种有趣的方法，我们可以使用其他运算符和不同的优先级轻松扩展它：
// 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 operator precedence 图表。括号的分组在继续之前在内部重复出现，并且所有函数在剩余的表达式上重复出现。请注意，正确关联的求幂有一些额外的工作要做，包括将字符串的其余部分作为捕获组，测试它不包含任何求幂运算符；这可能更好地写成负面的前瞻性，但我不是一个正则表达式专家。另请注意，我将插入符号 (^) 用于求幂运算符；如果愿意，更改为双星号 (**) 应该很容易。
对于一个复杂的表达式，它可能是这样进行的：
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
试试这个代码
function evaluate(str) {
var reg = /[*/+-]/
if(str.match(reg)){
var temp = ''
for(let i = 0; i < str.length; i++){
if(str[i] === '+') {
return parseInt(temp) + evaluate(str.substring(i+1))
}
else if(str[i] === '-') {
return parseInt(temp) - evaluate(str.substring(i+1))
}
else if(str[i] === '*') {
return parseInt(temp) * evaluate(str.substring(i+1))
}
else if(str[i] === '/') {
return parseInt(temp) / evaluate(str.substring(i+1))
}
else {
temp += str[i]
}
}
}
else {
return parseInt(str)
}
}
console.log(evaluate('1+2+3+4+5')) // 15
console.log(evaluate('1*2*3*4*5')) // 120
console.log(evaluate('20/4')) // 5
console.log(evaluate('20-6')) // 14
黑码，
我有一个字符串“1+1”，javascript 内置函数 eval() 我可以执行 eval(“1+1”) 所以 return 值将为 2
但是如果我想在 javascript 中将这个概念实现为递归函数呢？
function evaluate(str) {
}
evaluate("1+1");
evaluate("1-1");
evaluate("1*1");
evaluate("1/1");
我试过的是
function evaluate(str) {
if (str.length === 0) {
return "";
}else{
let angka;
let symbol;
for (let i = 0; i < str.length; i++) {
if (isNaN(str[i])) {
symbol = str[i];
break;
}else{
angka = str[i];
}
}
switch (symbol) {
case "+":
return angka + evaluate(str.slice(1));
case "-":
return angka - evaluate(str.slice(1));
case "/":
return angka / evaluate(str.slice(1));
case "*":
return angka * evaluate(str.slice(1));
default:
return parseInt(str[0]) + evaluate(str.slice(1));
}
}
}
function evaluate(str) {
if (str.length === 0) {
return ""
}
let numbers = "";
let operator = "";
let lastIndex = 0;
for (let i = 0; i <= str.length; i++) {
if (!isNaN(parseInt(str[i]))) {
numbers += parseInt(str[i]);
}else{
operator = str[i];
lastIndex = i;
break;
}
}
// console.log(numbers, " " , operator , " " , lastIndex);
lastIndex = lastIndex < 1 ? 1 : lastIndex;
if (operator === "+") {
return numbers + evaluate(str.slice(lastIndex));
}
}
function evaluate(str) {
if (str.length === 0) {
return 1;
}else{
let numbers = "";
for (let i = 0; i <= str.length; i++) {
if(parseInt(str[i]) >= 0){
numbers = numbers + "+" + str[i];
}else{
let lengthNumbers = numbers.length > 1 ? numbers.length : 1;
let tempNumbers = numbers;
numbers = "";
return tempNumbers + evaluate(str.slice(lengthNumbers))
}
}
}
}
===========
已更新
我是多么笨:)，现在这是我的答案（根据下面的解决方案），谢谢大家
function evaluate(str) {
if(str.match(/[*/+-]/)){
let numbers = "";
for (let i = 0; i < str.length; i++) {
switch (str[i]) {
case "+":
return parseInt(numbers) + evaluate(str.slice(numbers.length+1))
case "*":
return parseInt(numbers) * evaluate(str.slice(numbers.length+1))
case "/":
return parseInt(numbers) / evaluate(str.slice(numbers.length+1))
case "-":
return parseInt(numbers) - evaluate(str.slice(numbers.length+1))
default:
numbers += str[i];
break;
}
}
}else{
return parseInt(str[0]);
}
}
console.log(evaluate('1+2+3+4+5')) // 15
console.log(evaluate('1*2*3*4*5')) // 120
console.log(evaluate('20/4')) // 5
console.log(evaluate('20-6')) // 14
而且没有人工作！我知道 eval 会拯救我的一天，但在这种情况下我需要解决这个问题，谢谢。
你们非常亲密。它需要更复杂一点。
请阅读代码中的注释以了解其工作原理：
function evaluate(str) {
if (str.length === 0) {
return ""
}
// Function to apply the operator from right to left
const applyOperator = (operator, left, right) => {
result = left;
switch(operator) {
case '+':
result += right;
break;
case '-':
result -= right;
break;
case '*':
result *= right;
break;
case '/':
// Avoid division by zero
if(right !== 0) {
result /= right;
}
break;
}
return result;
}
let result = 0;
let numbers = "";
let operator = null;
for (let i = 0; i < str.length; i++) {
let c = str[i]; // Isolate the character
let isLast = i === str.length - 1; // Flag to check if we're on the last character
// Ignore spaces or tabs
if (c === ' ' || c === '\t') {
continue;
}
// Check if c is a number
if (!isNaN(parseInt(c))) {
// If it's a number add it to the number builder
numbers += c;
// If it's not the last character then continue to the next character
if(!isLast) {
continue;
}
}
// Convert the numbers stack into an integer and reset the stack
let number = parseInt(numbers);
numbers = '';
// If there was no operator before,
// then just set the result with the number and store the operator for the next calculation
if(operator === null) {
result = number;
operator = c;
} else {
// Apply the previous operator the the result using the number
result = applyOperator(operator, result, number);
// Store the current operator for the next calculation
operator = c;
}
}
return result;
}
document.getElementById('results').textContent =
[
"1 + 1",
"1 - 1",
"1 * 1",
"1 / 1",
"2 + 4 + 7",
"5 - 7",
"5 * 2 + 10",
"10 - 20 + 30 * 2 / 10"
].map(exp => `${exp} = ${evaluate(exp)}`).join('\n');
<pre id="results"></pre>
编辑
我不认为我们试图在这里实现某种 compiling/interpreting 引擎，但为了测试结果，这里是一个以正确顺序执行每个算术运算的版本 *, /, -, +:
function evaluate(str) {
if (str.length === 0) {
return ""
}
// Function to apply the operator from right to left
const applyOperator = (operator, left, right) => {
result = left;
switch(operator) {
case '+':
result += right;
break;
case '-':
result -= right;
break;
case '*':
result *= right;
break;
case '/':
// Avoid division by zero
if(right !== 0) {
result /= right;
}
break;
}
return result;
}
const passApply = (exp, opApply) => {
let result = 0;
let numbers = "";
let operator = null;
let prevWasOp = false;
let sign = '';
let parsed = '';
for (let i = 0; i < exp.length; i++) {
let c = exp[i]; // Isolate the character
let isLast = i === exp.length - 1; // Flag to check if we're on the last character
// Ignore spaces or tabs
if (c === ' ' || c === '\t') {
continue;
}
// Check if c is a number
if (!isNaN(parseInt(c))) {
// If it's a number add it to the number builder
numbers += c;
prevWasOp = false;
// If it's not the last character then continue to the next character
if(!isLast) {
continue;
}
} else if(prevWasOp || i === 0) {
// Checked for signed number
if(/[\+-]/.test(c)) {
sign = c;
continue;
}
prevWasOp = false;
}
// Convert the numbers stack into an integer and reset the stack
let number = parseInt(`${sign}${numbers}`);
// Reset the sign if there was any
sign = '';
// If there was no operator before,
// then just set the result with the number and store the operator for the next calculation
if(operator === null) {
result = number;
operator = c;
if(opApply !== operator) {
parsed += `${numbers}${operator}`;
result = 0;
}
} else {
if(opApply === operator) {
// Apply the previous operator the the result using the number
result = applyOperator(operator, result, number);
// Store the current operator for the next calculation
if(c !== opApply) {
parsed += `${result}`;
if(!isLast) {
parsed += `${c}`;
}
result = 0;
}
operator = c;
} else {
if(c !== opApply) {
parsed += `${numbers}`;
if(!isLast) {
parsed += `${c}`;
}
}
operator = c;
result = number;
}
}
numbers = '';
prevWasOp = ['+', '-', '*', '/'].indexOf(c) >= 0;
}
return parsed;
}
// Exeture each operator pass
const mulPass = passApply(str, '*');
const divPass = passApply(mulPass, '/');
const subPass = passApply(divPass, '-');
const addPass = passApply(subPass, '+');
// Convert result to int and return the result
return parseInt(result);
}
document.getElementById('results').textContent =
[
"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"
].map(exp => {
const result = evaluate(exp);
return `${exp} = ${result} eval(${result === eval(exp) ? 'OK' : 'ERROR'})`;
}).join('\n');
<pre id="results"></pre>
另一种方法是将您的字符串变成一个可以作为堆栈计算的数组，然后对该堆栈进行简单的计算。例如，我们可以将 "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 interpreter!
的开头更新
题目具体问的是如何递归的，我写了一个递归的版本，总体上比上面的简单。但后来我意识到如何轻松扩展它以处理括号并尊重运算符优先级。它不再一定更简单，但它是一种有趣的方法，我们可以使用其他运算符和不同的优先级轻松扩展它：
// 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 operator precedence 图表。括号的分组在继续之前在内部重复出现，并且所有函数在剩余的表达式上重复出现。请注意，正确关联的求幂有一些额外的工作要做，包括将字符串的其余部分作为捕获组，测试它不包含任何求幂运算符；这可能更好地写成负面的前瞻性，但我不是一个正则表达式专家。另请注意，我将插入符号 (^) 用于求幂运算符；如果愿意，更改为双星号 (**) 应该很容易。
对于一个复杂的表达式，它可能是这样进行的：
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
试试这个代码
function evaluate(str) {
var reg = /[*/+-]/
if(str.match(reg)){
var temp = ''
for(let i = 0; i < str.length; i++){
if(str[i] === '+') {
return parseInt(temp) + evaluate(str.substring(i+1))
}
else if(str[i] === '-') {
return parseInt(temp) - evaluate(str.substring(i+1))
}
else if(str[i] === '*') {
return parseInt(temp) * evaluate(str.substring(i+1))
}
else if(str[i] === '/') {
return parseInt(temp) / evaluate(str.substring(i+1))
}
else {
temp += str[i]
}
}
}
else {
return parseInt(str)
}
}
console.log(evaluate('1+2+3+4+5')) // 15
console.log(evaluate('1*2*3*4*5')) // 120
console.log(evaluate('20/4')) // 5
console.log(evaluate('20-6')) // 14