[数据结构与算法]栈 Stack 及 用栈实现简单计算器

栈 Stack

github: https://github.com/hongbao-chen/learn-java-datastuctures

一、介绍：

栈是限制插入和删除只能在一个位置操作的线性数据结构。先进后出。

压栈/入栈：push

出栈/弹栈：pop

二、栈的实现

• 栈实现

  由于栈是一个表，因此任何实现表的方法都可以用来实现栈。主要有两种方式，链表实现和数组实现。

• 链表实现栈

  可以使用单链表来实现栈。通过在表顶端插入一个元素来实现 PUSH，通过删除表顶端元素来实现 POP。使用链表方式实现的栈又叫动态栈。动态栈有链表的部分特性，即元素与元素之间在物理存储上可以不连续，但是功能有些受限制，动态栈只能在栈顶处进行插入和删除操作，不能在栈尾或栈中间进行插入和删除操作

• 数组实现栈

  栈也可以用数组来实现。使用数组方式实现的栈叫静态栈

1.使用数组实现栈：

package com.example.stack.basic;

public class ArrayStack {
    /**
     * 栈大小
     */
    private int maxStack;

    private int[] stack;

    /**
     * 栈顶所在位置： 栈为空时默认-1
     */
    private int top = -1;

    public ArrayStack(int maxStack) {
        this.maxStack = maxStack;
        //初始化数组
        this.stack = new int[maxStack];
    }

    /**
     * 1.压栈
     * 2.弹栈
     * 3.判断是否满栈
     * 4.判断是否空栈
     */

    public boolean isFull() {

        return this.top == this.maxStack - 1;

    }

    public boolean isEmpty(){

        return this.top == -1;

    }

    //压栈
    public void push(int val){
        if (isFull()){
            throw new RuntimeException("stack is full");
        }

        top++;
        stack[top]=val;

    }

    //出栈
    public int pop(){
        if (isEmpty()){
            throw new RuntimeException("stack is empty");
        }

        return stack[top--];

    }

    public void list(){
        if (isEmpty()){
            throw new RuntimeException("stack is empty");
        }

        for (int i = 0; i < stack.length; i++) {
            System.out.printf("stack[%d]=%d\n",i,stack[i]);
        }

    }

}

2.使用栈实现计算器: + - * /

栈：

/**
 * 使用泛型，兼容 int char Or 其他类型
 * @param <T>
 */
public class ArrayStack<T> {
    /**
     * 栈大小
     */
    private int maxStack;

    private T[] stack;

    /**
     * 栈顶所在位置： 栈为空时默认-1
     */
    private int top = -1;

    public ArrayStack(int maxStack) {
        this.maxStack = maxStack;
        //初始化数组
        this.stack = (T[]) new Object[maxStack];
    }

    /**
     * 1.压栈
     * 2.弹栈
     * 3.判断是否满栈
     * 4.判断是否空栈
     */

    public boolean isFull() {

        return this.top == this.maxStack - 1;

    }

    public boolean isEmpty(){

        return this.top == -1;

    }

    //压栈
    public void push(T val){
        if (isFull()){
            throw new RuntimeException("stack is full");
        }

        top++;
        stack[top]=val;

    }

    //出栈
    public T pop(){
        if (isEmpty()){
            throw new RuntimeException("stack is empty");
        }

        return stack[top--];

    }

    public void list(){
        if (isEmpty()){
            throw new RuntimeException("stack is empty");
        }

        for (int i = 0; i < stack.length; i++) {
            System.out.printf("stack[%d]=%c\n",i,stack[i]);
        }

    }

    public T peek() {

        if (isEmpty()){
            throw new RuntimeException("stack is empty");
        }

        return stack[top];

    }
}

calculate：

package com.example.stack.basic;

public class Calculate {

