[数据结构与算法]数据结构--前缀、中缀和后缀表达式

一、定义

（1）前缀表达式（波兰表达式）：从右到左扫描表达式，遇到数字时压入数字栈，遇到运算符时，弹出两个栈顶的两个数，进行计算，并将结果入栈；重复止到表达式最左端。
（2）中缀表达式：就是常见的运算表达式，和人的思考方式是一致的，但是与计算机来说不好操作。
（3）后缀表达式（逆波兰表达式）：与前缀表达式相似，只是运算符位于操作数之后。

二、具体实现

1.后缀表达式

代码如下（示例）：

// 设置一个列表接收表达式
    public static List<String> getList(String expression){
        String[] str = expression.split(" ");
        List<String> list = new ArrayList<>();
        for (int i = 0; i < str.length; i++) {
            list.add(str[i]);
        }
        return list;
    }

    // 表达式的计算
    public static int calculate(List<String> list){
        Stack<Integer> stack = new Stack<>();
        for (String s : list) {
            if(s.matches("\\d+")){
                stack.push(Integer.parseInt(s));
            }else{
                if(s.equals("+")){
                    int num1 = stack.pop();
                    int num2 = stack.pop();
                    int res = num1 + num2;
                    stack.push(res);
                }else if(s.equals("-")){
                    int num1 = stack.pop();
                    int num2 = stack.pop();
                    int res = num2 - num1;
                    stack.push(res);
                }else if(s.equals("*")){
                    int num1 = stack.pop();
                    int num2 = stack.pop();
                    int res = num1 * num2;
                    stack.push(res);
                }else if(s.equals("/")){
                    int num1 = stack.pop();
                    int num2 = stack.pop();
                    int res = num2 / num1;
                    stack.push(res);
                }else {
                    System.out.println("数据有问题");
                    break;
                }
            }
        }
        return stack.pop();
    }

2.中缀转后缀表达式

代码如下（示例）：

// 中缀转后缀表达式
    public static List<String> getPolandList(List<String> list){
        Stack<String> stack1 = new Stack<>();
        Stack<String> stack2 = new Stack<>();
        for (String s : list) {
            if(s.matches("\\d+")){
                stack1.push(s);
            }else if(s.equals("(")) {
                stack2.push(s);
            }else if(s.equals(")")) {
                while (!stack2.peek().equals("(")) {
                    stack1.push(stack2.pop());
                }
                stack2.pop();
            }else{
                while(isOpr(s)){
                    if(stack2.isEmpty() || stack2.peek().equals("(")){
                        stack2.push(s);
                        break;
                    }else if (priority(s) > priority(stack2.peek())){
                        stack1.push(s);
                        break;
                    }else {
                        stack1.push(stack2.pop());
                    }
                }

            }
        }
        for (int i = 0; i < stack2.size(); i++) {
            stack1.push(stack2.pop());
        }
        stack1 = reverseStack(stack1);
        List<String> list1 = new ArrayList<>();
        while (!stack1.isEmpty()){
            list1.add(stack1.pop());
        }

        return list1;
    }

    // 栈反转
    public static Stack<String> reverseStack(Stack<String> stack){
        Stack<String> stack1 = new Stack<>();
        while (!stack.isEmpty()){
            stack1.push(stack.pop());
        }
        return stack1;
    }