数据结构与算法(三) - 栈

四、栈

4.1 栈的介绍

1. 栈是一个先入后出(FILO-First In Last Out)的有序列表。

2. 栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。

3. 根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除

4. 出栈(pop)和入栈(push)的概念

   

4.2 栈的应用场景

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

4.3 栈的快速入门

用数组模拟栈的使用

public class ArrayStack {
    /**
     * 栈的大小
     */
    private final int maxSize;
    /**
     * 数组模拟栈
     */
    private final int[] stack;
    /**
     * top表示栈顶,初始化为-1
     */
    private int top = -1;

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

    // 栈空
    public boolean isFull() {
        return top == maxSize - 1;
    }

    // 栈满
    public boolean isEmpty() {
        return top == -1;
    }

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

    // 出栈
    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]);
        }
    }
}

演示

public class ArrayStackDemo {
    public static void main(String[] args) {
        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) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case "exit":
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出~~~");
    }
}

使用链表来模拟栈

public class LinkedListStack<T> {
    // 定义栈顶
    private final Node<T> top = new Node<>();
    private int size = 0;

    public boolean isEmpty() {
        return size == 0;
    }

    // 入栈
    public void push(T value) {
        Node<T> node = new Node<>(value);
        // 第一个节点的插入
        if (top.next != null) {
            node.next = top.next;
        }
        top.next = node;
        size++;
    }

    // 出栈
    public T pop() {
        if (top.next == null) {
            return null;
        }
        T result = top.next.value;
        top.next = top.next.next;
        size--;
        return result;
    }

    public T peek() {
        return top.next.value;
    }

    public void show() {
        if (top.next == null) {
            return;
        }
        // 大佬的写法
        for (Node<T> node = top.next; node != null; node = node.next) {
            System.out.print(node.value + " ");
        }
        // 自己的写法
        /*Node<T> node = top.next;
        while (node != null) {
            System.out.print(node.value + " ");
            node = node.next;
        }*/
        System.out.println();
    }
}

4.4 栈实现综合计算器(中缀表达式)

思路分析

1. 通过一个 index 值(索引)，来遍历我们的表达式
2. 如果发现是一个数字,就直接入数栈
3. 如果是符号,就分如下情况
   • 如果当前的符号栈为空，就直接入栈
   • 如果符号栈有操作符，就进行比较，如果当前的操作符的优先级≤栈中的操作符，就从数栈中弹出两个数，从符号栈中弹出一个符号进行运算，将得到的结果入数栈,然后当当前的操作符入符号栈; 如果当前的操作符的优先级＞栈中的操作符，就直接入符号栈
4. 当表达式扫描完毕，就顺序的从数栈和符号栈中弹出相应的数和符号,并运算
5. 最后在数栈只有一个数字,就是表达式的结果

public class Calculator {

    public static void main(String[] args) {
//        String expression = "7-5*3+9"; //==>计算该表达式会有问题
        String expression = "7*2*2-5+1-5+3-3";
        // 创建两个栈,一个数字栈,一个符号栈
        LinkedListStack<Integer> numStack = new LinkedListStack<>();
        LinkedListStack<Character> operStack = new LinkedListStack<>();
        // 定义需要的相关变量
        int index = 0;
        int num1;
        int num2;
        char oper;
        int result;
        // 将每次扫描得到char保存到ch
        char ch = ' ';
        // 用于拼接多位数
        String keepNum = "";

        // 开始do-while循环的扫描expression
        do {
            ch = expression.charAt(index);
            // 判断是否是运算符
            if (isOper(ch)) {
                // 判断当前的符号栈是否为空
                if (!operStack.isEmpty()) {
                    // 如果符号栈有操作符,就进行比较,如果当前的操作符的优先级≤栈中的操作符,就需要从数栈中pop出两个数,
                    // 再从符号栈中pop出一个符号,进行运算,将得到的结果入数栈,然后将当前的操作符入符号栈
                    if (priority(ch) <= priority(operStack.peek())) {
                        num1 = numStack.pop();
                        num2 = numStack.pop();
                        oper = operStack.pop();
                        result = cal(num1, num2, oper);
                        // 将运算结果入数栈
                        numStack.push(result);
                        // 将当前的操作符入符号栈
                        operStack.push(ch);
                    } else {
                        // 如果当前的操作符的优先级>栈中的操作符，就直接入符号栈
                        operStack.push(ch);
                    }
                } else {
                    // 如果为空直接入符号栈
                    operStack.push(ch);
                }
            } else {// 如果是数,则直接入数栈
                keepNum += ch;
                // 如果ch已经是expression的最后一位,就直接入栈
                if (index == expression.length() - 1) {
                    numStack.push(Integer.parseInt(keepNum));
                } else {
                    // 判断下一个字符是不是数字,如果是数字,就继续扫描,如果是运算符,则入栈
                    if (isOper(expression.charAt(index + 1))) {
                        numStack.push(Integer.parseInt(keepNum));
                        // 清空keepNum
                        keepNum = "";
                    }
                }
            }
            index++;
        } while (index < expression.length());

        // 当表达式扫描完毕,就顺序从数栈和符号栈中pop出相应的数和符号,并运行
        while (!operStack.isEmpty()) {
            // 如果符号栈为空,则计算到最后的结果,数栈中只有一个数字
            num1 = numStack.pop();
            num2 = numStack.pop();
            oper = operStack.pop();
            result = cal(num1, num2, oper);
            numStack.push(result);
        }
        int result2 = numStack.pop();
        System.out.printf("表达式 %s = %d", expression, result2);
    }

