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));

总结:此篇只是简单的进行了顺序栈的实现,有好多方法没有封装,有用到顺序栈的小伙伴可以自行优化。四则运算没有考虑表达式校验,小数情况以及具有括号情况,有兴趣的自行优化。篇中有错误的地方欢迎指出,有问题欢迎留言。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人工智能LeadAI

数据结构 | 栈

01 栈的定义 栈(Stack)是限定仅在表尾进行插入和删除操作的线性表。 我们把允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含...

3289
来自专栏Java与Android技术栈

高阶函数和Java的Lambda

java 8引入了函数式编程。函数式编程重点在函数,函数变成了Java世界里的一等公民,函数和其他值一样,可以到处被定义,可以作为参数传入另一个函数,也可以作为...

853
来自专栏我杨某人的青春满是悔恨

深入理解 weak-strong dance

这时handler持有 Block 对象,而 Block 对象虽然捕获了weakSelf,延长了weakSelf这个局部变量的生命周期,但weakSelf是附有...

514
来自专栏mathor

位与进制

 这里我假设读者有二进制的思维,知道(3)~10~=(011)~2~将十进制转换为二进制的方法

361
来自专栏余林丰

Effective Java通俗理解(上)

  这篇博客是Java经典书籍《Effective Java(第二版)》的读书笔记,此书共有78条关于编写高质量Java代码的建议,我会试着逐一对其进行更为通俗...

2237
来自专栏专注数据中心高性能网络技术研发

[Effective Modern C++(11&14)]Chapter 3: Moving to Modern C++

1976
来自专栏xingoo, 一个梦想做发明家的程序员

汇编语言 手记8

栈有两个基本的操作:入栈和出栈 入栈:将一个新的元素放到栈顶 出栈:从栈顶取出一个元素 栈顶的元素总是最后入栈,需要出栈时,又最先被从栈中取出。 栈的操作规则:...

1775
来自专栏阿杜的世界

Java泛型基础(一)目的泛型类总结

利用Java开发的时候,肯定会有一个类持有另一个或几个类的情况,在编写一些比较基础的组件,例如缓存操作组件,这类组件的逻辑差不多,但是希望能够处理不同的类型。

371
来自专栏小樱的经验随笔

【Java数据结构学习笔记之二】Java数据结构与算法之栈(Stack)实现

  本篇是java数据结构与算法的第2篇,从本篇开始我们将来了解栈的设计与实现,以下是本篇的相关知识点: 栈的抽象数据类型 顺序栈的设计与实现 链式栈的设计与实...

3216
来自专栏云霄雨霁

数据结构----队列

910

扫码关注云+社区