自定义运算符优先级计算 #>$
问题:给定一个由数字、#
和 $
组成的字符串,其中
#
的优先级高于$
- 运算规则:
a#b
:结果为a * 4 + b * 3 + 2
a$b
:结果为a * 2 + b + 3
- 最终输出整个表达式的计算结果
1、split + reduce 算法
function number(input) {
if (!input.includes("#") && !input.includes("$")) { // 如果没有运算符,直接返回0
return 0;
}
let lowerList = input.split("$"); // 第一步:按 $ 分割,先处理高优先级
lowerList = lowerList.map((it) => {
if (it.includes("#")) { // 第二步:对每个部分检查是否有 #(高优先级)
const higher = it.split("#");
if (higher.length === 2) {
return +higher[0] * 4 + +higher[1] * 3 + 2; // 形如 a#b
} else { // 形如 a#b#c...
return higher.reduce((pre, cur) => 4 * +pre + +cur * 3 + 2);
}
}
return it; // 无 # 则直接返回
});
return lowerList.reduce((pre, cur) => +pre * 2 + +cur + 3); // 第三步:按 $ 的规则合并
}
2、更优的写法 - 双栈法
利用 数字栈 和 运算符栈 + 高优先级立即计算
function calculateExpression(s) {
const numStack = [];
const opStack = [];
let i = 0;
while (i < s.length) {
if (s[i] === ' ') {
i++;
continue;
}
if (/\d/.test(s[i])) { // 提取完整数字
let num = 0;
while (i < s.length && /\d/.test(s[i])) {
num = num * 10 + parseInt(s[i++]);
}
numStack.push(num);
} else if (s[i] === '#' || s[i] === '$') { // 处理运算符优先级
while (opStack.length
&& getPriority(opStack[opStack.length - 1]) >= getPriority(s[i])) {
compute(numStack, opStack);
}
opStack.push(s[i++]);
}
}
while (opStack.length) {
compute(numStack, opStack);
}
return numStack.pop();
}
function getPriority(op) {
return op === '#' ? 2 : 1; // #优先级高于$
}
function compute(numStack, opStack) {
const b = numStack.pop();
const a = numStack.pop();
const op = opStack.pop();
if (op === '#') {
numStack.push(a * 4 + b * 3 + 2);
} else {
numStack.push(a * 2 + b + 3);
}
}
// 测试
console.log(calculateExpression('7#6$5#12')); // 输出 157