数据结构中,针对线性表包含两种结构,一种是顺序线性表,一种是链表。顺序线性表适用于查询,时间复杂度为O(1),增删的时间复杂度为O(n).链表适用于增删,时间复杂度为O(1),查询的时间复杂度为O(n).
栈可以说是特殊的线性表,因为栈拥有线性表的基础特征基础上,有一些特殊的要求,比如后进先出,即每次插入的元素只能放在栈顶,每次弹出值也只能弹出栈顶。同样的,栈分成顺序栈和链栈。本篇内容为顺序栈的实现以及简单应用。
顺序栈可以应用到很多的地方,比如递归运算,语法检查(比如括号匹配问题),数值转换(十进制转换成其他进制),四则运算等等。
栈在java中有现有的封装的类,但是在apex中貌似没有已经封装的类,我们可以针对其功能进行自行的封装。顺序栈是顺序线性表的特殊情况,所以说实现上可以使用数组来实现。
一.顺序栈的实现
针对栈的类应该有以下的构造函数及方法:
1.构造函数:设计成了三种,无参设置默认长度,传入默认长度,以及传默认长度并且指定此栈为固定长度还是动态扩展;
2.empty:判断此栈是否为空栈;
3.peek:返回栈顶元素,栈顶元素指针不减一;
4.push:入栈,栈顶元素指针加一;
5.pop:出栈,栈顶元素减一;
6.search:搜索obj在栈的位置,大于0说明存在;
7.toString:重写stack默认返回的内容。
顺序栈类应该还有其他的方法,比如destroy等,有兴趣的可以自行填充。
Stack类的代码设计如下:
1 public without sharing class Stack {
2
3 //数据集
4 private Object[] datas{get;set;}
5 //栈最大容量
6 private Integer maxSize{get;set;}
7 //栈顶指针
8 private Integer topIndex{get;set;}
9 //是否允许动态扩展栈的容量
10 private Boolean allowExtension{get;set;}
11 //默认扩展容量大小
12 private final Integer DEFAULT_EXTENSION_SIZE = 5;
13
14 public Stack() {
15 this(5);
16 }
17
18 public Stack(Integer stackSize) {
19 this(stackSize,false);
20 }
21
22 public Stack(Integer stackSize,Boolean allowStackExtension) {
23 if(stackSize > 0) {
24 datas = new Object[stackSize];
25 maxSize = stackSize;
26 topIndex = -1;
27 allowExtension = allowStackExtension;
28 } else {
29 //TODO throw exception
30 //栈容量必须大于0
31 throw new StackException('栈容量必须大于0');
32 }
33 }
34
35 public Boolean empty() {
36 return topIndex == -1 ? true : false;
37 }
38
39 public Object peek() {
40 if(topIndex == -1) {
41 //TODO throw exception
42 //空栈无法获取栈顶值
43 throw new StackException('空栈无法获取栈顶值');
44 }
45 return datas[topIndex];
46 }
47
48 public Object push(Object obj) {
49 if(topIndex == maxSize - 1) {
50 if(allowExtension) {
51 datas = copyOf(maxSize + DEFAULT_EXTENSION_SIZE);
52 } else {
53 //TODO 栈已满,无法入栈
54 throw new StackException('栈已满,无法入栈');
55 }
56 }
57 datas[++topIndex] = obj;
58 return obj;
59 }
60
61 public Object pop() {
62 if(topIndex == -1) {
63 //TODO 空栈,无法出栈
64 throw new StackException('空栈无法获取栈顶值');
65 }
66
67 Object popObj = datas[topIndex];
68 datas[topIndex] = null;
69 topIndex -=1;
70 return popObj;
71 }
72
73 public Integer search(Object obj) {
74 Integer i=topIndex;
75 while(i != -1){
76 if(datas[i] != obj) {
77 i--;
78 } else {
79 break;
80 }
81 }
82 return i + 1;
83 }
84
85 private Object[] copyOf(Integer newStackSize) {
86 Object[] tempObjs = new Object[newStackSize];
87 for(Integer i = 0;i < datas.size();i++) {
88 tempObjs[i] = datas[i];
89 }
90 return tempObjs;
91 }
92
93 override public String toString() {
94 List<Object> objs = new List<Object>();
95 for(Object obj : datas) {
96 if(obj != null) {
97 objs.add(obj);
98 }
99 }
100 return String.valueOf(objs);
101 }
102
103
104 public class StackException extends Exception{
105
106 }
107 }
二.顺序栈的简单应用
顺序栈可以应用到很多场景,demo来一个简单的四则运算。此四则运算考虑的东西比较少,没有对细节进行完善,目前仅支持 + - * / 以及整数的操作,返回的结果为double类型的值。
来一个简单的四则运算的例子:1 + 2 + 3 * 4 - 8 / 5 * 2 + 3 - 1
此表达式为中缀表示法--运算符均在数字中间。我们需要以一定的规则转换成后缀表达式,这便用到了栈的知识。
1).中缀表达式转换成后缀表达式
中缀表达式转换成后缀表达式规则为将运算符放在空栈里面:
1.当栈为空情况下,第一个运算符入栈;
2.当前的运算符优先级如果比栈顶元素高,则入栈;
3.当前的运算符如果比栈顶元素低,则将栈中从栈顶开始所有连续的高于当前运算符的元素出栈,然后将当前运算符入栈;
4.当表达式结束后,将栈中所有的元素弹出。
原始表达式:1 + 2 + 3 * 4 - 8 / 5 * 2 + 3 - 1
第一轮:1是数字,所以不进入栈,直接弹出; 内容1
第二轮:+是运算符,因为栈为空,所以直接入栈 内容1 栈:+
第三轮:2是数字,所以不进入栈,直接弹出; 内容1 2 栈: +
第四轮:+是运算符,优先级不如栈顶元素,将栈顶元素+弹出,并将当前的+入栈 内容1 2 + 栈:+
第五轮:3是数字,不进入栈,直接弹出 内容1 2 + 3 栈:+
第六轮:*是运算符,因为优先级比栈顶元素+高,所以入栈 内容1 2 + 3 栈:+ *
第七轮:4是数字,不进入栈,直接弹出 内容1 2 + 3 4 栈:+ *
第八轮:-是运算符,因为优先级比栈顶元素* 以及相邻元素+优先级低,所以* + 出栈,-入栈 内容1 2 + 3 4 * + 栈:-
第九轮:8是数字,不进入栈,直接弹出 内容1 2 + 3 4 * + 8 栈:-
第十轮:/是运算符,因为优先级比栈顶元素-高,所以入栈 内容1 2 + 3 4 * + 8 栈:- /
第十一轮:5是数字,不进入栈,直接弹出 内容1 2 + 3 4 * + 8 5 栈:- /
第十二轮:*是运算符,优先级比栈顶元素低,但是比-高,所以/出栈,*入栈 内容1 2 + 3 4 * + 8 5 / 栈:- *
第十三轮:2是数字,不进入栈,直接弹出 内容1 2 + 3 4 * + 8 5 / 2 栈:- *
第十四轮:+是运算符,优先级比* - 低,所以 * -出栈,+入栈 内容1 2 + 3 4 * + 8 5 / 2 * - 栈: +
第十五轮:3是数字,不进入栈,直接弹出 内容1 2 + 3 4 * + 8 5 / 2 * - 3 栈: +
第十六轮:-是运算符,优先级比+低,所以+出栈,-入栈 内容1 2 + 3 4 * + 8 5 / 2 * - 3 + 栈: -
第十七轮:1是数字,不进入栈,直接弹出 内容1 2 + 3 4 * + 8 5 / 2 * - 3 + 1 栈: -
第十八轮,表达式已结束,将栈所有元素弹出 内容1 2 + 3 4 * + 8 5 / 2 * - 3 + 1 -
所以此表达式转换成后缀表达式的结果为: 1 2 + 3 4 * + 8 5 / 2 * - 3 + 1 -
2)后栈表达式求结果
后栈表达式为运算符在数字的后面,规则为将数字放到栈里,遇到运算符则把栈顶的前两个元素拿出来进行运算,并把结果值放入栈顶,重复操作,直到表达式运算到最后,栈里只有一个值,即最终的结果。
原始表达式:1 2 + 3 4 * + 8 5 / 2 * - 3 + 1 -
第一轮:1是数字,当前栈为空栈,入栈 栈 : 1
第二轮:2是数字,入栈 栈:1 2
第三轮:+是运算符,弹出位于栈顶前两个内容进行相加,结果为3入栈 栈:3
第四轮:3是数字,入栈 栈:3 3
第四轮:4是数字,入栈 栈:3 3 4
第五轮:*是运算符,弹出位于栈顶前两个内容进行相乘,结果为12入栈 栈:3 12
第六轮:+是运算符,弹出位于栈顶前两个内容进行相加,结果为15入栈 栈:15
第七轮:8是数字,入栈 栈:15 8
第八轮:5是数字,入栈 栈: 15 8 5
第九轮:/是运算符,弹出位于栈顶前两个内容进行相除,结果为1.6入栈 栈:15 1.6
第十轮:2是数字,入栈 栈: 15 1.6 2
第十一轮:*是运算符,弹出位于栈顶前两个内容进行相乘,结果为3.2入栈 栈:15 3.2
第十二轮:-是运算符,弹出位于栈顶前两个内容进行相减,结果为11.8入栈 栈:11.8
第十三轮:3是数字,入栈 栈:11.8 3
第十四轮:+是运算符,弹出位于栈顶前两个内容进行相加,结果为14.8入栈 栈:14.8
第十五轮:1是数字,入栈 栈:14.8 1
第十六轮:-是运算符,弹出位于栈顶前两个内容进行相减,结果为15.8入栈 栈:13.8
运算结束,结果为13.8
代码实现:
1 public with sharing class MathUtil {
2
3 private static Set<String> symbolSet = new Set<String>{'+','-','*','/'};
4
5 private static Integer compareTo(String stackTopValue,String compareValue) {
6 Integer result;
7 if(stackTopValue == '+' || stackTopValue == '-') {
8 if(compareValue == '+' || compareValue == '-') {
9 result = -1;
10 } else if(compareValue == '*' || compareValue == '/') {
11 result = 1;
12 }
13 } else if(stackTopValue == '*' || stackTopValue == '/') {
14 return -1;
15 }
16 return result;
17 }
18
19 //将表达式从中缀表示法转换成后缀表示法
20 //eg : 1 + 2 + 3 * 4 - 10 / 5 * 2 + 3 - 1 ==> 1 2 + 3 4 * + 10 5 / 2 * - 3+ 1-
21 private static String transferToPostFixNotation(String inFixNotationContent) {
22 String result = '';
23 Stack symbolStack = new Stack(10,true);
24 Boolean previousCharacterIsNumric = true;
25 Integer[] chars = inFixNotationContent.getChars();
26 for(Integer charInteger : chars) {
27 String tempChar = String.fromCharArray(new List<Integer>{charInteger});
28
29 if(symbolSet.contains(tempChar)) {
30 if(symbolStack.empty()) {
31 symbolStack.push(tempChar);
32 } else {
33 String stackTopValue = (String)symbolStack.peek();
34 if(compareTo(stackTopValue,tempChar) > 0) {
35 symbolStack.push(tempChar);
36 } else {
37 Boolean enablePop = true;
38 //将所有栈中优先级比当前的符号高的出栈
39 while(enablePop) {
40 if(!symbolStack.empty()) {
41 String symbolStackPop = (String)symbolStack.peek();
42 if(compareTo(symbolStackPop,tempChar) < 0) {
43 symbolStackPop = (String)symbolStack.pop();
44 result += symbolStackPop;
45 } else {
46 enablePop = false;
47 }
48 } else {
49 enablePop = false;
50 }
51 }
52 symbolStack.push(tempChar);
53 }
54 }
55 } else if(tempChar.isWhitespace()) {
56 continue;
57 } else {
58 if(previousCharacterIsNumric) {
59 result += tempChar;
60 } else {
61 result += ' ' + tempChar;
62 }
63 }
64 if(tempChar.isNumeric() || tempChar == '.') {
65 previousCharacterIsNumric = true;
66 } else {
67 previousCharacterIsNumric = false;
68 }
69 }
70 while(!symbolStack.empty()) {
71 result += (String)symbolStack.pop();
72 }
73 return result;
74 }
75
76
77 public static Double calculate(String inFixNotationContent) {
78 String postFixNotationContent = transferToPostFixNotation(inFixNotationContent);
79 Stack numricStack = new Stack(10,true);
80 Integer[] chars = postFixNotationContent.getChars();
81 Boolean previousCharacterIsNumric = true;
82 for(Integer charInteger : chars) {
83 String character = String.fromCharArray(new List<Integer>{charInteger});
84 if(character.isNumeric()) {
85 if(!numricStack.empty()) {
86 if(previousCharacterIsNumric) {
87 character = (String)numricStack.pop() + character;
88 }
89 }
90 numricStack.push(character);
91 } else if(character == ' ') {
92 previousCharacterIsNumric = false;
93 continue;
94 } else if(symbolSet.contains(character)){
95 Double number1 = Double.valueOf(numricStack.pop());
96 Double number2 = Double.valueOf(numricStack.pop());
97 Double result;
98 if(character.equals('+')) {
99 result = number2 + number1;
100 } else if(character.equals('-')) {
101 result = number2 - number1;
102 } else if(character.equals('*')) {
103 result = number2 * number1;
104 } else if(character.equals('/')) {
105 result = number2 / number1;
106 }
107 numricStack.push(String.valueOf(result));
108 }
109 if(character.isNumeric()) {
110 previousCharacterIsNumric = true;
111 } else {
112 previousCharacterIsNumric = false;
113 }
114 }
115 String result = numricStack.toString().remove('(').remove(')');
116 return Double.valueOf(result);
117 }
118
119 }
执行结果:
String test = '1 + 2 + 3 * 4 - 8 / 5 * 2 + 3 - 1'; System.debug('result :' + MathUtil.calculate(test));
总结:此篇只是简单的进行了顺序栈的实现,有好多方法没有封装,有用到顺序栈的小伙伴可以自行优化。四则运算没有考虑表达式校验,小数情况以及具有括号情况,有兴趣的自行优化。篇中有错误的地方欢迎指出,有问题欢迎留言。