Discuss / Java / 练习1
Back

练习1

Topic source

忒修斯之船

#1 Created at ... [Delete] [Delete and Lock User] 
public abstract class StackUtil {
    private static final int HEX_BASE = 16;
    private static final Map<Long, Character> HEX_VALUE_MAP = Map.of(10L, 'A', 11L, 'B', 12L, 'C', 13L, 'D', 14L, 'E', 15L, 'F');

    /**
     * 将一个 10 进制整数转为 16进制形式字符串
     *
     * @param num 10 进制整数
     * @return 数字的 16 进制形式字符串
     */
    public static String toHex(int num) {
        StringBuilder sb = new StringBuilder("0x");
        Deque<Long> stack = new LinkedList<>();

        if (num == 0) {
            return "0x0";
        }
        if (num > 0) {
            hexStackPush(stack, num);
        } else {
            hexStackPush(stack, Integer.toUnsignedLong(num));
        }
        for (Long foo : stack) {
            Character ch = HEX_VALUE_MAP.get(foo);
            // 注意 int 和 char 最终走的是不同的重载方法
            if (ch == null) {
                sb.append(foo);
            } else {
                sb.append(ch);
            }
        }
        return sb.toString();
    }

    /**
     * 16 进制入栈方法
     *
     * @param stack    栈
     * @param quotient 商
     */
    private static void hexStackPush(Deque<Long> stack, long quotient) {
        stack.push((quotient % HEX_BASE));
        quotient = quotient / HEX_BASE;

        if (quotient > HEX_BASE) {
            hexStackPush(stack, quotient);
        } else {
            stack.push(quotient);
        }
    }
}

忒修斯之船

#2 Created at ... [Delete] [Delete and Lock User]

改一下，虽然之前结果没错，但读取时没用栈的方法

public abstract class StackUtil {
    private static final int HEX_BASE = 16;
    private static final Map<Integer, Character> HEX_VALUE_MAP = Map.of(10, 'A', 11, 'B', 12, 'C', 13, 'D', 14, 'E', 15, 'F');

    /**
     * 将一个 10 进制整数转为 16进制形式字符串
     *
     * @param num 10 进制整数
     * @return 数字的 16 进制形式字符串
     */
    public static String toHex(int num) {
        if (num == 0) {
            return "0x0";
        }
        StringBuilder sb = new StringBuilder("0x");
        Deque<Integer> stack = new LinkedList<>();
        if (num > 0) {
            hexStackPush(stack, num);
        } else {
            hexStackPush(stack, Integer.toUnsignedLong(num));
        }
        // 出栈
        while (!stack.isEmpty()) {
            int pop = stack.pop();
            sb.append(Objects.requireNonNullElse(HEX_VALUE_MAP.get(pop), pop));
        }
        return sb.toString();
    }

    /**
     * 16 进制入栈方法
     *
     * @param stack    栈
     * @param quotient 商
     */
    private static void hexStackPush(Deque<Integer> stack, long quotient) {
        stack.push((int) (quotient % HEX_BASE));
        quotient = quotient / HEX_BASE;

        if (quotient > HEX_BASE) {
            hexStackPush(stack, quotient);
        } else {
            stack.push((int) quotient);
        }
    }}

忒修斯之船

#3 Created at ... [Delete] [Delete and Lock User]

再次改进

public abstract class StackUtil {
    private static final int HEX_BASE = 16;
    private static final Map<Integer, Character> HEX_VALUE_MAP = Map.of(10, 'A', 11, 'B', 12, 'C', 13, 'D', 14, 'E', 15, 'F');

    /**
     * 将一个 10 进制整数转为 16进制形式字符串
     *
     * @param num 10 进制整数
     * @return 数字的 16 进制形式字符串
     */
    public static String toHex(int num) {
        if (num == 0) {
            return "0x0";
        }

        // 入栈
        Deque<Integer> stack = new LinkedList<>();
        // 处理负数
        long quotient = (num > 0) ? num : Integer.toUnsignedLong(num);
        while (quotient > HEX_BASE) {
            stack.push((int) (quotient % HEX_BASE));
            quotient /= HEX_BASE;
        }
        stack.push((int) quotient);

        // 出栈
        StringBuilder sb = new StringBuilder("0x");
        while (!stack.isEmpty()) {
            int pop = stack.pop();
            sb.append(Objects.requireNonNullElse(HEX_VALUE_MAP.get(pop), pop));
        }
        return sb.toString();
    }
}

