THIS IS B3c0me

记录生活中的点点滴滴

0%

栈

发表于 更新于 分类于

1.Java数组模拟栈

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
package com.datastructure.stack;

import java.util.Scanner;

public class StackTest {
    //测试
    public static void main(String[] args) {
        Stack stack = new Stack(10);
        String key = "";
        boolean loop = true;//控制是否退出菜单
        Scanner scanner = new Scanner(System.in);
        while(loop){
            System.out.println("show:表示显示栈");
            System.out.println("push:表示压入栈");
            System.out.println("pop:表示出栈");
            System.out.println("exit:退出程序");
            System.out.println("请输入你的选择");
            key = scanner.next();
            switch(key){
                case "show":
                    stack.showStack();
                    break;
                case "push":
                    System.out.println("请输入一个要入栈的数：");
                    int num = scanner.nextInt();
                    stack.push(num);
                    System.out.println("入栈成功！");
                    break;
                case "pop":
                    System.out.println("出栈的数据是：" + stack.pop());
                    break;
                case "exit":
                    loop = false;
                    break;
                default:
                    System.out.println("输入格式不正确！");
                    break;
            }
        }
    }
}

class Stack {
    private int maxSize;
    private int[] stack;//数组模拟栈
    private int top = -1;//栈顶，初始化为-1

    //构造器
    public Stack(int maxSize){
        this.maxSize = maxSize;
        stack = new int[this.maxSize];
    }

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

    //判断栈空
    public boolean isEmpty(){
        return top == -1;
    }

    //入栈
    public void push(int value){
        //先判断是否满
        if(isFull()){
            return ;
        }
        top++;
        stack[top] = value;
    }
    //出栈
    public int pop(){
        if(isEmpty()){
            System.out.println("栈空");
            return -1;
        }
        int value = stack[top];
        top--;
        return value;
    }
    //遍历栈,需要从栈顶开始显示
    public void showStack(){
        if(isEmpty()){
            System.out.println("没有数据");
            return;
        }
        for(int i = top; i >= 0; i--){
            System.out.printf("stack[%d]=%d\n",i,stack[i]);
        }
    }
}

2.栈实现综合计算器

  • 思路分析：
    1. 通过一个index值遍历表达式
    2. 如果发现index扫描到的是一个数字，将该数字入数栈
    3. 如果Index扫描到的是一个符号：
      1. 如果当前符号栈为空，直接入符号栈
      2. 如果符号栈中有操作符，进行比较：
        1. 如果当前符号的优先级低于或等于栈中的操作符：
          1. 从数据栈中pop出两个数
          2. 从符号栈中pop出一个符号
          3. 进行运算，将得到的结果存入数栈
          4. 把当前的符号入符号栈
        2. 如果当前符号优先级高于符号栈中的符号，直接入符号栈
    4. 当表达式扫描完毕，顺序地从数栈和符号栈中pop出相应的数和符号进行运算
    5. 最后的数栈中只有一个数字，就是表达式的结果
  • 代码实现
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
package com.datastructure.stack;

import java.util.Scanner;

public class StackCalculator {
    public static void main(String[] args) {
        //要计算的表达式
        String expression = "";
        Scanner scanner = new Scanner(System.in);
        expression=scanner.nextLine();
        //创建两个栈，数栈和符号栈
        Stackk nStackk = new Stackk(20);
        Stackk oStackk = new Stackk(10);
        //扫描表达式
        int index = 0;
        int num1 = 0;
        int num2 = 0;
        int oper = 0;
        int res = 0;
        char ch =' ';//将每次扫描到的char保存到ch
        String keepNum = "";
        //开始循环扫描
        while(true){
            //依次得到expression的每个字符
            ch = expression.substring(index,index+1).charAt(0);
            //判断ch是什么类型，然后做相应的处理
            if(oStackk.isOper(ch)){//如果是运算符
                //判断当前栈是否为空
                if(!oStackk.isEmpty()){
                    //比较运算符优先级
                    if(oStackk.priority(ch) <= oStackk.priority(oStackk.top())){
                        num2 = nStackk.pop();
                        num1 = nStackk.pop();
                        oper = oStackk.pop();
                        res = nStackk.cal(num1,num2,oper);
                        //把运算的结果存入到数栈
                        nStackk.push(res);
                        //把当前的符号入符号栈
                        oStackk.push(ch);
                    }else{
                        oStackk.push(ch);
                    }
                }else{
                    //直接入栈
                    oStackk.push(ch);
                }

            }else {//如果是数字则直接入栈
                //当处理多位数是，不能发现是一个数字就立即入栈，因为它可能是多位数
                //在处理数是需要向expression的表达式的Index后再看一位，如果是数就继续进行扫描，如果是符号则将当前数入栈
                //因此要定义一个字符串变量用于拼接
                keepNum += ch;
                //如果ch已经是expression的最后一位，则不需要判断
                if (index == expression.length() - 1) {
                    nStackk.push(Integer.parseInt(keepNum));
                } else {
                    //判断下一个字符是否是数字,如果是则继续进行扫描，如果是运算符则入栈
                    if (oStackk.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
                        //如果后一位是运算符，则入栈
                        nStackk.push(Integer.parseInt(keepNum));
                        /////重要！！！！清空keepNum;
                        keepNum = "";
                    }
                }
            }
            //让index+1,并判断是否扫描到expressin的最后
            index++;
            if(index >= expression.length()){
                break;
            }
        }
        //扫描完毕，顺序地从数栈和符号栈中pop出相应的数字和符号，并运行
        while(true){
            //如果符号栈为空，则计算结束,最后的结果是数栈中只有一个数字
            if(oStackk.isEmpty()){
                break;
            } else {
                num2 = nStackk.pop();
                num1 = nStackk.pop();
                oper = oStackk.pop();
                res = nStackk.cal(num1, num2, oper);
                nStackk.push(res);

            }
        }
        System.out.println("最后的计算结果为：" + expression + "=" + nStackk.pop());
    }


}

