Code More Create

Appearance

Return to top
On this page

栈

基本介绍（stack）

  • 先进后出
  • 插入/删除只能在线性表的同一端进行
  • 栈顶：允许插入和删除的一端，栈底：另一端

应用场景

  • 子程序的调用
    • 在调往子程序之前，先将下一个指令的地址存到堆栈中，直到子程序执行完再将地址取出，以回到原来的程序中
  • 处理递归调用
    • 与子程序调用类似，将下一指令的地址、参数、区域变量等数据存入堆栈中。
  • 表达式的转换【中缀表达式转后缀表达式】与求值（实际解决）
  • 二叉树的遍历
  • 图形的深度优先算法

思路分析

  1. 数组模拟栈
  2. 定义top来表示栈顶，初始化为-1
  3. 入栈，当有数据加入到栈时，top++，stack[top] = data
  4. 出栈，value = stack[top]；top--；return value

代码实现 

class ArrayStack {
    private final int maxSize; //栈的大小
    private final int[] stack; //存储数据
    private int top = -1; //栈顶

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

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

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

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

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("栈空");
        }
        return stack[top--];
    }

    public void list() {
        if (isEmpty()) {
            System.out.println("栈空");
            return;
        }
        for (int i = top; i >= 0; i--) {
            System.out.printf("%d\t", stack[i]);
        }
        System.out.println();
    }
}

拓展

完成表达式计算(中缀表达式)

  • 通过index来遍历我们的表达式
  • 发现是一个数字，直接进数栈
  • 发现是符号
    • 符号栈为空，直接进栈
    • 符号栈不为空
      • 如果当前操作符的优先级小于或等于栈中的操作符，则pop出两个数和一个符号，计算，将结果和当前的操作符压入栈
      • 反之直接入栈
  • 当表达式扫描完毕，顺序的从数栈和符号栈中pop出数据，并运行。
  • 最后在数栈只有一个数字，就是表达式的结果

存在问题

  • 多位数计算
  • 小括号
public static void main(String[] args) {
    String expression = "3+2*5-4";
    CalculatorStack numStack = new CalculatorStack(10);
    CalculatorStack operaStack = new CalculatorStack(10);
    int index = 0; //扫描
    int num1 = 0;
    int num2 = 0;
    int operator = ' ';
    int res = 0;
    char ch = ' '; //每次扫描的结果

    //扫描表达式
    while (true) {
        ch = expression.substring(index, index + 1).charAt(0);
        if (operaStack.isOperator(ch)) {
            if (!operaStack.isEmpty()) {
                if (operaStack.priority(operaStack.getTop()) >= operaStack.priority(ch)) {
                    num1 = numStack.pop();
                    num2 = numStack.pop();
                    operator = operaStack.pop();
                    res = operaStack.cal(num1, num2, (char) operator);
                    numStack.push(res);
                }
                operaStack.push(ch);
            } else {
                operaStack.push(ch);
            }
        } else {
            keepNum += ch;

                if (index == expression.length() - 1) {
                    numStack.push(ch - 48);
                } else {
                    if (operaStack.isOperator(expression.substring(index + 1, index + 2).charAt(0))) {
                        numStack.push(Integer.parseInt(keepNum));
                        keepNum = "";
                    }
                }
        }
        index++;
        if (index >= expression.length()) {
            break;
        }
    }

    //计算表达式
    while (true) {
        if (operaStack.isEmpty()) {
            break;
        }
        num1 = numStack.pop();
        num2 = numStack.pop();
        operator = operaStack.pop();
        res = operaStack.cal(num1, num2, (char) operator);
        numStack.push(res);
    }
    System.out.printf(expression + " = " + numStack.pop());
}

class CalculatorStack {
    private final int maxSize; //栈的大小
    private final int[] stack; //存储数据
    private int top = -1; //栈顶

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

    public int priority(char operator) {
        if (operator == '*' || operator == '/') {
            return 1;
        } else if (operator == '+' || operator == '/') {
            return 0;
        } else {
            return -1;
        }
    }

    //是否是操作符
    public boolean isOperator(int val) {
        return val == '+' || val == '-' || val == '*' || val == '/';
    }

    //计算方法
    public int cal(int num1, int num2, char operator) {
        int res = 0;
        switch (operator) {
            case '+':
                res = num1 + num2;
                break;
            case '-':
                res = num2 - num1; //注意数据
                break;
            case '*':
                res = num1 * num2;
                break;
            case '/':
                res = num2 / num1;//注意顺序
                break;
            default:
                break;
        }
        return res;
    }

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

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

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

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("栈空");
        }
        return stack[top--];
    }

    public char getTop() {
        return (char) stack[top];
    }

    public void list() {
        if (isEmpty()) {
            System.out.println("栈空");
            return;
        }
        for (int i = top; i >= 0; i--) {
            System.out.printf("%d\t", stack[i]);
        }
        System.out.println();
    }
}

前缀表达式

计算机 从右到左，将数字压入栈，遇到运算符时，弹出栈顶和次顶元素，计算结果，重新入栈，重复过程。

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

从左到右，遇到数字，压入栈，遇到运算符，弹出栈顶和次顶元素，计算结果，重复过程。