忒修斯之船

#4 Created at ... [Delete] [Delete and Lock User]

进阶2

public record SuffixExpression(List<String> exp) {
    /**
     * 中缀表达式转后缀表达式
     * <p>
     * 暂只考虑加减乘除和括号
     *
     * @param exp 中缀表达式
     * @return 后缀表达式
     */
    @SuppressWarnings({"ConstantConditions", "AlibabaUndefineMagicConstant"})
    public static SuffixExpression compile(String exp) {
        // 符号暂存区
        Deque<Character> symbols = new LinkedList<>();
        // 数字匹配集
        String numberCollection = "0123456789";
        // 用于接收和拼接结果
        List<String> resultExp = new ArrayList<>();

        // 移除空白字符
        exp = exp.replaceAll("\\s+", "");
        for (int foo = 0; foo < exp.length(); foo++) {
            char ch = exp.charAt(foo);

            if ('(' == ch) {
                // 右括号直接入栈
                symbols.push(ch);
            } else if (')' == ch) {
                // 左括号将匹配到的符号弹出
                // 表达式正确的情况下栈内一定有元素
                while ('(' != (ch = symbols.poll())) {
                    resultExp.add(String.valueOf(ch));
                }
            } else if ('+' == ch || '-' == ch) {
                // 将同级或更高级的符号弹出并写入结果
                //将自身入栈
                if (!symbols.isEmpty()) {
                    char peek = symbols.peek();
                    if ('+' == peek || '-' == peek || '*' == peek || '/' == peek) {
                        resultExp.add(String.valueOf(symbols.pop()));
                    }
                }
                symbols.push(ch);
            } else if ('*' == ch || '/' == ch) {
                // 将同级或低级的符号弹出并写入结果
                //将自身入栈
                if (!symbols.isEmpty()) {
                    char peek = symbols.peek();
                    if ('*' == peek || '/' == peek) {
                        resultExp.add(String.valueOf(symbols.pop()));
                    }
                }
                symbols.push(ch);
            } else {
                // 其他情况（数字或变量）
                if (numberCollection.indexOf(ch) != -1) {
                    // 匹配数字
                    int baz = foo + 1;
                    while (numberCollection.indexOf(exp.charAt(baz)) != -1) {
                        baz++;
                    }
                    resultExp.add(exp.substring(foo, baz));
                    foo = baz - 1;
                } else {
                    // 写出字母
                    resultExp.add(String.valueOf(ch));
                }
            }
        }
        // 将剩余的符号拼到结果中
        while (!symbols.isEmpty()) {
            resultExp.add(String.valueOf(symbols.pop()));
        }
        return new SuffixExpression(resultExp);
    }

    /**
     * 获取后缀表达式字符串
     *
     * @return 后缀表达式字符串
     */
    public String getExpStr() {
        StringJoiner sj = new StringJoiner(" ");
        for (String foo : exp) {
            sj.add(foo);
        }
        return sj.toString();
    }

    /**
     * 运行获取结果
     *
     * @param env 变量值
     * @return 运算结果
     */
    public int execute(Map<String, Integer> env) {
        // 符号暂存区
        Deque<Integer> numbers = new LinkedList<>();
        for (String elm : exp) {
            switch (elm) {
                case "+" -> {
                    Integer nb = numbers.pop();
                    Integer na = numbers.pop();
                    numbers.push(na + nb);
                }
                case "-" -> {
                    Integer nb = numbers.pop();
                    Integer na = numbers.pop();
                    numbers.push(na - nb);
                }
                case "*" -> {
                    Integer nb = numbers.pop();
                    Integer na = numbers.pop();
                    numbers.push(na * nb);
                }
                case "/" -> {
                    Integer nb = numbers.pop();
                    Integer na = numbers.pop();
                    numbers.push(na / nb);
                }
                default -> numbers.push((env != null && env.get(elm) != null) ? env.get(elm) : Integer.valueOf(elm));
            }
        }
        return numbers.pop();
    }
}