    /**
     * 返回运算符的优先级，优先级是程序员来确定, 优先级使用数字表示
     * 数字越大，则优先级就越高
     * 假定目前的表达式只有 +, - , * , /
     */
    public static int priority(char oper) {
        if (oper == '*' || oper == '/') {
            return 1;
        }
        if (oper == '+' || oper == '-') {
            return 0;
        }
        return -1;
    }

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

    public static int cal(int num1, int num2, char oper) {
        int result = 0;
        switch (oper) {
            case '+':
                result = num1 + num2;
                break;
            case '-':
                result = num2 - num1;
                break;
            case '*':
                result = num1 * num2;
                break;
            case '/':
                result = num2 / num1;
                break;
            default:
                break;
        }
        return result;
    }
}

4.5 前缀、中缀、后缀表达式(逆波兰表达式)

前缀表达式(波兰表达式)

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

前缀表达式的计算机求值

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

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

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

中缀表达式

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

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

后缀表达式

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

(3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 –

正常的表达式	逆波兰表达式
a+b	a b +
a+(b-c)	a b c - +
a+(b-c)*d	a b c – d * +
a+d*(b-c)	a d b c - * +
a=1+3	a 1 3 + =

后缀表达式的计算机求值

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

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

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，由此得出最终结果

4.6 逆波兰计算器

逆波兰计算器是将逆波兰表达式(后缀表达式)使用栈来计算结果

public class ReversePolishNotation {

    public static void main(String[] args) {
        System.out.println(calc("3 4 + 5 × 6 -"));
    }

    static final String ADD = "+";
    static final String MINUS = "-";
    static final String TIMES = "×";
    static final String DIVISION = "/";

    public static int calc(String str) {
        Stack<String> stack = new Stack<>();
        String[] s = str.split(" ");
        for (String item : s) {
            //匹配数字
            if (item.matches("\\d+")) {
                stack.push(item);
            } else {
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                int result;
                switch (item) {
                    case ADD:
                        result = num1 + num2;
                        break;
                    case MINUS:
                        result = num2 - num1;
                        break;
                    case TIMES:
                        result = num1 * num2;
                        break;
                    case DIVISION:
                        result = num1 / num2;
                        break;
                    default:
                        throw new RuntimeException("运算符有误");
                }
                // 把结果压入栈中
                stack.push(result + "");
            }
        }
        return Integer.parseInt(stack.pop());
    }
}

4.7 中缀表达式转换为后缀表达式

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

4.7.1 具体步骤如下

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

4.7.2 举例说明

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

扫描到的元素	s2(栈底→栈顶)	s1 (栈底→栈顶)	说明
1	1	空	数字，直接入栈
+	1	+	s1为空，运算符直接入栈
(	1	+ (	左括号，直接入栈
(	1	+ ( (	同上
2	1 2	+ ( (	数字
+	1 2	+ ( ( +	s1栈顶为左括号，运算符直接入栈
3	1 2 3	+ ( ( +	数字
)	1 2 3 +	+ (	右括号，弹出运算符直至遇到左括号
×	1 2 3 +	+ ( ×	s1栈顶为左括号，运算符直接入栈
4	1 2 3 + 4	+ ( ×	数字
)	1 2 3 + 4 ×	+	右括号，弹出运算符直至遇到左括号
-	1 2 3 + 4 × +	-	-与+优先级相同，因此弹出+，再压入-
5	1 2 3 + 4 × + 5	-	数字
到达最右端	1 2 3 + 4 × + 5 -	空	s1中剩余的运算符

4.7.3 代码实现中缀表达式转为后缀表达式

/**
 * 逆波兰表达式计算
 * 1. 将中缀表达式转化为对应的List
 * 2. 将中缀表达式的List转化为后缀表达式对应的List
 * 3. 计算后缀表达式
 */
public class ReversePolishNotation {

    public static void main(String[] args) {
        String expression = "(3.5+4.5)×4-6×2";
        List<String> s = toInfixExpressionList(expression);
        List<String> s2 = parseSuffixExpression(s);
        double calc = calc(s2);
        System.out.println(calc);
    }

    static final String ADD = "+";
    static final String SUB = "-";
    static final String MUL = "×";
    static final String DIV = "/";
    static final String LEFT = "(";
    static final String RIGHT = ")";


    /**
     * 将中缀表达式转化为对应的List
     */
    public static List<String> toInfixExpressionList(String str) {
        if (str == null || "".equals(str.trim())) {
            throw new RuntimeException("data is empty");
        }
        // 去除所有空白符
        str = replaceAllBlank(str);
        List<String> list = new ArrayList<>();
        int index = 0;
        StringBuilder sb;
        char c = ' ';
        do {
            if (isSymbol(c = str.charAt(index))) {
                list.add(c + "");
                index++;
            } else {
                sb = new StringBuilder();
                while (index < str.length() && !isSymbol(c = str.charAt(index))) {
                    sb.append(c);
                    index++;
                }
                list.add(sb.toString());
            }
        } while (index < str.length());
        return list;
    }

    /**
     * 将中缀表达式的List转化为后缀表达式对应的List
     */
    public static List<String> parseSuffixExpression(List<String> list) {
        Stack<String> stack = new Stack<>();
        // 用来存放后缀表达式
        List<String> data = Collections.synchronizedList(new ArrayList<>());
        for (String str : list) {
            if (!isSymbol(str)) {
                data.add(str);
                continue;
            }
            if (str.equals(LEFT)) {
                stack.add(str);
                continue;
            }
            if (str.equals(RIGHT)) {
                while (!stack.peek().equals(LEFT)) {
                    // 弹出运算符到List直至遇到左括号
                    data.add(stack.pop());
                }
                // 弹出一个左括号
                stack.pop();
                continue;
            }
            // 到此 情况只剩下加减乘除
            // 如果操作符的优先级和栈中的相同,则弹出栈中的操作符到List
            // 这里使用while循环进行比较是因为 栈中可能存在多个乘除遇到加减 这时要将所有的乘除弹出
            while (stack.size() != 0 && calcLevel(str) <= calcLevel(stack.peek())) {
                data.add(stack.pop());
            }
            // 将当前操作符压入栈中,这里也分两种情况
            // 1.栈空,则直接将操作符压入栈中
            // 2.当前操作符的优先级比栈中的要高
            stack.push(str);
        }
        // 这里将栈中剩余的操作符弹出存入List中
        while (stack.size() != 0) {
            data.add(stack.pop());
        }
        return data;
    }

    /**
     * 计算后缀表达式的结果
     */
    public static double calc(List<String> list) {
        Stack<String> stack = new Stack<>();
        for (String item : list) {
            //匹配数字
            if (!isSymbol(item)) {
                stack.push(item);
            } else {
                BigDecimal num1 = new BigDecimal(stack.pop());
                BigDecimal num2 = new BigDecimal(stack.pop());
                BigDecimal result;
                switch (item) {
                    case ADD:
                        result = num1.add(num2);
                        break;
                    case SUB:
                        result = num2.subtract(num1);
                        break;
                    case MUL:
                        result = num1.multiply(num2);
                        break;
                    case DIV:
                        result = num2.divide(num1, 10, BigDecimal.ROUND_HALF_UP);
                        break;
                    default:
                        throw new RuntimeException("运算符有误");
                }
                // 把结果压入栈中
                stack.push(result + "");
            }
        }
        return Double.parseDouble(stack.pop());
    }

    /**
     * 判断是不是运算符
     */
    public static boolean isSymbol(char c) {
        String str = c + "";
        return isSymbol(str);
    }

    /**
     * 判断是不是运算符
     */
    public static boolean isSymbol(String str) {
        return str.matches("\\+|-|×|/|\\(|\\)");
    }

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

    /**
     * 匹配运算等级
     *
     * @param str str
     * @return int
     */
    public static int calcLevel(String str) {
        if ("+".equals(str) || "-".equals(str)) {
            return 1;
        }
        if ("×".equals(str) || "/".equals(str)) {
            return 2;
        }
        return 0;
    }
}