Java栈实现真值表未输出预期结果，求修复方法

给定表达式 pq¬∨pq∧→，期望输出为 true false true false，但当前代码输出完全相反，调整优先级后甚至全为true，以下是问题分析和修复方案：

原代码 #

import java.util.*;

public class TruthTable {

public static boolean evaluateExpression(String expression, boolean p, boolean q) {
    Stack<Boolean> stack = new Stack<>();
    Stack<Character> opStack = new Stack<>();

    for (int i = 0; i < expression.length(); i++) {
        char c = expression.charAt(i);
        if (c == 'p') {
            stack.push(p);
        } else if (c == 'q') {
            stack.push(q);
        } else if (c == '¬') {
            boolean b = stack.pop();
            stack.push(!b);
        } else if (c == '∧') {
            // Check if the next character is a ¬ character.
            if (i + 1 < expression.length() && expression.charAt(i + 1) == '¬') {
                // If the next character is a ¬ character, pop the top of the stack and negate it,
                // then push the conjunction of the negated value and the value of q.
                boolean b = stack.pop();
                stack.push(!(b && q));
                // Increment the index to skip the ¬ character.
                i++;
            } else {
                // If the next character is not a ¬ character, simply push the conjunction of the
                // value of p and the value of q.
                stack.push(stack.pop() && q);
            }
        } else if (c == '∨' || c == '→' || c == '↔' || c == '⊕' || c == '⊼' || c == '⊽') {
            while (!opStack.isEmpty() && getPrecedence(c) <= getPrecedence(opStack.peek())) {
                char op = opStack.pop();
                applyOperator(op, stack);
            }
            opStack.push(c);
        }
    }

    while (!opStack.isEmpty()) {
        char op = opStack.pop();
        applyOperator(op, stack);
    }

    return stack.pop();
}

private static void applyOperator(char op, Stack<Boolean> stack) {
    boolean b1 = stack.pop();
    boolean b2 = stack.pop();
    switch (op) {
        case '∧':
            stack.push(b1 && b2);
            break;
        case '∨':
            stack.push(b1 || b2);
            break;
        case '→':
            stack.push(!b1 || b2);
            break;
        case '↔':
            stack.push(b1 == b2);
            break;
        case '⊕':
            stack.push(b1 != b2);
            break;
        case '⊼':
            stack.push((b1 && b2) || (!b1 && b2) || (b1 && !b2));
            break;
        case '⊽':
            stack.push(b1 && b2 && stack.pop());
            break;
        case '¬':
            stack.push(!b1);
            break;
    }
}

private static int getPrecedence(char op) {
    switch (op) {
        case '¬':
            return 3;
        case '∧':
            return 2;
        case '∨':
            return 1;
        case '→':
            return 0;
        case '↔':
            return 0;
        case '⊕':
            return 1;
        case '⊼':
            if (op == '∨' || op == '→' || op == '↔' || op == '⊕') {
                return 2;
            } else {
                return 3;
            }
        case '⊽':
            return 2;
        default:
            return -1;
    }
}

public static void main(String[] args) {
    String expression = "pq¬∨pq∧→";
    System.out.println("p\tq\t(" + expression + ")");
    for (boolean p : new boolean[]{true, false}) {
        for (boolean q : new boolean[]{true, false}) {
            System.out.println(p + "\t" + q + "\t" + evaluateExpression(expression, p, q));
        }
    }
}
}

核心问题分析 #

1. 错误处理表达式类型：输入的pq¬∨pq∧→是后缀表达式（逆波兰式），无需运算符栈(opStack)处理优先级，原代码错误混合了中缀表达式的解析逻辑，导致计算顺序完全混乱。
2. 运算符处理逻辑错误：
   • 对∧的特殊判断完全多余，后缀表达式中每个运算符独立生效，无需预判下一个字符。
   • applyOperator中操作数顺序颠倒：后缀表达式中，栈顶弹出的第一个是右操作数，第二个是左操作数，原代码的运算逻辑搞反了左右操作数的顺序。
   • 部分运算符实现错误：⊼（与非）、⊽（或非）的逻辑完全不符合定义，→的逻辑也因操作数顺序颠倒而错误。
3. 冗余优先级判断：后缀表达式的计算顺序由字符顺序决定，getPrecedence方法完全无用，反而干扰逻辑。

修复后的代码 #

import java.util.Stack;

public class TruthTable {

    public static boolean evaluateExpression(String expression, boolean p, boolean q) {
        Stack<Boolean> stack = new Stack<>();

        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);
            if (c == 'p') {
                stack.push(p);
            } else if (c == 'q') {
                stack.push(q);
            } else if (c == '¬') {
                // 一元运算符：弹出一个操作数取反
                boolean operand = stack.pop();
                stack.push(!operand);
            } else {
                // 二元运算符：弹出两个操作数，注意顺序（b2是左操作数，b1是右操作数）
                boolean b1 = stack.pop();
                boolean b2 = stack.pop();
                stack.push(applyOperator(c, b2, b1));
            }
        }

        return stack.pop();
    }

    private static boolean applyOperator(char op, boolean left, boolean right) {
        return switch (op) {
            case '∧' -> left && right;
            case '∨' -> left || right;
            case '→' -> !left || right; // 蕴涵：left → right 等价于 ¬left ∨ right
            case '↔' -> left == right; // 双蕴涵：等价于双向蕴涵
            case '⊕' -> left != right; // 异或
            case '⊼' -> !(left && right); // 与非：¬(left ∧ right)
            case '⊽' -> !(left || right); // 或非：¬(left ∨ right)
            default -> throw new IllegalArgumentException("未知运算符: " + op);
        };
    }

    public static void main(String[] args) {
        String expression = "pq¬∨pq∧→";
        System.out.println("p\tq\t(" + expression + ")");
        // 按p从true到false，q从true到false遍历
        for (boolean p : new boolean[]{true, false}) {
            for (boolean q : new boolean[]{true, false}) {
                System.out.println(p + "\t" + q + "\t" + evaluateExpression(expression, p, q));
            }
        }
    }
}

修复说明 #

1. 移除运算符栈：后缀表达式直接按顺序计算，遇到运算符就弹出对应操作数计算，无需优先级处理。
2. 修正操作数顺序：明确二元运算符的左、右操作数，确保运算逻辑符合数学定义。
3. 修复运算符实现：
   • ⊼（与非）修正为!(left && right)
   • ⊽（或非）修正为!(left || right)
   • →（蕴涵）修正为!left || right（符合left → right的逻辑）
4. 简化逻辑：移除冗余的特殊判断和优先级方法，代码更简洁清晰。

运行修复后的代码，输出将符合预期：

p	q	(pq¬∨pq∧→)
true	true	true
true	false	false
false	true	true
false	false	false

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