忒修斯之船

#5 Created at ... [Delete] [Delete and Lock User]

进阶2，改 BUG
之前的程序符号判断的优先级有问题，单针对这个表达式可以得出结果，但改其他式子不太对

public record SuffixExpression(List<String> exp) {
    /**
     * 中缀表达式转后缀表达式
     * <p>
     * 暂只考虑加减乘除和括号
     *
     * @param exp 中缀表达式
     * @return 后缀表达式
     */
    public static SuffixExpression compile(String exp) {
        // 符号暂存区
        Deque<Character> symbols = new LinkedList<>();
        // 数字匹配集
        String numberCollection = "0123456789";
        // 用于接收和拼接结果
        List<String> resultExp = new ArrayList<>();

        // 移除空白字符
        exp = exp.replaceAll("\\s+", "");
        for (int foo = 0; foo < exp.length(); foo++) {
            char ch = exp.charAt(foo);

            if ('(' == ch) {
                // 右括号直接入栈
                symbols.push(ch);
            } else if (')' == ch) {
                // 左括号将匹配到的符号弹出
                // 表达式正确的情况下栈内一定有元素
                while ('(' != (ch = symbols.poll())) {
                    resultExp.add(String.valueOf(ch));
                }
            } else if ('+' == ch || '-' == ch) {
                // 将同级或更高级的符号弹出并写入结果
                //将自身入栈
                if (!symbols.isEmpty()) {
                    char peek = symbols.peek();
                    while ('+' == peek || '-' == peek || '*' == peek || '/' == peek) {
                        resultExp.add(String.valueOf(symbols.pop()));
                        if (symbols.isEmpty()) {
                            break;
                        }
                        peek = symbols.peek();
                    }
                }
                symbols.push(ch);
            } else if ('*' == ch || '/' == ch) {
                // 将同级或低级的符号弹出并写入结果
                // 将自身入栈
                if (!symbols.isEmpty()) {
                    char peek = symbols.peek();
                    while ('*' == peek || '/' == peek) {
                        resultExp.add(String.valueOf(symbols.pop()));
                        if (symbols.isEmpty()) {
                            break;
                        }
                        peek = symbols.peek();
                    }
                }
                symbols.push(ch);
            } else {
                // 其他情况（数字或变量）
                if (numberCollection.indexOf(ch) != -1) {
                    // 匹配数字
                    int baz = foo + 1;
                    while (baz < exp.length() && numberCollection.indexOf(exp.charAt(baz)) != -1) {
                        baz++;
                    }
                    resultExp.add(exp.substring(foo, baz));
                    foo = baz - 1;
                } else {
                    // 写出字母
                    resultExp.add(String.valueOf(ch));
                }
            }
        }
        // 将剩余的符号拼到结果中
        while (!symbols.isEmpty()) {
            resultExp.add(String.valueOf(symbols.pop()));
        }
        return new SuffixExpression(resultExp);
    }

    /**
     * 获取后缀表达式字符串
     *
     * @return 后缀表达式字符串
     */
    public String getExpStr() {
        StringJoiner sj = new StringJoiner(" ");
        for (String foo : exp) {
            sj.add(foo);
        }
        return sj.toString();
    }

    /**
     * 运行获取结果
     *
     * @param env 变量值
     * @return 运算结果
     */
    public int execute(Map<String, Integer> env) {
        // 符号暂存区
        Deque<Integer> numbers = new LinkedList<>();
        for (String elm : exp) {
            switch (elm) {
                case "+" -> numbers.push(numbers.pop() + numbers.pop());
                case "-" -> {
                    Integer nb = numbers.pop();
                    Integer na = numbers.pop();
                    numbers.push(na - nb);
                }
                case "*" -> numbers.push(numbers.pop() * numbers.pop());
                case "/" -> {
                    Integer nb = numbers.pop();
                    Integer na = numbers.pop();
                    numbers.push(na / nb);
                }
                default -> numbers.push((env != null && env.get(elm) != null) ? env.get(elm) : Integer.valueOf(elm));
            }
        }
        return numbers.pop();
    }
}
  • 1

Reply