    /**
     * 要使用栈实现计算器；
     * 1.分为数字栈和符号栈，遍历计算式，将数字放入数字栈、运算符放入符号栈。
     * 2.计算时，从数字栈取两个 数（注意顺序），从符号栈取一个符号，计算符号栈结果。
     * 3.考虑运算符问题，加减乘除。优先级不同。
     * 由于我们利用栈，最后运算符弹栈的时候，是按运算符倒叙计算。
     * 例如：
     * 3+2*5 顺序=》 * + ok
     * 2*5+3 顺序=》 + * error
     * 即：符号栈应该 按优先级倒叙压入。（栈顶优先级要不低于栈底），换句话讲，后进符号栈的必须比栈中的优先级高。
     * 所以我们在向符号栈压入符号时，应该先判断待压入符号栈符号 大于等于 上次符号（之前所有符号）优先级；如果不符合，将这个符号算出结果，压入数字栈。
     * 然后再尝试压入符号。。。
     * 全部符号数字压入完成，进行弹栈计算，直到符号栈为空。
     *
     * @param waitCal
     */
    public static int calculate(String waitCal) {

        //定义 数字栈、符号栈
        ArrayStack<Integer> numStack = new ArrayStack<Integer>(20);
        ArrayStack<Character> symbolStack = new ArrayStack<Character>(20);

        //一、遍历 计算式，并区分符号数字，分别入栈。
        //用来存放数字字符串
        String num = "";
        //用来存放 符号
        String symbol = "";
        for (int i = 0; i < waitCal.length(); i++) {
            char c = waitCal.charAt(i);
            if (isNum(c)) {
                //是数字则 拼接，直到遇到符号（说明数字结束）在转换为 符号
                num = num + c;
            } else if (isSymbol(c)) {
                //遇到符号，赋值符号
                symbol = symbol + c;

                //将数字解析后放入 数字栈，并初始化 num局部变量，以便记录下一个数字
                numStack.push(Integer.parseInt(num));
                num = "";

                //将符号 压入符号栈（需要判断服 符号的 优先级）
                symbolPush(c, numStack, symbolStack);
                symbol = "";

            }
            //最后一个数字(num拼接完了，直接放入 数字栈)
            if( i == waitCal.length()-1){
                //将数字解析后放入 数字栈，并初始化 num局部变量，以便记录下一个数字
                numStack.push(Integer.parseInt(num));
                num = "";
            }
        }

        //二、弹栈计算
        //  符号栈没空就计算
        while (!symbolStack.isEmpty()){
            int num1 = numStack.pop();
            int num2 = numStack.pop();
            int popSymbol = symbolStack.pop();
            int calculate = calculate(num1, num2, popSymbol);
            numStack.push(calculate);
        }
        //符号栈弹空以后， 数字栈中的数字为 结果
        return numStack.pop();
    }

    /**
     * @param c
     * @param numStack
     * @param symbolStack
     */
    private static void symbolPush(char c, ArrayStack<Integer> numStack, ArrayStack<Character> symbolStack) {
        // 判断符号栈是否为空，空则可以 push
        if (symbolStack.isEmpty()) {
            symbolStack.push(c);
            return ;
        }

        // 查看符号栈顶元素
        int topVal = symbolStack.peek();
        //获取优先级
        int priorityPeek = getPriority((char) topVal);
        int priorityC = getPriority(c);

        //优先级高于等于 栈顶才能 push
        if (priorityC >= priorityPeek){
            symbolStack.push(c);
            //否则，弹出数字计算，压入数字栈，在尝试压入符号栈（递归：调用自己）
        }else {
            int num1 = numStack.pop();
            int num2 = numStack.pop();
            int symbolTop = symbolStack.pop();
            int result = calculate(num1,num2,symbolTop);
            numStack.push(result);
            //递归
            symbolPush(c,numStack,symbolStack);
        }
    }

    /**
     * 注意数字弹栈顺序：
     * 根据符号数字计算  a symbol b = result
     * @param num1  b
     * @param num2  a
     * @param symbolTop symbol
     * @return result
     */
    private static int calculate(int num1, int num2, int symbolTop) {
        //也可以
        char symbol = (char)symbolTop;
        return switch (symbol) {
            case '+' -> num2 + num1;
            case '-' -> num2 - num1;
            case '*' -> num2 * num1;
            case '/' -> num2 / num1;
            default -> throw new RuntimeException("error symbol");
        };
    }

    private static int getPriority(char topVal) {
        return switch (topVal) {
            case '+', '-' -> 0;
            case '*', '/' -> 1;
            default -> -1;
        };
    }

    private static boolean isSymbol(char c) {
        return switch (c) {
            case '+', '-', '*', '/' -> true;
            default -> false;
        };
    }

    private static boolean isNum(char c) {
        //return c >= 48 && c <= 57;
        return c >= '0' && c <= '9';
    }

}

测试：

package com.example.stack.basic;

public class Test {

    public static void main(String[] args) {

        // 测试例子：
        String waitCal = "3+2*2+13";

        int result = Calculate.calculate(waitCal);

        System.out.printf("%s=%d",waitCal,result);

    }

}

//结果：
3+2*2+13=20

3、使用栈实现计算器:+ - * / ( )

修改calculate:

package com.example.stack.improve;

import com.example.stack.basic.ArrayStack;

/**
 * 增加 处理 （） 的能力
 * 方案一： 在计算方法中，得到计算式以后，两个指针，从两端遍历，找到最外层的 （），截取出来子计算式，
 *         子计算式再次调用计算方法（递归），计算出结果替换原（）。
 * 方案二： 处理思路 与 + - * / 类似，将（）内的值，先算出来。
 *         而计算的最先单位应该为一对儿 括号。
 *
 *         一对括号是该优先级最小的单位
 *
 * 方案二
 *
 * */
public class ImproveCalculate {

