求布尔代数复杂表达式转逆波兰表示法（RPN）的实现方案

你的现有代码仅能处理双操作数加单个二元运算符的简单表达式，要支持带否定（~）、蕴含（→）的复杂表达式，标准解决方案是使用Shunting-yard算法（调度场算法），它能妥善处理运算符优先级、一元运算符与括号，完全适配你的需求。

核心实现逻辑 #

1. 明确运算符规则 #

先定义布尔运算符的优先级（从高到低）与结合性：

• ~（否定，一元）：优先级最高，右结合（如~~X等价于~(~X)）
• ^（合取）：优先级次之，左结合
• v（析取）：优先级再次之，左结合
• →（蕴含）：优先级最低，左结合（逻辑上P→Q等价于~PvQ，转后缀时直接按运算符处理即可）

2. 表达式分词（Tokenize） #

将输入的表达式字符串拆分为单个token（操作数、运算符、括号），比如~X v Y → Y会被拆分为['~', 'X', 'v', 'Y', '→', 'Y']，处理时自动忽略空格。

3. 调度场算法转后缀表达式 #

遍历每个token，按以下逻辑处理：

• 若为操作数（X/Y等变量），直接加入输出队列
• 若为运算符：
  • 对于一元运算符~，先判断其是否为一元（出现在表达式开头、运算符后或左括号后），再将栈中优先级更高的运算符弹出至输出队列，最后压入当前运算符
  • 对于二元运算符，将栈中优先级更高或相等（左结合）的运算符弹出至输出队列，再压入当前运算符
• 若为左括号，直接压入栈；若为右括号，弹出栈中运算符至输出队列，直到遇到左括号，弹出左括号但不加入输出
• 遍历结束后，将栈中剩余运算符全部弹出至输出队列

4. 后缀表达式求值 #

遍历后缀表达式，用栈处理：

• 遇到操作数，将其对应的布尔值（用户设置的1/0）压入栈
• 遇到运算符，从栈中弹出对应数量的操作数（一元弹1个，二元弹2个），计算结果后压回栈
• 最终栈顶值即为表达式结果

完整实现代码 #

// 用户设置的变量值，可直接修改
const vars = {
  X: 1,
  Y: 0
};

// 运算符配置：优先级、是否为一元、结合性
const operators = {
  '~': { precedence: 4, isUnary: true, associativity: 'right' },
  '^': { precedence: 3, isUnary: false, associativity: 'left' },
  'v': { precedence: 2, isUnary: false, associativity: 'left' },
  '→': { precedence: 1, isUnary: false, associativity: 'left' }
};

// 表达式分词函数
function tokenize(expression) {
  const tokens = [];
  let i = 0;
  const len = expression.length;
  while (i < len) {
    const char = expression[i];
    // 跳过空格
    if (char.trim() === '') {
      i++;
      continue;
    }
    // 匹配运算符或括号
    if (operators[char] || char === '(' || char === ')') {
      tokens.push(char);
      i++;
    } else {
      // 匹配单个字母变量，如需多字符变量可扩展此处逻辑
      tokens.push(char);
      i++;
    }
  }
  return tokens;
}

// 中缀表达式转后缀表达式
function infixToPostfix(tokens) {
  const output = [];
  const stack = [];
  
  for (let i = 0; i < tokens.length; i++) {
    const token = tokens[i];
    
    // 操作数直接加入输出
    if (!operators[token] && token !== '(' && token !== ')') {
      output.push(token);
      continue;
    }
    
    // 左括号压栈
    if (token === '(') {
      stack.push(token);
      continue;
    }
    
    // 右括号弹出至左括号
    if (token === ')') {
      while (stack.length > 0 && stack[stack.length - 1] !== '(') {
        output.push(stack.pop());
      }
      stack.pop(); // 弹出左括号，不加入输出
      continue;
    }
    
    // 处理运算符
    const currentOp = operators[token];
    // 判断~是否为一元运算符
    const isUnary = currentOp.isUnary && (
      i === 0 || 
      operators[tokens[i-1]] || 
      tokens[i-1] === '('
    );
    
    while (stack.length > 0) {
      const topToken = stack[stack.length - 1];
      if (topToken === '(') break;
      
      const topOp = operators[topToken];
      // 比较优先级，决定是否弹出栈顶运算符
      const shouldPop = isUnary 
        ? (topOp.precedence > currentOp.precedence)
        : (currentOp.associativity === 'left' && topOp.precedence >= currentOp.precedence) ||
          (currentOp.associativity === 'right' && topOp.precedence > currentOp.precedence);
      
      if (shouldPop) {
        output.push(stack.pop());
      } else {
        break;
      }
    }
    stack.push(token);
  }
  
  // 弹出栈中剩余运算符
  while (stack.length > 0) {
    output.push(stack.pop());
  }
  
  return output.join('');
}

// 计算后缀表达式结果
function evaluatePostfix(postfix) {
  const stack = [];
  for (const char of postfix) {
    if (!operators[char]) {
      // 压入变量对应的值
      stack.push(vars[char]);
    } else {
      const op = operators[char];
      if (op.isUnary) {
        // 一元运算符取反
        const val = stack.pop();
        stack.push(val === 0 ? 1 : 0);
      } else {
        // 二元运算符：注意弹出顺序，先弹的是右操作数
        const right = stack.pop();
        const left = stack.pop();
        let result;
        switch (char) {
          case '^':
            result = left & right; // 合取：同1为1
            break;
          case 'v':
            result = left | right; // 析取：有1为1
            break;
          case '→':
            result = left === 1 && right === 0 ? 0 : 1; // 蕴含：仅1→0为0，其余为1
            break;
        }
        stack.push(result);
      }
    }
  }
  return stack.pop();
}

// 测试示例
const inputExpr = "~X v Y → Y";
const tokens = tokenize(inputExpr);
const postfix = infixToPostfix(tokens);
const result = evaluatePostfix(postfix);

console.log(`原表达式：${inputExpr}`);
console.log(`后缀形式：${postfix}`);
console.log(`计算结果：${result}`);

代码说明 #

• 变量vars用于存储用户设置的X/Y等值，可直接修改
• 支持带括号的复杂表达式，比如~(X v Y) ^ Z
• 蕴含运算符→的计算逻辑严格遵循布尔代数规则，也可替换为转成~PvQ后再计算
• 分词函数默认支持单个字母变量，如需多字符变量可扩展分词逻辑

内容的提问来源于stack exchange，提问作者user526218