自定义运算符优先级计算

Posted by CodingWithAlice on March 25, 2025

自定义运算符优先级计算 #>$

问题:给定一个由数字、#$ 组成的字符串,其中

  1. # 的优先级高于 $
  2. 运算规则:
    • a#b:结果为 a * 4 + b * 3 + 2
    • a$b:结果为 a * 2 + b + 3
  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