//创建一个栈，直接使用前面创建好的栈
//需要扩展功能
class Stackk {
    private int maxSize;
    private int[] stack;//数组模拟栈
    private int top = -1;//栈顶，初始化为-1

    //构造器
    public Stackk(int maxSize){
        this.maxSize = maxSize;
        stack = new int[this.maxSize];
    }

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

    //判断栈空
    public boolean isEmpty(){
        return top == -1;
    }

    //入栈
    public void push(int value){
        //先判断是否满
        if(isFull()){
            return ;
        }
        top++;
        stack[top] = value;
    }
    //出栈
    public int pop(){
        if(isEmpty()){
            System.out.println("栈空");
            return -1;
        }
        int value = stack[top];
        top--;
        return value;
    }
    //查看栈顶的元素但不出栈
    public int top(){
        int value = stack[top];
        return value;
    }
    //遍历栈,需要从栈顶开始显示
    public void showStack(){
        if(isEmpty()){
            System.out.println("没有数据");
            return;
        }
        for(int i = top; i >= 0; i--){
            System.out.printf("stack[%d]=%d\n",i,stack[i]);
        }
    }
    //返回运算符的优先级,使用数字表示，数字越大则优先级越高
    public int priority(int oper){
        if(oper == '*' || oper == '/'){
            return 1;
        }
        else if(oper == '+' || oper == '-'){
            return 0;
        }
        else{
            return -1;//嘉定目前的表达式只有+-*/
        }
    }
    //判断是不是一个运算符
    public boolean isOper(char val){
        return val == '+' || val == '-' || val == '*' || val == '/';
    }

    //计算方法
    public int cal(int num1,int num2,int oper){
        int res = 0;//用于存放计算的结果
        switch(oper){
            case '+':
                res = num1 + num2;
                break;
            case '-':
                res = num1 - num2;
                break;
            case '*':
                res = num1 * num2;
                break;
            case '/':
                res = num1 / num2;
                break;
            default:
                break;
        }
        return res;
    }
}

3.前缀、中缀、后缀表达式

3.1 前缀表达式

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

  • 前缀表达式的计算机求值：
    • 从右至左扫描表达式，遇到数字时将数字压入栈遇到运算符时弹出栈顶的两个数，用运算符对他们做相应的计算，将结果入栈，重复上述操作直到表达式最左端，最后运算得出的值即为表达式的结果
3.2 中缀表达式

中缀表达式就是我们常见的数字和运算符结合在一起的表达式

  • 求值：
    • 在计算结果时往往会将中缀表达式转成其他表达式来操作（一般转成后缀表达式）
3.3 后缀表达式

也称逆波兰表达式，与前缀表达式相似，运算符位于操作数字后面

如(3+4)x5-6的后缀表达式为：34+5*6-

  • 计算机求值：
    • 从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对他们做出相应的计算，并将结果入栈，重复上升哦成直到表达式的最右端

4.逆波兰计算器的实现

4.1 实现思路：
4.2 代码实现：

5.中缀表达式转后缀表达式

5.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中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
5.2 代码实现

欢迎关注我的其它发布渠道