数据结构与算法二：栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式-阿里云开发者社区

前言

腊月 25 仍然在学习，虽然在家学习的时间比较短，但还是想继续坚持下去，希望在春招中进入到自己满意的公司（sli）.加油加油

一、栈

1.1 栈的一个实际需求

请输入一个表达式
计算式:[7_2_2-5+1-5+3-3] 点击计算【如下图】
在这里插入图片描述
请问: 计算机底层是如何运算得到结果的？注意不是简单的把算式列出运算,因为我们看这个算式 7 * 2 * 2 - 5, 但是计算机怎么理解这个算式的(对计算机而言，它接收到的就是一个字符串)，我们讨论的是这个问题。-> 栈

1.2 栈的介绍

栈的英文为(stack)
栈是一个先入后出(FILO-First In Last Out)的有序列表。
栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。
根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除
出栈(pop)和入栈(push)的概念(如图所示)

1.3 栈的应用场景

子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。
处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。
表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)。
二叉树的遍历。
图形的深度优先(depth一first)搜索法。

二、栈的快速入门

2.1 用数组模拟栈的使用，

由于栈是一种有序列表，当然可以使用数组的结构来储存栈的数据内容，下面我们就用数组模拟栈出栈，入栈等操作。

2.2 实现思路分析

实现思路分析，并画出示意图
在这里插入图片描述

2.3 代码实现

package com.feng.ch04_stack;

import java.util.Scanner;

public class Ch01_ArraryStackDemo {
    public static void main(String[] args) {
        // 测试一下ArrayStack 是否正确
        // 先创建一个ArrayStack对象->表示栈
        ArrayStack stack = new ArrayStack(4);
        String key = "";
        boolean loop = true; // 控制是否退出菜单
        Scanner scanner = new Scanner(System.in);

        while (loop) {
            System.out.println("show: 表示显示栈");
            System.out.println("exit: 退出程序");
            System.out.println("push: 表示添加数据到栈(入栈)");
            System.out.println("pop: 表示从栈取出数据(出栈)");
            System.out.println("请输入你的选择");
            key = scanner.next();
            switch (key) {
            case "show":
                stack.list();
                break;
            case "push":
                System.out.println("请输入一个数");
                int value = scanner.nextInt();
                stack.push(value);
                break;
            case "pop":
                try {
                    int res = stack.pop();
                    System.out.printf("出栈的数据是 %d\n", res);
                } catch (Exception e) {
                    // TODO: handle exception
                    System.out.println(e.getMessage());
                }
                break;
            case "exit":
                scanner.close();
                loop = false;
                break;
            default:
                break;
            }
        }

        System.out.println("程序退出~~~");
    }
}

class ArrayStack {
    private int maxSize;
    private int[] stack;
    private int top = -1;

    public ArrayStack(int maxSize) {
        this.maxSize = maxSize;
        this.stack = new int[this.maxSize];
    }

    /**
     * 栈满
     */
    public Boolean isFull() {
        return top == maxSize - 1;
    }

    /**
     * 栈空
     */
    public Boolean isEmpty() {
        return top == -1;
    }

    /**
     * 入栈 -push
     */
    public void push(int value) {
        if (isFull()) {
            System.out.println("链表为满~~");
            return;
        }
        top++;
        stack[top] = value;
    }

    /**
     * 出栈 pop
     */
    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("栈空，没有数据~");
        }
        int value = stack[top];
        top--;
        return value;
    }

    /**
     * 显示栈的情况[遍历栈]， 遍历时，需要从栈顶开始显示数据
     */
    public void list() {
        if (isEmpty()) {
            System.out.println("栈空~");
            return;
        }
        for (int i = top; i >= 0; i--) {
            System.out.printf("stack[%d]=%d\n", i, stack[i]);
        }
    }
}

三、课后练习：链表来模拟栈

课堂练习，将老师写的程序改成使用链表来模拟栈

3.1 图表详解

在这里插入图片描述

3.2 代码示例

package com.feng.ch04_stack;

