给定 n 个数,不能改变顺序,可以在中间添加加号、减号或乘号,求有多少种算式可以算出 24
时间: 2023-06-11 10:06:14 浏览: 96
这是一个经典的算法问题,可以使用回溯算法来解决。
具体思路如下:
1. 首先,将给定的 n 个数放到一个数组中。
2. 然后,从数组中选出两个数进行运算,得到一个新的数,将这个新的数放回数组中。
3. 重复步骤 2,直到数组中只剩下一个数。
4. 判断这个数是否等于 24,如果是,则说明这个算式可以算出 24。
5. 如果步骤 2 中选出的两个数为 a 和 b,那么有三种运算方法:a+b、a-b、a*b,因此需要进行三次递归,分别计算这三种情况。
6. 在递归过程中,需要注意两点:
(1)不能改变数组中数的顺序。
(2)除了第一个数外,其他数选出来的顺序不同,但是结果应该是相同的,因此可以使用一个变量记录上一次递归选出来的数,避免重复计算。
实现代码如下:
相关问题
js实现一个函数,对一个只包含数字,减号加号和括号的字符串表达式求值,不能使用eval
可以使用栈来实现对表达式求值,具体步骤如下:
1. 创建两个栈,一个用于存储操作数 `operandStack`,一个用于存储运算符 `operatorStack`。
2. 遍历字符串表达式,逐个字符进行处理。
3. 如果遇到数字字符,继续往后遍历,将连续的数字字符组成完整操作数,并将其转换为数字,然后将操作数压入操作数栈 `operandStack`。
4. 如果遇到运算符字符,判断当前运算符与运算符栈顶元素的优先级。如果当前运算符优先级较高或与栈顶元素相等并且栈顶元素不是左括号,则将当前运算符压入运算符栈 `operatorStack`。
5. 如果遇到左括号字符,则直接将其压入运算符栈 `operatorStack`。
6. 如果遇到右括号字符,则从运算符栈 `operatorStack` 弹出运算符进行计算,直到遇到左括号为止。每次弹出运算符时,同时从操作数栈 `operandStack` 弹出两个操作数,进行计算并将结果压入操作数栈 `operandStack`。
7. 遍历完整个表达式后,如果运算符栈 `operatorStack` 不为空,则依次弹出运算符进行计算,同时从操作数栈 `operandStack` 弹出两个操作数,将结果压入操作数栈 `operandStack`。
8. 最后,操作数栈 `operandStack` 中的唯一元素即为表达式的求值结果。
下面是实现上述逻辑的 JavaScript 函数:
```javascript
function evaluateExpression(expression) {
const operandStack = []; // 操作数栈
const operatorStack = []; // 运算符栈
// 定义运算符优先级
const precedence = {
'+': 1,
'-': 1,
'(': 0
};
// 计算结果函数
function calculate() {
const operator = operatorStack.pop();
const operand2 = operandStack.pop();
const operand1 = operandStack.pop();
switch (operator) {
case '+':
operandStack.push(operand1 + operand2);
break;
case '-':
operandStack.push(operand1 - operand2);
break;
}
}
// 遍历表达式
for (let i = 0; i < expression.length; i++) {
const char = expression[i];
if (/\d/.test(char)) { // 数字字符
let numStr = char;
// 继续往后遍历,将连续的数字字符组成完整的操作数
while (/\d/.test(expression[i + 1])) {
numStr += expression[i + 1];
i++;
}
operandStack.push(Number(numStr));
} else if (char === '+' || char === '-') { // 运算符字符
while (
operatorStack.length > 0 &&
precedence[char] <= precedence[operatorStack[operatorStack.length - 1]]
) {
calculate();
}
operatorStack.push(char);
} else if (char === '(') { // 左括号字符
operatorStack.push(char);
} else if (char === ')') { // 右括号字符
while (operatorStack[operatorStack.length - 1] !== '(') {
calculate();
}
operatorStack.pop(); // 弹出左括号
}
}
while (operatorStack.length > 0) { // 处理剩余运算符
calculate();
}
return operandStack[0];
}
```
使用示例:
```javascript
console.log(evaluateExpression("2+3*(4-1)")); // 输出 11
console.log(evaluateExpression("5+(6-2)*8")); // 输出 37
console.log(evaluateExpression("(1+2)*(3-4)+5")); // 输出 2
```
注意:以上实现仅适用于只包含数字、减号、加号和括号的简单表达式,对于更复杂的表达式或其他运算符,需要进行相应的扩展和修改。
js实现一个函数,对一个只包含数字,减号,加号,括号的字符串表达式求值,不能使用eval
为了实现对包含数字、减号、加号和括号的字符串表达式求值,可以使用逆波兰表达式(Reverse Polish Notation, RPN)算法来解决。具体步骤如下:
1. 创建两个栈,一个用于存储操作数 `operandStack`,一个用于存储运算符 `operatorStack`。
2. 将字符串表达式转换为逆波兰表达式。遍历字符串表达式,逐个字符进行处理。
3. 如果遇到数字字符,继续往后遍历,将连续的数字字符组成完整操作数,并将其添加到逆波兰表达式的末尾。
4. 如果遇到运算符字符,判断当前运算符与运算符栈顶元素的优先级。如果当前运算符优先级较高或与栈顶元素相等并且栈顶元素不是左括号,则将当前运算符压入运算符栈 `operatorStack`。
5. 如果遇到左括号字符,则直接将其压入运算符栈 `operatorStack`。
6. 如果遇到右括号字符,则从运算符栈 `operatorStack` 弹出运算符并添加到逆波兰表达式的末尾,直到遇到左括号为止。
7. 遍历完整个表达式后,如果运算符栈 `operatorStack` 不为空,则依次弹出运算符并添加到逆波兰表达式的末尾。
8. 通过逆波兰表达式计算结果。遍历逆波兰表达式,逐个元素进行处理。
9. 如果遇到操作数,则将其压入操作数栈 `operandStack`。
10. 如果遇到运算符,则从操作数栈 `operandStack` 弹出两个操作数进行计算,并将结果压入操作数栈 `operandStack`。
11. 最后,操作数栈 `operandStack` 中的唯一元素即为表达式的求值结果。
下面是实现上述逻辑的 JavaScript 函数:
```javascript
function evaluateExpression(expression) {
// 运算符优先级映射
const precedence = {
'+': 1,
'-': 1,
'(': 0
};
// 将中缀表达式转换为逆波兰表达式
function convertToRPN(infixExpression) {
const rpn = []; // 逆波兰表达式
const operatorStack = []; // 运算符栈
for (let i = 0; i < infixExpression.length; i++) {
const char = infixExpression[i];
if (/\d/.test(char)) { // 数字字符
let numStr = char;
// 继续往后遍历,将连续的数字字符组成完整的操作数
while (/\d/.test(infixExpression[i + 1])) {
numStr += infixExpression[i + 1];
i++;
}
rpn.push(Number(numStr));
} else if (char === '+' || char === '-') { // 运算符字符
while (
operatorStack.length > 0 &&
precedence[char] <= precedence[operatorStack[operatorStack.length - 1]]
) {
rpn.push(operatorStack.pop());
}
operatorStack.push(char);
} else if (char === '(') { // 左括号字符
operatorStack.push(char);
} else if (char === ')') { // 右括号字符
while (operatorStack[operatorStack.length - 1] !== '(') {
rpn.push(operatorStack.pop());
}
operatorStack.pop(); // 弹出左括号
}
}
while (operatorStack.length > 0) { // 处理剩余运算符
rpn.push(operatorStack.pop());
}
return rpn;
}
// 使用逆波兰表达式计算结果
function calculateRPN(rpnExpression) {
const operandStack = []; // 操作数栈
for (let i = 0; i < rpnExpression.length; i++) {
const token = rpnExpression[i];
if (typeof token === 'number') { // 操作数
operandStack.push(token);
} else { // 运算符
const operand2 = operandStack.pop();
const operand1 = operandStack.pop();
switch (token) {
case '+':
operandStack.push(operand1 + operand2);
break;
case '-':
operandStack.push(operand1 - operand2);
break;
}
}
}
return operandStack[0];
}
const rpnExpression = convertToRPN(expression);
return calculateRPN(rpnExpression);
}
```
使用示例:
```javascript
console.log(evaluateExpression("2+3*(4-1)")); // 输出 11
console.log(evaluateExpression("5+(6-2)*8")); // 输出 37
console.log(evaluateExpression("(1+2)*(3-4)+5")); // 输出 2
```
这样,我们就可以通过将字符串表达式转换为逆波兰表达式,并使用逆波兰表达式来计算结果,实现对包含数字、减号、加号和括号的字符串表达式求值,而不使用 `eval` 函数。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)