后缀表达式计算 

public class PolandNotation {
    public static void main(String[] args) {
        String suffixExpression = "30 4 + 5 * 6 -";
        List<String> list = getListString(suffixExpression);
        int res = calculator(list);
        System.out.println(res);
    }

    public static List<String> getListString(String suffixExpression) {
        String[] split = suffixExpression.split(" ");
        List<String> list = new ArrayList<>();
        for (String ele : split) {
            list.add(ele);
        }
        return list;
    }

    public static int calculator(List<String> list) {
        Stack<String> stack = new Stack<>();
        for (String e : list) {
            if (e.matches("\\d+")) {
                //匹配多位数
                stack.push(e);
            } else {
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int res = 0;
                if (e.equals("+")) {
                    res = num1 + num2;
                } else if (e.equals("-")) {
                    res = num1 - num2;
                } else if (e.equals("*")) {
                    res = num1 * num2;
                } else if (e.equals("/")) {
                    res = num1 / num2;
                } else {
                    throw new RuntimeException("运算符有误");
                }
                stack.push("" + res);
            }
        }
        return Integer.parseInt(stack.pop());
    }
}

中缀表达式转后缀表达式

  • 使用两个栈，运算符栈s1 和 存储中间结果的栈s2
  • 从左到右扫描中缀表达式
  • 遇到操作数，压入s2
  • 遇到运算符，比较和s1栈顶的优先级
    • 如果s1为空或者为左括号，直接入栈
    • 优先级比栈顶高，入栈
    • 优先级比栈顶低，弹出，压入s2，随后继续比较新的栈顶
  • 遇到括号时
    • 左括号，直接压入s1
    • 右括号，依次弹出s1栈顶，压入s2，知道遇到左括号，括号不入栈
  • 继续扫描，直到表达式的最右边
  • 将s1中剩余的运算符弹出，并压入s2
  • 依次弹出s2输出，结果的逆序就是中缀转后缀的结果
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class PolandNotation {
    public static void main(String[] args) {
        List<String> InfixExpressList = toInfixExpression("1+((2+5)*6+1)*4");
        System.out.println(InfixExpressList);
        List<String> parseSuffixExpression = parseSuffixExpressList(InfixExpressList);
        System.out.println(parseSuffixExpression);
        System.out.println(calculator(parseSuffixExpression));
    }
  
  //转化为中缀数组
    public static List<String> toInfixExpression(String s) {
        List<String> list = new ArrayList<>();
        int i = 0; // 指针
        String str; //对多位数拼接
        char c;
        do {
            //不是数字
            if (!isNumber(c = s.charAt(i))) {
                list.add(c + "");
                i++;
            } else {
                //数字
                str = "";
                while (i < s.length() && isNumber(c = s.charAt(i))) {
                    str += c;
                    i++;
                }
                list.add(str);
            }
        } while (i < s.length());
        return list;
    }

    public static boolean isNumber(char ch) {
        return ch >= 48 && ch <= 57;
    }

    public static List<String> getListString(String suffixExpression) {
        String[] split = suffixExpression.split(" ");
        List<String> list = new ArrayList<>();
        for (String ele : split) {
            list.add(ele);
        }
        return list;
    }
   //计算后缀数组
    public static int calculator(List<String> list) {
        Stack<String> stack = new Stack<>();
        for (String e : list) {
            if (e.matches("\\d+")) {
                //匹配多位数
                stack.push(e);
            } else {
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int res = 0;
                if (e.equals("+")) {
                    res = num1 + num2;
                } else if (e.equals("-")) {
                    res = num1 - num2;
                } else if (e.equals("*")) {
                    res = num1 * num2;
                } else if (e.equals("/")) {
                    res = num1 / num2;
                } else {
                    throw new RuntimeException("运算符有误");
                }
                stack.push("" + res);
            }
        }
        return Integer.parseInt(stack.pop());
    }

    public static int priority(char operator) {
        if (operator == '*' || operator == '/') {
            return 1;
        } else if (operator == '+' || operator == '-') {
            return 0;
        } else {
            return -1;
        }
    }

  //中缀转化后缀数组
    public static List<String> parseSuffixExpressList(List<String> list) {
        Stack<String> stack1 = new Stack<>();
        //因为整个过程中 s2没有pop操作，而且后续需要对其逆序输出，所以我们不用stack,直接使用list
        List<String> stack2 = new ArrayList<>();
        char c;
        for (String e : list) {
            if (e.matches("\\d+")) {
                //数字
                stack2.add(e);
            } else if (e.equals("(")) {
                //左括号
                stack1.push(e);
            } else if (e.equals(")")) {
                //右括号
                while (!stack1.peek().equals("(")) {
                    stack2.add(stack1.pop());
                }
                stack1.pop(); //消除“（”
            } else {
                //普通符号
                while (stack1.size() != 0 && priority(e.charAt(0)) <= priority(stack1.peek().charAt(0))) {
                    stack2.add(stack1.pop());
                }
                stack1.push(e);
            }
        }
        //将s1剩余的符号依次弹出压入s2
        while (stack1.size() != 0) {
            stack2.add(stack1.pop());
        }
        return stack2;
    }
}