用Java实现算符优先法

算符优先法是一种用于构建语法分析器的技术，它可以根据运算符的优先级和结合性来确定表达式的语法结构。下面是用Java实现算符优先法的示例代码：

import java.util.*;

public class OperatorPrecedenceParser {

    private static final String[] OPERATORS = {"+", "-", "*", "/", "(", ")"};

    private static final int[][] PRECEDENCE = {
            {1, 1, -1, -1, -1, 1},
            {1, 1, -1, -1, -1, 1},
            {1, 1, 1, 1, -1, 1},
            {1, 1, 1, 1, -1, 1},
            {-1, -1, -1, -1, -1, 0},
            {1, 1, 1, 1, 0, 1}
    };

    private static final Map<String, Integer> OPERATOR_MAP = new HashMap<>();

    static {
        for (int i = 0; i < OPERATORS.length; i++) {
            OPERATOR_MAP.put(OPERATORS[i], i);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter an infix expression: ");
        String infix = scanner.nextLine();
        List<String> tokens = tokenize(infix);
        List<String> postfix = toPostfix(tokens);
        System.out.println("Postfix expression: " + postfix);
        int result = evaluatePostfix(postfix);
        System.out.println("Result: " + result);
    }

    private static List<String> tokenize(String infix) {
        List<String> tokens = new ArrayList<>();
        int i = 0;
        while (i < infix.length()) {
            if (Character.isDigit(infix.charAt(i))) {
                StringBuilder sb = new StringBuilder();
                while (i < infix.length() && Character.isDigit(infix.charAt(i))) {
                    sb.append(infix.charAt(i++));
                }
                tokens.add(sb.toString());
            } else if (isOperator(String.valueOf(infix.charAt(i)))) {
                tokens.add(String.valueOf(infix.charAt(i++)));
            } else {
                i++;
            }
        }
        return tokens;
    }

    private static List<String> toPostfix(List<String> tokens) {
        List<String> postfix = new ArrayList<>();
        Stack<String> stack = new Stack<>();
        for (String token : tokens) {
            if (isOperator(token)) {
                while (!stack.isEmpty() && isOperator(stack.peek())) {
                    String top = stack.peek();
                    if (PRECEDENCE[OPERATOR_MAP.get(top)][OPERATOR_MAP.get(token)] >= 0) {
                        break;
                    }
                    postfix.add(stack.pop());
                }
                stack.push(token);
            } else if (token.equals("(")) {
                stack.push(token);
            } else if (token.equals(")")) {
                while (!stack.isEmpty() && !stack.peek().equals("(")) {
                    postfix.add(stack.pop());
                }
                stack.pop();
            } else {
                postfix.add(token);
            }
        }
        while (!stack.isEmpty()) {
            postfix.add(stack.pop());
        }
        return postfix;
    }

    private static int evaluatePostfix(List<String> postfix) {
        Stack<Integer> stack = new Stack<>();
        for (String token : postfix) {
            if (isOperator(token)) {
                int b = stack.pop();
                int a = stack.pop();
                switch (token) {
                    case "+":
                        stack.push(a + b);
                        break;
                    case "-":
                        stack.push(a - b);
                        break;
                    case "*":
                        stack.push(a * b);
                        break;
                    case "/":
                        stack.push(a / b);
                        break;
                }
            } else {
                stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }

    private static boolean isOperator(String token) {
        return OPERATOR_MAP.containsKey(token);
    }

}

在上述代码中，`OPERATORS`数组存储了运算符，`PRECEDENCE`数组存储了运算符之间的优先级和结合性，`OPERATOR_MAP`映射运算符到其在`OPERATORS`数组中的索引。`tokenize`方法将中缀表达式转换为一个个的标记（数字或运算符），`toPostfix`方法将中缀表达式转换为后缀表达式，`evaluatePostfix`方法计算后缀表达式的值。在`toPostfix`方法中，使用栈来保存运算符，遇到数字直接输出，遇到左括号直接入栈，遇到右括号则将栈顶运算符弹出直到遇到左括号为止，最后将栈中剩余的运算符全部弹出输出。在弹出运算符之前，需要比较栈顶运算符和当前运算符的优先级和结合性，如果栈顶运算符的优先级大于或等于当前运算符，则可以弹出，否则需要继续等待。

在`evaluatePostfix`方法中，使用栈来保存数字和中间结果，遇到数字直接入栈，遇到运算符则从栈中弹出两个数字进行运算，将结果入栈。最后栈中剩余的数字就是表达式的结果。