    public static int calculate(String waitCal) {

        //定义 数字栈、符号栈
        ArrayStack<Integer> numStack = new ArrayStack<Integer>(20);
        ArrayStack<Character> symbolStack = new ArrayStack<Character>(20);

        //一、遍历 计算式，并区分符号数字，分别入栈。
        //用来存放数字字符串
        String num = "";
        //用来存放 符号
        String symbol = "";
        for (int i = 0; i < waitCal.length(); i++) {
            char c = waitCal.charAt(i);
            if (isNum(c)) {
                //是数字则 拼接，直到遇到符号（说明数字结束）在转换为 符号
                num = num + c;
            } else if (isSymbol(c)) {
                //遇到符号，赋值符号
                symbol = symbol + c;

                //将数字解析后放入 数字栈，并初始化 num局部变量，以便记录下一个数字
                if (!"".equals(num)){
                    numStack.push(Integer.parseInt(num));
                    num = "";
                }

                //将符号 压入符号栈（需要判断服 符号的 优先级）
                symbolPush(c, numStack, symbolStack);
                symbol = "";

                /**
                 * 增加 对 （） 的处理
                 */
            }else if ( isParenthesesLeft(c) ){
                //左括号直接入栈
                symbolStack.push(c);

            }else if ( isParenthesesRight(c) ){

                numStack.push(Integer.parseInt(num));
                num = "";

                //右括号 这个字符不用操作，但是要不断弹栈，计算，直到弹出上一个’（‘,
                //即 计算完这个小括号
                while ( !isParenthesesLeft(symbolStack.peek()) ){
                    //弹俩数 一个符号，计算。 结果压入数字栈。
                    int num1 = numStack.pop();
                    int num2 = numStack.pop();
                    int popSymbol = symbolStack.pop();
                    int calculate = calculate(num1, num2, popSymbol);
                    numStack.push(calculate);

                }
                //左括号 刚才只peek，未取出。  取出扔掉
                symbolStack.pop();

            }



            //最后一个数字(num拼接完了，直接放入 数字栈)
            if( i == waitCal.length()-1 && isNum(c)){
                //将数字解析后放入 数字栈，并初始化 num局部变量，以便记录下一个数字
                numStack.push(Integer.parseInt(num));
                num = "";
            }
        }

        //二、弹栈计算
        //  符号栈没空就计算
        while (!symbolStack.isEmpty()){
            int num1 = numStack.pop();
            int num2 = numStack.pop();
            int popSymbol = symbolStack.pop();
            int calculate = calculate(num1, num2, popSymbol);
            numStack.push(calculate);
        }
        //符号栈弹空以后， 数字栈中的数字为 结果
        return numStack.pop();
    }


    /**
     * @param c
     * @param numStack
     * @param symbolStack
     */
    private static void symbolPush(char c, ArrayStack<Integer> numStack, ArrayStack<Character> symbolStack) {
        // 判断符号栈是否为空，空则可以 push
        if (symbolStack.isEmpty()) {
            symbolStack.push(c);
            return ;
        }

        // 查看符号栈顶元素
        int topVal = symbolStack.peek();
        //获取优先级
        int priorityPeek = getPriority((char) topVal);
        int priorityC = getPriority(c);

        //优先级高于等于 栈顶才能 push
        /**
         * 由于默认 优先级返回-1 ，所以’（‘可以使计算停止。 从而正常放入符号。
         */
        if (priorityC >= priorityPeek){
            symbolStack.push(c);
            //否则，弹出数字计算，压入数字栈，在尝试压入符号栈（递归：调用自己）
        }else {
            int num1 = numStack.pop();
            int num2 = numStack.pop();
            int symbolTop = symbolStack.pop();
            int result = calculate(num1,num2,symbolTop);
            numStack.push(result);
            //递归
            symbolPush(c,numStack,symbolStack);
        }
    }

    /**
     * 注意数字弹栈顺序：
     * 根据符号数字计算  a symbol b = result
     * @param num1  b
     * @param num2  a
     * @param symbolTop symbol
     * @return result
     */
    private static int calculate(int num1, int num2, int symbolTop) {
        //也可以
        char symbol = (char)symbolTop;
        return switch (symbol) {
            case '+' -> num2 + num1;
            case '-' -> num2 - num1;
            case '*' -> num2 * num1;
            case '/' -> num2 / num1;
            default -> throw new RuntimeException("error symbol");
        };
    }

    private static int getPriority(char topVal) {
        return switch (topVal) {
            case '+', '-' -> 0;
            case '*', '/' -> 1;
            default -> -1;
        };
    }


    private static boolean isSymbol(char c) {
        return switch (c) {
            case '+', '-', '*', '/' -> true;
            default -> false;
        };
    }

    private static boolean isNum(char c) {
        //return c >= 48 && c <= 57;
        return c >= '0' && c <= '9';
    }

    private static boolean isParenthesesLeft(char c) {
        return c == '(';
    }

    private static boolean isParenthesesRight(char c) {
        return c == ')';
    }



}

测试：

package com.example.stack.basic;

import com.example.stack.improve.ImproveCalculate;

public class Test {

    public static void main(String[] args) {

        // 测试例子：
        String waitCal = "3+2*2+13";

        int result = Calculate.calculate(waitCal);

        System.out.printf("%s=%d\n",waitCal,result);

        // 测试例子：
        String waitCal2 = "3+2*(2+5*5)*2+13";

        //使用 新的 cal
        int result2 = ImproveCalculate.calculate(waitCal2);

        System.out.printf("%s=%d\n",waitCal2,result2);

    }

}

//结果：
3+2*2+13=20
3+2*(2+5*5)*2+13=124