public class Ch02_LinkedStackDemo {

    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);

        LinkedStack stack = new LinkedStack();
        stack.push(node1);
        stack.push(node2);
        stack.push(node3);
        stack.push(node4);
        stack.push(node5);
        stack.list();System.out.println();

        System.out.println("**************出栈一个**********************");
        Node pop = stack.pop();
        System.out.println("pop出的头结点:"+pop.getNo());
        stack.list();System.out.println();

        System.out.println("**************出栈一个**********************");
        Node pop1 = stack.pop();
        System.out.println("pop出的头结点:"+pop1.getNo());
        stack.list();System.out.println();
    }
}

class LinkedStack {

    // 先初始化一个头节点, 头节点不要动, 不存放具体的数据
    private Node top = new Node(0);   

    public Node getNode() {
        return top;
    }

    /**
     * push 添加
     * 
     * @param newNode
     */
    public void push(Node newNode) {
        if (top.getNext() == null) {
            top.setNext(newNode);
        } else {
            //  这两步 不能互换，互换则出错  ，
            // 1、先挂载下面的，2、再挂载到top节点上。
            newNode.setNext(top.getNext());  // 将原来的 挂在 新的下面。 
            top.setNext(newNode);  // 将新的挂在 头上
        }
    }

    /**
     * pop 出栈
     * 
     * @return
     */
    public Node pop() {
        if (top == null) {
            throw new RuntimeException("链表为空");
        }
        Node value = top.getNext();
//        top = value.getNext();     // 这句话错了，这句话是赋值给 头结点。
        top.setNext(value.getNext());
        return value;
    }


    /**
      *   遍历 
     */
    public void list() {
        if (top.getNext()==null) {
            System.out.println("链表为空~");
            return;
        }
        Node temporary = top.getNext();
        while (true) {
            if (temporary == null) {
                break;
            }
            System.out.println("节点的编号为："+temporary.getNo());
            temporary = temporary.getNext();             // 后移一位。
//            temporary.setNext(temporary.getNext());   // 这句话 错了，这是设置值。
        }
    }

    /**
     *  仅读取 栈顶的值。
     */
    public void getTop() {

    }

}

/**
 * 定义一个节点
 * 
 * @param next
 */
class Node {
    private int no;
    private Node next;

    public Node(int no) {
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

}

四. 栈实现综合计算器（中缀表达式）

使用栈来实现综合计算器
在这里插入图片描述

[4.1 思路分析（图解）

在这里插入图片描述

4.2 代码实现：

先实现一位数的运算，扩展到多位数的运算

package com.feng.ch04_stack;

public class Ch03_Calculator {

    public static void main(String[] args) {
        // 根据前面老师思路，完成表达式的运算
        // String expression = "3+2*6-2"; // 13//如何处理多位数的问题？
        // String expression = "7*2*2-5+1-5+3-4"; // 18//如何处理多位数的问题？
        String expression = "70+2*6-2"; // -10//如何处理多位数的问题？
        // 创建两个栈，数栈，一个符号栈
        ArrayStack2 numStack = new ArrayStack2(10);
        ArrayStack2 operStack = new ArrayStack2(10);

        // 定义需要的相关变量
        int index = 0; // 用于扫描
        int num1 = 0;
        int num2 = 0;
        int oper = 0;
        int res = 0;
        char ch = ' '; // 将每次扫描得到 char 保存到 ch
        // 用于拼接多位数
        String keepNum = "";

        // 开发 while 循环 的 扫描 experssion
        while (true) {
            // 依次 得到 expression 的 每一个字符
            ch = expression.substring(index, index + 1).charAt(0);
            /**
             * 获取表达式的第一个字符， 判断 字符 or 数字
             */
            // 当为 操作符时，然后做相应的处理
            if (operStack.isOper(ch)) {
                // 判断当前的符号栈是否为空
                if (!operStack.isEmpty()) {
                    // 如果符号栈有操作符,就进行比较,如果当前的操作符的优先级小于或者等于栈中的操作符,
                    // 就需要从数栈中pop出两个数, 在从符号栈中pop出一个符号， 进行运算，将得到结果，入数栈，然后将当前的操作符入符号栈
                    if (operStack.getPriority(ch) <= operStack.getPriority(operStack.peek())) {
                        num1 = numStack.pop();
                        num2 = numStack.pop();
                        oper = operStack.pop();
                        res = numStack.cal(num1, num2, oper);
                        /**
                         * 把运算的结果入数栈 然后将当前的操作符入符号栈
                         */
                        operStack.push(ch);
                        numStack.push(res);
                    } else {
                        // 如果当前的操作符的优先级大于栈中的操作符，就直接入符号栈
                        operStack.push(ch);
                    }
                } else {
                    // 如果为空直接入符号栈。。。
                    operStack.push(ch);
                }
            } else {
                // 当为数时，直接入栈， 这里的ch为字符，需要转换成 数字,   这个只能是个位数的运算
                // numStack.push(ch - 48); // ? "1+3" '1' => 1

                /**
                 * 1、当处理多位数时，不能发现是一个数就立即入栈，因为他可能是多位数 2、在处理数，需要向expression 的表达式的 index
                 * 后看一位，如果是数就进行扫描，如果是符号才入栈 3、因此我们需要定义一个变量 字符串，用于拼接
                 */
                // 处理多位数
                keepNum += ch;

                // 如果 ch 已经是expression 的最后一位，就直接入栈
                if (index == expression.length() - 1) {
                    numStack.push(Integer.parseInt(keepNum));
                } else {
                    // 判断下一个字符是不是数字，如果是数字，就继续扫描，如果是运算符，则入栈
                    // 注意是看后一位，不是index++
                    if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
                        // 如果后一位是运算符，则入栈 keepNum = "1" 或者 "123"
                        numStack.push(Integer.parseInt(keepNum));
                        // 重要的 ！！！！ ，keepNum清空
                        keepNum = "";
                    }
                }
            }
            index++;
            if (index >= expression.length()) {
                break;
            }
        }
        // 当表达式 扫描完毕，就顺序的从数栈和符号栈中pop出相应的数和符号，并运行计算
        while (true) {
            if (operStack.isEmpty()) {
                break;
            }
            num1 = numStack.pop();
            num2 = numStack.pop();
            oper = operStack.pop();
            res = numStack.cal(num1, num2, oper);
            // 入栈
            numStack.push(res);
        }
        // 将数栈的最后数，pop出，就是结果
        int res2 = numStack.pop();
        System.out.printf("表达式 %s = %d", expression, res2);
    }
}

/**
 * 
 * @author 89796
 *
 */
class ArrayStack2 {
    private int maxSize;
    private int[] stack;
    private int top = -1;

