js实现一个函数,对一个只包含数字,减号,加号,括号的字符串表达式求值,不能使用eval
时间: 2024-04-15 09:32:08 浏览: 17
为了实现对包含数字、减号、加号和括号的字符串表达式求值,可以使用逆波兰表达式(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` 函数。