Java 高级程序设计：实验七 线性表、栈、队列和优先队列的使用

代码地址：Github

实验目的和要求

1. 初步熟悉线性表、栈、队列和优先队列的基本概念及用途，熟悉应用开发环境：Eclipse的使用；
2. 掌握利用线性表、栈、队列和优先队列设计应用。

实验内容

1. 按字母的升序显示单词，编写一个程序，从字符串中读取单词，并按照字母的升序显示所有的单词，不能重复。字符串用键盘录入。如输入：“Write a program to evaluate postfix expressions. Pass the expression as a commandline argument in one string.”
2. 通常将运算符写在运算量之间，例如a+b，这种表示法称为中缀表示法。后缀表示法又称逆波兰表示法，它是波兰逻辑学家卢卡西维奇发明的一种表示表达式的方法。这种表示法把运算量写在前面，把运算符写在后面（后缀），例如a+b写作a b+，a+b*c写作a b c*+，（a+b）*c写作a b+c*等等。编写一个程序计算后缀表达式。表达式用命令行录入。计算输出结果。
3. 中缀表示法转化为后缀表示法。中缀表示法表达式用命令行录入。计算输出结果为后缀表示法。

实验结果

Answer01

public class CountWords {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String sentences = scanner.nextLine();
        HashMap<String, Integer> wordsHashMap = new HashMap<>();

        for (String s : sentences.split("[,.; !]")) {
            int v = 1;
            if (wordsHashMap.containsKey(s)) {
                v += wordsHashMap.get(s);
            }
            wordsHashMap.put(s, v);
        }

        wordsHashMap.remove(" ");
        wordsHashMap.remove("");

        System.out.println(wordsHashMap);
    }
}

Answer02

public class SuffixCalculator {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String suffixExpression = scanner.nextLine();
        List<String> list = getListString(suffixExpression);
        System.out.println("rpnList=" + list);
        System.out.println("计算的结果是=" + calculate(list));
    }

    public static List<String> getListString(String suffixExpression) {
        //将 suffixExpression 分割
        String[] split = suffixExpression.split(" ");
        return new ArrayList<>(Arrays.asList(split));
    }

    public static int calculate(List<String> ls) {
        Stack<String> stack = new Stack<>();
        for (String item : ls) {
            if (item.matches("\\d+")) {
                // 匹配的是多位数, 入栈
                stack.push(item);
            } else {
                // pop出两个数，并运算， 再入栈
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int res = switch (item) {
                    case "+" -> num1 + num2;
                    case "-" -> num1 - num2;
                    case "*" -> num1 * num2;
                    case "/" -> num1 / num2;
                    default -> throw new RuntimeException("运算符有误");
                };
                //把res 入栈
                stack.push("" + res);
            }
        }
        return Integer.parseInt(stack.pop());
    }
}

Answer03

public class InfixExpressionToSuffixExpression {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<String> list = getListString(scanner.nextLine());
        for (String str : infixExpToSuffixExp(list)) {
            System.out.print(str + " ");
        }
    }

    public static List<String> infixExpToSuffixExp(List<String> infixExp) {
        Stack<String> operatorStack = new Stack<>();
        List<String> resList = new ArrayList<>();
        for (String item : infixExp) {
            //如果是一个数，加入resList
            if (item.matches("^(\\-|\\+)?\\d+(\\.\\d+)?$")) {
                resList.add(item);
            } else if (item.equals("(")) {
                operatorStack.push(item);
            } else if (item.equals(")")) {
                //如果是又括号，则依次弹出operatorStack中的运算符，并压入resList，直到遇到左括号为止
                while (!operatorStack.peek().equals("(")) {
                    resList.add(operatorStack.pop());
                }
                operatorStack.pop(); // 消除左括号
            } else {
                //当item的优先级小于等于栈顶的优先级时
                while (operatorStack.size() != 0 &&
                        priority(item.charAt(0)) <= priority(operatorStack.peek().charAt(0))) {
                    resList.add(operatorStack.pop());
                }
                //还要将item压入栈
                operatorStack.push(item);
            }
        }
        //将operatorStack中剩余的运算符依次加入resList中
        while (operatorStack.size() != 0) {
            resList.add(operatorStack.pop());
        }
        return resList;
    }

    public static int priority(int operator) {
        if (operator == '*' || operator == '/') {
            return 1;
        }
        if (operator == '+' || operator == '-') {
            return 0;
        }
        return -1;
    }


    public static List<String> getListString(String infixExpression) {
        String[] split = infixExpression.split(" ");
        List<String> list = new ArrayList<>();
        Collections.addAll(list, split);
        return list;
    }
}