    public ArrayStack2(int maxSize) {
        this.maxSize = maxSize;
        this.stack = new int[this.maxSize];
    }

    /**
     * 栈满
     */
    public Boolean isFull() {
        return top == maxSize - 1;
    }

    /**
     * 栈空
     */
    public Boolean isEmpty() {
        return top == -1;
    }

    /**
     * 入栈 -push
     */
    public void push(int value) {
        if (isFull()) {
            System.out.println("链表为满~~");
            return;
        }
        top++;
        stack[top] = value;
    }

    /**
     * 出栈 pop
     */
    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("栈空，没有数据~");
        }
        int value = stack[top];
        top--;
        return value;
    }

    /**
     * 显示栈的情况[遍历栈]， 遍历时，需要从栈顶开始显示数据
     */
    public void list() {
        if (isEmpty()) {
            System.out.println("栈空~");
            return;
        }
        for (int i = top; i >= 0; i--) {
            System.out.printf("stack[%d]=%d\n", i, stack[i]);
        }
    }

    /**
     * 以下为 新添加的方法
     */
    // 返回栈顶的值 ，但不是真正的pop
    public int peek() {
        return stack[top];
    }

    // 返回运算符的优先级，优先级是程序员来确定, 优先级使用数字表示
    // 数字越大，则优先级就越高.
    public int getPriority(int oper) {
        if (oper == '*' || oper == '/') {
            return 1;
        } else if (oper == '+' || oper == '-') {
            return 0;
        } else {
            return -1;
        }
    }

    // 判断是不是一个运算符
    public Boolean isOper(char val) {
        return val == '+' || val == '-' || val == '*' || val == '/';
    }

    // 计算方法
    public int cal(int num1, int num2, int oper) {
        int res = 0;
        switch (oper) {
        case '+':
            res = num1 + num2;
            break;
        case '-':
            res = num2 - num1;
            break;
        case '*':
            res = num1 * num2;
            break;
        case '/':
            res = num2 / num1;
            break;
        default:
            break;
        }
        return res;
    }
}

课后练习-给表达式加入小括号

后面有，这里不做

前面讲的都是中缀表达式
前缀

五、前缀、中缀、后缀

