salesforce零基礎學習（七十六）順序棧的實現以及應用

數據結構中，針對線性表包含兩種結構，一種是順序線性表，一種是鏈表。順序線性表適用於查詢，時間複雜度為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));

總結：此篇只是簡單的進行了順序棧的實現，有好多方法沒有封裝，有用到順序棧的小夥伴可以自行優化。四則運算沒有考慮表達式校驗，小數情況以及具有括弧情況，有興趣的自行優化。篇中有錯誤的地方歡迎指出，有問題歡迎留言。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！