【数据结构与算法】stack栈的介绍和实现、使用栈来实现中缀表达式求值

1. 栈的介绍

栈是一个先入后出的有序列表。允许插入(入栈push)和删除(出栈pop)的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)

2. 栈的应用场景

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

3. 栈的实现

使用数组模拟栈的使用，思路如下：

1. 定义一个top来表示栈顶，初始化为-1
2. 当有数据加入到栈时，top++，stack[top] = 数据
3. 当从栈中取出数据时，int value = stack[top]，top–

实现如下：

import java.util.Scanner;

public class ArrayStackDemo {

    public static void main(String[] args) {
        ArrayStack stack = new ArrayStack(3);
        String key = "";
        Scanner scanner = new Scanner(System.in);
        boolean loop = true;

        System.out.println("show: 表示显示栈");
        System.out.println("exit: 退出程序");
        System.out.println("push: 表示入栈");
        System.out.println("pop: 表示出栈");
        System.out.println("请输入你的选择：");

        while (loop) {
            key = scanner.next();
            switch (key) {
                case "show":
                    stack.show();
                    break;
                case "push":
                    System.out.println("请输入一个数");
                    int inputData = scanner.nextInt();
                    stack.push(inputData);
                    break;
                case "pop":
                    try {
                        int outData = stack.pop();
                        System.out.printf("出栈的数据是%d\n", outData);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case "exit":
                    scanner.close();
                    loop = false;
                    System.out.println("程序退出");
                    break;
                default:
                    break;
            }
        }

    }

}

// 用数组实现的栈
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 this.top == this.maxSize - 1;
    }

    // 判断栈是否空的
    public boolean isEmpty() {
        return this.top == -1;
    }

    // 入栈push
    public void push(int data) {
        // 先判断栈是否满了
        if (this.isFull()) {
            System.out.println("栈满了");
            return;
        }
        this.top++;
        this.stack[this.top] = data;
    }

    // 出栈pop
    public int pop() {
        // 先判断栈是否空
        if (this.isEmpty()) {
            throw new RuntimeException("栈空");
        }
        int data = this.stack[this.top];
        this.top--;
        return data;
    }

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

}

运行程序，结果如下：

show: 表示显示栈
exit: 退出程序
push: 表示入栈
pop: 表示出栈
请输入你的选择：
push
请输入一个数
10
show
stack[0]=10
pop
出栈的数据是10
exit
程序退出

4. 使用栈实现中缀表达式的转换与求值

需求说明：输入一个字符串的表达式，如7*2*2-5+1-5+3-4，我们需要对这个字符串的表达式进行转换，然后求值。这个时候就可以使用栈解决。目前只处理+、-、*、/四个运算符，且字符串表达式不包含空格

使用栈完成表达式计算的思路：

1. 通过一个index索引值，来遍历我们的表达式
2. 如果是一个数字，就直接入数栈
3. 如果是一个符号，情况如下：
   1. 如果当前的符号栈为空，就直接入符号栈
   2. 如果符号栈有运算符，就进行运算符优先级的比较。如果当前运算符的优先级小于或等于栈中的运算符，就需要从数栈中pop出两个数，再从符号栈中pop出一个符号，进行计算，再将计算的结果入数栈，然后将当前的运算符入符号栈；如果当前的运算符的优先级大于栈中的运算符，就直接入符号栈
4. 当遍历完表达式，就顺序的从数栈和符号栈中pop出相应的数和符号，并进行计算
5. 最后在数栈只有一个数字，就是表达式的结果

实现如下：

public class StackExpressionCalculator {

    public static void main(String[] args) {
        String expression = "7*2*2-5+1-5+3-4";

        // 创建数栈和符号栈
        ArrayStack numberStack = new ArrayStack(10);
        ArrayStack operatorStack = new ArrayStack(10);

        // 定义计算的相关变量
        int index = 0;
        char tmpChar = ' ';    // 临时储存遍历的字符
        String concatNumber = "";   // 用于拼接多位数字
        int number1 = 0;
        int number2 = 0;
        char operator = ' ';
        int result = 0;

        while (true) {
            tmpChar = expression.charAt(index);

            if (operatorStack.isOperator(tmpChar)) {
                if (!operatorStack.isEmpty()) {
                    // 数字0对应char为49
                    if (operatorStack.priority(tmpChar) = 0; i--) {
            System.out.printf("stack[%d]=%d\n", i, this.stack[i]);
        }
    }

    // 返回栈顶的值(非pop)
    public int getTop() {
        return this.stack[this.top];
    }


    // 计算运算符的优先级，优先级用数字表示，数字越大，优先级越高
    public int priority(char operator) {
        if (operator == '*' || operator == '/') {
            return 1;
        } else if (operator == '+' || operator == '-') {
            return 0;
        } else {
            return -1;
        }
    }

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


    // 用运算符对数字进行计算
    public int calculate(int number1, int number2, char operator) {
        int result = 0;
        switch (operator) {
            case '+':
                result = number1 + number2;
                break;
            case '-':
                // 注意相减的顺序
                result = number2 - number1;
                break;
            case '*':
                result = number1 * number2;
                break;
            case '/':
                result = number2 / number1;
                break;
            default:
                break;
        }
        return result;
    }

}

运算程序，结果如下：

表达式: 7*2*2-5+1-5+3-4 = 18

如果计算722-5*1-5+3-4，因为连续出现两个减，所有计算结果错误，正常的结果为17，而此次的计算结果为29。连续出现两个除也会出错。可以使用逆波兰表达式进行解决，参考数据结构与算法之使用栈Stack来实现逆波兰表达式求值