介绍顺序和学习顺序：中缀表达式、前缀表达式、后缀表达式

5.1 中缀表达式

举例说明 ：中缀表达式就是常见的运算表达式，如(3+4)×5-6

中缀表达式的求值是我们人最熟悉的，但是对计算机来说却不好操作(前面我们讲的案例就能看的这个问题)，因此，在计算结果时，往往会将中缀表达式转成其它表达式来操作(一般转成后缀表达式.)

前面的计算方式就是基于中缀表达式来计算的。

5.2 前缀表达式（波兰表达式）

前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前

举例说明：中缀表达式：(3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6

前缀表达式的计算机求值

从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素和次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果

例如: (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6 , 针对前缀表达式求值步骤如下:

从右至左扫描，将6、5、4、3压入堆栈
遇到+运算符，因此弹出3和4（3为栈顶元素，4为次顶元素），计算出3+4的值，得7，再将7入栈
接下来是×运算符，因此弹出7和5，计算出7×5=35，将35入栈
最后是-运算符，计算出35-6的值，即29，由此得出最终结果

5.3 后缀表达式（逆波兰表达式）***

后缀表达式又称逆波兰表达式,与前缀表达式相似，只是运算符位于操作数之后

中举例说明： (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 –

再比如:
在这里插入图片描述

后缀表达式的计算方式

从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素和栈顶元素），并将结果入栈；

重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果

例如: (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 - , 针对后缀表达式求值步骤如下:

从左至右扫描，将3和4压入堆栈；
遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈；
将5入栈；
接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；
将6入栈；
最后是-运算符，计算出35-6的值，即29，由此得出最终结果

六、逆波兰计算器

6.1 任务描述

我们完成一个逆波兰计算器，要求完成如下任务；

输入一个逆波兰表达式(后缀表达式)，使用栈(Stack), 计算其结果
支持小括号和多位数整数，因为这里我们主要讲的是数据结构，因此计算器进行简化，只支持对整数的计算。
思路分析

从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素和栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果

例如: (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 - , 针对后缀表达式求值步骤如下:
从左至右扫描，将3和4压入堆栈；
遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈；
将5入栈；
接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；
将6入栈；
最后是-运算符，计算出35-6的值，即29，由此得出最终结果

6.2 代码完成

package com.feng.ch04_stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 测试 说明为了方便，逆波兰表达式 的数字和符号使用空格隔开 先定义给逆波兰表达式 (3+4)×5-6 => 3 4 + 5 × 6 -=> 29
 * (30+4)×5-6 => 30 4 + 5 × 6 -=> 164 4 * 5 - 8 + 60 + 8 / 2 => 4 5 * 8 - 60 + 8
 * 2 / + =>76
 */
public class Ch04_PolandNotation {

    public static void main(String[] args) {

        // String suffixExpression = "3 4 + 5 * 6 -"; //29
        // String suffixExpression = "30 4 + 5 * 6 -"; //164
        String suffixExpression = "4 5 * 8 - 60 + 8 2 / +"; // 76

        /**
         * 思路: 1. 先将 "3 4 + 5 × 6 -" => 放到ArrayList中 2. 将 ArrayList 传递给一个方法，遍历 ArrayList
         * 配合栈 完成计算
         */

        List<String> list = getListString(suffixExpression);
        System.out.println("list=" + list);
        int res = calculate(list);
        System.out.println("计算的结果：" + res);
    }

    /**
     * 将一个逆波兰表达式，依次将数据和运算符 放入到 ArrayList 中
     * 
     * @param suffixExpression
     * @return
     */
    private static List<String> getListString(String suffixExpression) {
        // 将
        String[] split = suffixExpression.split(" ");
        List<String> list = new ArrayList<>();
        for (String ele : split) {
            list.add(ele);
        }
        return list;
    }

    // 完成对逆波兰表达式的运算
    /*
     * 1)从左至右扫描，将3和4压入堆栈； 2)遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈； 3)将5入栈；
     * 4)接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈； 5)将6入栈； 6)最后是-运算符，计算出35-6的值，即29，由此得出最终结果
     */
    public static int calculate(List<String> list) {
        // 创建栈，只需要一个栈即可
        Stack<String> stack = new Stack<>();
        // 遍历list
        for (String item : list) {
            // 这里使用正则表达式来取出数
            if (item.matches("\\d+")) {
                // 入栈
                stack.push(item);
            } else {
                // pop 出两个数，并运算，再入栈
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int res = 0;
                if (item.equals("+")) {
                    res = num1 + num2;
                } else if (item.equals("-")) {
                    res = num1 - num2;
                } else if (item.equals("*")) {
                    res = num1 * num2;
                } else if (item.equals("/")) {
                    res = num1 / num2;
                } else {
                    throw new RuntimeException("运算符有误");
                }
                stack.push("" + res); // 整型转变为 字符串 最快的方式
            }
        }
        return Integer.parseInt(stack.pop());
    }

}

6.3 中缀表达式转后缀表达式

大家看到，后缀表达式适合计算器进行运算，但是人却不太容易写出来，尤其是表达式很长的情况下，因此在开发中，我们需要将中缀表达式转成后缀表达式。

6.3.1 具体步骤：

初始化两个栈：运算符栈s1和储存中间结果的栈s2；
从左至右扫描中缀表达式；
遇到操作数时，将其压s2；
遇到运算符时，比较其与s1栈顶运算符的优先级：
1. 如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
2. 否则，若优先级比栈顶运算符的高，也将运算符压入s1；
3. 否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4.1)与s1中新的栈顶运算符相比较；
遇到括号时：
1. 如果是左括号“(”，则直接压入s1
2. 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
重复步骤2至5，直到表达式的最右边
将s1中剩余的运算符依次弹出并压入s2
依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式

6.3.2 举例说明

将中缀表达式 “ 1+((2+3)*4)-5 ” 转换为后缀表达式的过程如下

因此结果为：“1 2 3 + 4 * + 5 -”
在这里插入图片描述

6.3.3 思路分析

在这里插入图片描述

6.3.4 代码实现

代码中包含了上面的计算代码。

package com.feng.ch04_stack;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Stack;

public class Ch04_PolandNotation {

    public static void main(String[] args) {

        /**
         * 完成将一个中缀表达式转成后缀表达式的功能 说明 1. 1+((2+3)×4)-5 => 转成 1 2 3 + 4 × + 5 – 2. 因为直接对str
         * 进行操作，不方便，因此 先将 "1+((2+3)×4)-5" =》 中缀的表达式对应的List 即 "1+((2+3)×4)-5" =>
         * ArrayList [1,+,(,(,2,+,3,),*,4,),-,5] 3. 将得到的中缀表达式对应的List => 后缀表达式对应的List 即
         * ArrayList [1,+,(,(,2,+,3,),*,4,),-,5] =》 ArrayList [1,2,3,+,4,*,+,5,–]
         */
        String expression = "1+((2+3)*4)-5";// 注意表达式
        List<String> infixExpressionList = toInfixExpressionList(expression);
        System.out.println("中缀表达式对应的List=" + infixExpressionList);
        List<String> parseSuffixExpreesionList = parseSuffixExpreesionList(infixExpressionList);
        System.out.println("后缀表达式对应的List" + parseSuffixExpreesionList); //ArrayList [1,2,3,+,4,*,+,5,–] 
        System.out.printf("计算后缀表达式的结果=%d", calculate(parseSuffixExpreesionList)); // 16

    }

    /**
     * 即 ArrayList [1,+,(,(,2,+,3,),*,4,),-,5] =》 ArrayList [1,2,3,+,4,*,+,5,–]
     * 方法：将得到的中缀表达式对应的List => 后缀表达式对应的List
     * 
     * @param list
     * @return
     */
    public static List<String> parseSuffixExpreesionList(List<String> list) {
        //
        /**
         * 定义两个栈 说明：因为s2 这个栈，在整个转换过程中，没有pop操作，而且后面我们还需要逆序输出 因此比较麻烦，这里我们就不用 Stack<String>
         * 直接使用 List<String> s2 Stack<String> s2 = new Stack<String>(); // 储存中间结果的栈s2
         */
        Stack<String> s1 = new Stack<String>(); // 符号栈
        List<String> s2 = new ArrayList<String>(); // 储存中间结果的Lists2

        for (String item : list) {
            // 如果是一个数， 直接加入到 s2
            if (item.matches("\\d+")) {
                s2.add(item);
            } else if (item.equals("(")) {
                s1.push(item);
            } else if (item.equals(")")) {
                /**
                 * 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止， 此时将这一对括号丢弃
                 */
                while (!s1.peek().equals("(")) {
                    s2.add(s1.pop());
                }
                // !!! 将 ( 弹出 s1栈， 消除小左括号
                s1.pop();
            } else {
                // 当item的优先级小于等于s1栈顶运算符，将s1栈顶的运算符弹出并加入到s2中，再次转到(4.1)与s1中新的栈顶运算符相比较
                // 问题：我们缺少一个比较优先级高低的方法
                while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)) {
                    s2.add(s1.pop());
                }
                // 还需要将item压入栈
                s1.push(item);
            }
        }
        // 将s1中剩余的运算符依次弹出并加入s2
        while (s1.size() != 0) {
            s2.add(s1.pop());
        }
        //注意因为是存放到List, 因此按顺序输出就是对应的后缀表达式对应的List
        return s2;
    }

    /**
     * 方法：将 中缀表达式转成对应的List s="1+((2+3)×4)-5"; => [1, +, (, (, 2, +, 3, ), *, 4, ),
     * -, 5]
     * 
     * @param s
     * @return
     */
    public static List<String> toInfixExpressionList(String s) {

        List<String> list = new ArrayList<>();
        int i = 0; // 这时是一个指针，用于遍历 中缀表达式字符串
        String str;// 对多位数的拼接
        char c; // 每遍历到一个字符，就放入到c
        do {
            /**
             * 判断的目的 是为了多位数
             */
            // 如果 c 是一个 非数字，加入到 list
            if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {
                list.add("" + c);
                i++; // i需要后移
            } else {
                // 如果是一个数，需要考虑多位数
                str = ""; // 现将str 置成 ""，'0'[48]->'9'[57]
                while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) {
                    str += c;
                    i++;
                }
                list.add(str);
            }
        } while (i < s.length());

        return list;
    }

    /**
     * 将一个逆波兰表达式，依次将数据和运算符 放入到 ArrayList 中
     * 
     * @param suffixExpression
     * @return
     */
    private static List<String> getListString(String suffixExpression) {
        // 将
        String[] split = suffixExpression.split(" ");
        List<String> list = new ArrayList<>();
        for (String ele : split) {
            list.add(ele);
        }
        return list;
    }

    // 完成对逆波兰表达式的运算
    /*
     * 1)从左至右扫描，将3和4压入堆栈； 2)遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈； 3)将5入栈；
     * 4)接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈； 5)将6入栈； 6)最后是-运算符，计算出35-6的值，即29，由此得出最终结果
     */
    public static int calculate(List<String> list) {
        // 创建栈，只需要一个栈即可
        Stack<String> stack = new Stack<>();
        // 遍历list
        for (String item : list) {
            // 这里使用正则表达式来取出数
            if (item.matches("\\d+")) {
                // 入栈
                stack.push(item);
            } else {
                // pop 出两个数，并运算，再入栈
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int res = 0;
                if (item.equals("+")) {
                    res = num1 + num2;
                } else if (item.equals("-")) {
                    res = num1 - num2;
                } else if (item.equals("*")) {
                    res = num1 * num2;
                } else if (item.equals("/")) {
                    res = num1 / num2;
                } else {
                    throw new RuntimeException("运算符有误");
                }
                stack.push("" + res); // 整型转变为 字符串 最快的方式
            }
        }
        return Integer.parseInt(stack.pop());
    }

}

/**
 * 编写一个类 Operation 可以返回一个运算符 对应的优先级
 * 
 * @author 89796
 */
class Operation {
    private static int ADD = 1; // +
    private static int SUB = 1; // -
    private static int MUL = 2; // *
    private static int DIV = 2; // /

    // 写一个方法，返回对应的优先级数字
    public static int getValue(String operation) {
        int result = 0;
        switch (operation) {
        case "+":
            result = ADD;
            break;
        case "-":
            result = SUB;
            break;
        case "*":
            result = MUL;
            break;
        case "/":
            result = DIV;
            break;
        default:
            System.out.println("不存在该运算符" + operation);
            break;
        }
        return result;
    }
}

七、逆波兰计算器完整版

7.1 功能包括

完整版的逆波兰计算器，功能包括

支持 + - * / ( )
多位数，支持小数,
兼容处理, 过滤任何空白字符，包括空格、制表符、换页符

逆波兰计算器完整版考虑的因素较多，下面给出完整版代码供同学们学习，其基本思路和前面一样，也是使用到：中缀表达式转后缀表达式。

7.2 代码实现（直接copy）

package com.feng.ch04_stack;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;
import java.util.regex.Pattern;

public class ch05_ReversePolishMultiCalc {

    /**
     * 匹配 + - * / ( ) 运算符
     */
    static final String SYMBOL = "\\+|-|\\*|/|\\(|\\)";

    static final String LEFT = "(";
    static final String RIGHT = ")";
    static final String ADD = "+";
    static final String MINUS = "-";
    static final String TIMES = "*";
    static final String DIVISION = "/";

    /**
     * 加減 + -
     */
    static final int LEVEL_01 = 1;
    /**
     * 乘除 * /
     */
    static final int LEVEL_02 = 2;

    /**
     * 括号
     */
    static final int LEVEL_HIGH = Integer.MAX_VALUE;

    static Stack<String> stack = new Stack<>();
    static List<String> data = Collections.synchronizedList(new ArrayList<String>());

    /**
     * 去除所有空白符
     * 
     * @param s
     * @return
     */
    public static String replaceAllBlank(String s) {
        // \\s+ 匹配任何空白字符，包括空格、制表符、换页符等等, 等价于[ \f\n\r\t\v]
        return s.replaceAll("\\s+", "");
    }

    /**
     * 判断是不是数字 int double long float
     * 
     * @param s
     * @return
     */
    public static boolean isNumber(String s) {
        Pattern pattern = Pattern.compile("^[-\\+]?[.\\d]*$");
        return pattern.matcher(s).matches();
    }

    /**
     * 判断是不是运算符
     * 
     * @param s
     * @return
     */
    public static boolean isSymbol(String s) {
        return s.matches(SYMBOL);
    }

    /**
     * 匹配运算等级
     * 
     * @param s
     * @return
     */
    public static int calcLevel(String s) {
        if ("+".equals(s) || "-".equals(s)) {
            return LEVEL_01;
        } else if ("*".equals(s) || "/".equals(s)) {
            return LEVEL_02;
        }
        return LEVEL_HIGH;
    }

    /**
     * 匹配
     * 
     * @param s
     * @throws Exception
     */
    public static List<String> doMatch(String s) throws Exception {
        if (s == null || "".equals(s.trim()))
            throw new RuntimeException("data is empty");
        if (!isNumber(s.charAt(0) + ""))
            throw new RuntimeException("data illeagle,start not with a number");

        s = replaceAllBlank(s);

        String each;
        int start = 0;

        for (int i = 0; i < s.length(); i++) {
            if (isSymbol(s.charAt(i) + "")) {
                each = s.charAt(i) + "";
                // 栈为空，(操作符，或者 操作符优先级大于栈顶优先级 && 操作符优先级不是( )的优先级 及是 ) 不能直接入栈
                if (stack.isEmpty() || LEFT.equals(each)
                        || ((calcLevel(each) > calcLevel(stack.peek())) && calcLevel(each) < LEVEL_HIGH)) {
                    stack.push(each);
                } else if (!stack.isEmpty() && calcLevel(each) <= calcLevel(stack.peek())) {
                    // 栈非空，操作符优先级小于等于栈顶优先级时出栈入列，直到栈为空，或者遇到了(，最后操作符入栈
                    while (!stack.isEmpty() && calcLevel(each) <= calcLevel(stack.peek())) {
                        if (calcLevel(stack.peek()) == LEVEL_HIGH) {
                            break;
                        }
                        data.add(stack.pop());
                    }
                    stack.push(each);
                } else if (RIGHT.equals(each)) {
                    // ) 操作符，依次出栈入列直到空栈或者遇到了第一个)操作符，此时)出栈
                    while (!stack.isEmpty() && LEVEL_HIGH >= calcLevel(stack.peek())) {
                        if (LEVEL_HIGH == calcLevel(stack.peek())) {
                            stack.pop();
                            break;
                        }
                        data.add(stack.pop());
                    }
                }
                start = i; // 前一个运算符的位置
            } else if (i == s.length() - 1 || isSymbol(s.charAt(i + 1) + "")) {
                each = start == 0 ? s.substring(start, i + 1) : s.substring(start + 1, i + 1);
                if (isNumber(each)) {
                    data.add(each);
                    continue;
                }
                throw new RuntimeException("data not match number");
            }
        }
        // 如果栈里还有元素，此时元素需要依次出栈入列，可以想象栈里剩下栈顶为/，栈底为+，应该依次出栈入列，可以直接翻转整个stack 添加到队列
        Collections.reverse(stack);
        data.addAll(new ArrayList<>(stack));

        System.out.println(data);
        return data;
    }

    /**
     * 算出结果
     * 
     * @param list
     * @return
     */
    public static Double doCalc(List<String> list) {
        Double d = 0d;
        if (list == null || list.isEmpty()) {
            return null;
        }
        if (list.size() == 1) {
            System.out.println(list);
            d = Double.valueOf(list.get(0));
            return d;
        }
        ArrayList<String> list1 = new ArrayList<>();
        for (int i = 0; i < list.size(); i++) {
            list1.add(list.get(i));
            if (isSymbol(list.get(i))) {
                Double d1 = doTheMath(list.get(i - 2), list.get(i - 1), list.get(i));
                list1.remove(i);
                list1.remove(i - 1);
                list1.set(i - 2, d1 + "");
                list1.addAll(list.subList(i + 1, list.size()));
                break;
            }
        }
        doCalc(list1);
        return d;
    }

    /**
     * 运算
     * 
     * @param s1
     * @param s2
     * @param symbol
     * @return
     */
    public static Double doTheMath(String s1, String s2, String symbol) {
        Double result;
        switch (symbol) {
        case ADD:
            result = Double.valueOf(s1) + Double.valueOf(s2);
            break;
        case MINUS:
            result = Double.valueOf(s1) - Double.valueOf(s2);
            break;
        case TIMES:
            result = Double.valueOf(s1) * Double.valueOf(s2);
            break;
        case DIVISION:
            result = Double.valueOf(s1) / Double.valueOf(s2);
            break;
        default:
            result = null;
        }
        return result;

    }

    public static void main(String[] args) {
        // String math = "9+(3-1)*3+10/2";
        String math = "12.8 + (2 - 3.55)*4+10/5.0";
        try {
            doCalc(doMatch(math));
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

}

数据结构与算法二：栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式

前言

一、栈

1.1 栈的一个实际需求

1.2 栈的介绍

1.3 栈的应用场景

二、栈的快速入门

2.1 用数组模拟栈的使用，

2.2 实现思路分析

2.3 代码实现

三、课后练习：链表来模拟栈

3.1 图表详解

3.2 代码示例

四. 栈实现综合计算器（中缀表达式）

[4.1 思路分析（图解）

4.2 代码实现：

五、前缀、中缀、后缀

5.1 中缀表达式

5.2 前缀表达式（波兰表达式）

5.3 后缀表达式（逆波兰表达式）***

六、逆波兰计算器

6.1 任务描述

6.2 代码完成

6.3 中缀表达式转后缀表达式

6.3.1 具体步骤：

6.3.2 举例说明

6.3.3 思路分析

6.3.4 代码实现

七、逆波兰计算器完整版

7.1 功能包括

7.2 代码实现（直接copy）

热门文章

最新文章

相关电子书

数据结构与算法二：栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式

前言

一、 栈

1.1 栈的一个实际需求

1.2 栈的介绍

1.3 栈的应用场景

二、栈的快速入门

2.1 用数组模拟栈的使用，

2.2 实现思路分析

2.3 代码实现

三、课后练习：链表来模拟栈

3.1 图表详解

3.2 代码示例

四. 栈实现综合计算器（中缀表达式）

[4.1 思路分析（图解）

4.2 代码实现：

五、前缀、中缀、后缀

5.1 中缀表达式

5.2 前缀表达式（波兰表达式）

5.3 后缀表达式（逆波兰表达式）***

六、逆波兰 计算器

6.1 任务描述

6.2 代码完成

6.3 中缀表达式转后缀表达式

6.3.1 具体步骤：

6.3.2 举例说明

6.3.3 思路分析

6.3.4 代码实现

七、逆波兰计算器完整版

7.1 功能包括

7.2 代码实现（直接copy）

热门文章

最新文章

相关电子书

一、栈

六、逆波兰计算器