基于数组实现栈，再基于栈实现后缀表达式计算

简单来讲，后缀表达式的计算就是从左到右扫描表达式，遇到数字就将其压入栈，遇到操作符表示可以计算，这时取出栈顶的两个元素进行操作，然后再次将结果压入栈，最后栈里会留下一个元素，该元素就是运行结果（详解看图）

基于数组的栈实现
Stack

/**
 * @description:
 * @author: Czw
 * @create: 2022-10-24 19:19
 **/
public interface Stack<E> {
    //判断栈是否为空
    public boolean empty();

    //返回栈中元素数量
    public int size();

    //压栈容
    public void push(E item);

    //弹栈
    public E pop();

    //查看栈顶(不弹栈)
    public E peek();
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

MyArrayStack

/**
 * @description:
 * @author: Czw
 * @create: 2022-10-25 20:00
 **/
public class MyArrayStack<E> implements Stack<E> {
    private int size;
    private E[] data;
    private int top;

    private static final int DEFAULT_CAPACITY = 10;

    public MyArrayStack() {
        this.size = 0;
        this.top = -1;
        this.data = (E[]) new Object[DEFAULT_CAPACITY];
    }


    @Override
    public boolean empty() {
        return size == 0;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public void push(E item) {
        if (top == -1) {
            top = 0;
            data[0] = item;
        } else {
            if (size == data.length) {
                grow(data.length * 2);
            }
            data[++top] = item;
        }
        size++;

    }

    private void grow(int i) {

    }

    @Override
    public E pop() {
        E result = data[top--];
        size--;
        return result;
    }

    @Override
    public E peek() {
        return data[top];
    }

    public static void main(String[] args) {
        Stack<Integer> mas = new MyArrayStack<>();
        for (int i = 0; i < 10; i++) {
            mas.push(i);
        }

        int size = mas.size();
        for (int i = 0; i < size; i++) {
            System.out.println(mas.pop());
            ;
        }

    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

后缀表达式

/**
 * 后缀表达式，例如：13+2*45*-
 *
 * @author: Czw
 * @create: 2022-10-29 13:38
 **/
public class PostfixExpression {
    public static void main(String[] args) {
        //后缀表达式，13+2*45*-
        String postfixExpression = "13+2*45*-";
        Stack<Integer> stack = new MyArrayStack<>();
        for (int i = 0; i < postfixExpression.length(); i++) {
            char ss = postfixExpression.charAt(i);
            if (Character.isDigit(ss)) {
                stack.push(Integer.valueOf(String.valueOf(ss)));
            } else {
                Integer p1 = stack.pop();
                Integer p2 = stack.pop();
                switch (String.valueOf(ss)) {
                    case "+":
                        Integer p = p1 + p2;
                        stack.push(p);
                        break;
                    case "-":
                        Integer p3 = p2 - p1;
                        stack.push(p3);
                        break;
                    case "*":
                        Integer p4 = p1 * p2;
                        stack.push(p4);
                        break;
                    default:
                        System.out.println("运算符不存在");
                }
            }
        }
        System.out.println(stack.pop());

    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42