要敲代码, 设计先行. 栈不再解释了, 这里主要看设计思想.
修炼完数据结构与算法之后, 可以左手一把精钢哈希表盾牌, 右手一条链表数组剑鞭, 可以去刷怪(题)了.
今天正好是难得的2月29日, 必须得发一篇博文. 最近在好友安利下开始玩起了PathOfExile, 感觉是一个巨坑, 不过再坑也不能耽误学编程.
- 栈的设计
- 栈的实现
- 栈的应用 - 括号匹配
- 栈的应用 - 中缀运算表达式转后缀 - 四则运算符
- 栈的应用 - 中缀运算表达式转后缀 - 扩展运算符
- 栈的应用 - 计算后缀表达式的值
- 栈的应用 - 双栈计算中缀表达式
栈的设计
栈顶: 最后添加到栈的一项. 栈限制对其中项目的访问, 客户只能看到或删除栈顶或者加入栈顶. 查找的方法是一个个删除, 直到找到或者为空.
栈的这个特点, 可以将一系列内容的顺序反过来.
将项添加到栈中的操作称为入栈(push), 删除操作称为出栈(pop). 获取栈顶项目但不删除的操作叫做查看(peek). 一般不能在栈中查找具体项, 但可以根据实现而不同.
所以老样子, 先来创建接口:
public interface Stack<T> {
void push(T newEntry);
T pop();
T peek();
boolean isEmpty();
void clear();
}
接口只是一个开始, 然后还需要规划行为:
- 栈为空时候要不要抛异常. 取决于是否认为栈中可以存放null. 如果可以, 最好的方法是在栈空的时候, 对公共方法比如pop()和peek()来抛出异常.
- 私有方法与公有方法不同, 私有方法需要处理各种可能出现的问题, 以让私有方法可以信任. 不要信任公有方法, 客户会以很多方式来调用.
- 抛异常抛什么异常呢, 如果预期让客户从异常中恢复, 就应该抛受检异常. 对于栈来说, 如果栈为空一般意味着使用错误, 所以要抛运行时错误.
栈的实现
回想一下之前写的包, 虽然包本身是没有顺序的. 但是我们内部使用的链表和数组都是有顺序的.
但具体顺序如何, 还需要进一步看实现, 数组包添加到最后一项, 默认弹出最后一项, 其实完全符合要求. 链表每次添加在头部节点, 删除的时候也从头部节点开始删除, 依然符合这种情况.
所以可以任意选择数组和链表结构来实现, 但是对外暴露的API就不要向包那么多了, 仅需要实现上边的代码.
就以链表为例, 修改一个栈出来, 由于栈对外暴露的方法不多, 因此只需要弄两个私有方法来添加和删除首结点即可:
public class LinkedListStack<T> implements Stack<T> {
private class Node {
private T data;
private Node next;
private Node(T dataPortion) {
this(dataPortion, null);
}
private Node(T dataPortion, Node nextNode) {
this.data = dataPortion;
this.next = nextNode;
}
@Override
public String toString() {
return "Node{" +
"data=" + data +
'}';
}
}
private Node firstNode;
private int numberOfEntries;
public LinkedListStack() {
this.firstNode = null;
this.numberOfEntries = 0;
}
@Override
public T pop() {
return remove();
}
@Override
public T peek() {
if (isEmpty()) {
throw new RuntimeException("栈为空, 不能进行peek()操作");
} else {
return firstNode.data;
}
}
@Override
public boolean isEmpty() {
return numberOfEntries == 0;
}
@Override
public void clear() {
firstNode = null;
numberOfEntries = 0;
}
@SuppressWarnings("unchecked")
public T[] toArray() {
T[] result = (T[]) new Object[numberOfEntries];
int i = 0;
Node currentNode = firstNode;
while (i < numberOfEntries && currentNode != null) {
result[i++] = currentNode.data;
currentNode = currentNode.next;
}
return result;
}
@Override
public void push(T newEntry) {
add(newEntry);
}
/**
* 私有方法删除并返回一个数据, 删除链表开头的数据
* 如果链表为空则抛出异常
*
* @return 当链表为空返回null, 不为空则返回链表第一个节点的数据对象
*/
private T remove() {
T result = null;
if (!isEmpty()) {
result = firstNode.data;
firstNode = firstNode.next;
numberOfEntries--;
} else {
throw new RuntimeException("栈为空, 不能进行pop()操作");
}
return result;
}
/**
* 向链表中添加一个新的数据, 原理是创建一个新节点, 让新节点指向链表头, 然后让链表头指向新节点
*
* @param newEntry The object to be added as a new entry.
*/
private void add(T newEntry) {
Node newNode = new Node(newEntry);
newNode.next = firstNode;
firstNode = newNode;
numberOfEntries++;
}
}
栈的应用 - 括号匹配
先看几个概念:
- a+b 中缀表达式, 即运算符在操作数之间.
- +ab 前缀表达式, 也叫波兰表示法
- ab+ 后缀表达式, 也叫逆波兰表示法
利用栈首先可以解决的一大问题, 就是中缀代数表达式中的分隔符是否正确, 分隔符即{},[],(), 所谓分隔符正确, 就是指整个式子中所有的分隔符都是能够互相配对的.
这个套路其实之前就玩过了, 如果表达式是一个字符串, 只要按从左到右(或者右到左)的顺序扫描一遍, 将所有的一侧符号都压入栈中, 扫描到另外一侧符号的时候, 从栈中弹出与其对应的符号, 如果扫描完毕, 栈依然是空的, 就说明分隔符是正确的.
写出代码如下:
public boolean checkBalance(String expression) {
boolean result = false;
if (expression == null) {
return result;
}
int length = expression.length();
LinkedListStack<Character> stack = new LinkedListStack<>();
Character popedCharacter;
for (int i = 0; i < length; i++) {
char c = expression.charAt(i);
switch (c) {
case '{':
case '[':
case '(':
stack.push(c);
break;
case '}':
popedCharacter = stack.pop();
if (popedCharacter != '{') {
return result;
}
break;
case ']':
popedCharacter = stack.pop();
if (popedCharacter != '[') {
return result;
}
break;
case ')':
popedCharacter = stack.pop();
if (popedCharacter != '(') {
return result;
}
break;
default:
}
System.out.println("当前的栈是: " + Arrays.toString(stack.toArray()));
}
if (stack.isEmpty()) {
result = true;
}
return result;
}
栈的应用 - 中缀运算表达式转后缀 - 四则运算符
将中缀表达式转换成后缀表达式. 当时第一次碰到这个算法的时候还是仔细想了一下. 因为后缀表达式是按照优先级来排序的, 优先级高的会拍在一起, 所以这个套路就是不断的比较压入栈的操作符与当前操作符的优先级.
如果当前操作符的优先级高于栈中的操作符,就说明这个当前操作符一定是写的更靠左, 所以就压入栈中, 等到下一个操作数拼接到字符串上之后, 再弹栈或者进行比较, 如果小于, 就说明靠右, 就出一个栈, 然后把当前操作符压进栈, 然后继续拼接字符串并进行比较.
总结一下操作就是:
- 从左至右扫描操作符, 创建一个新的空字符串A作为结果
- 对于每一个符号, 如果不是运算符, 拼接到A上
- 对于每一个符号, 如果是运算符, 如果栈为空, 压入栈中. 如果栈不为空, 比较当前符号与栈顶符号的优先级程度
- 当前符号优先级大于栈顶符号, 将当前符号压入栈中
- 当前符号优先级等于或者小于栈顶符号, 说明之前有操作符不属于下一个操作数, 必须反复弹出操作符并拼接到字符串上, 直到栈为空, 说明之前的操作符都已经弹完了, 之后再把当前操作符加入到栈中.
根据这个方法, 写出支持四则运算, 不带括号的方法:
public String change(String expression) {
if (expression == null) {
return "";
}
LinkedListStack<Character> stack = new LinkedListStack<>();
StringBuilder stringBuilder = new StringBuilder();
int length = expression.length();
for (int i = 0; i < length; i++) {
char c = expression.charAt(i);
switch (c) {
case '+':
case '-':
case '*':
case '/':
if (stack.isEmpty()) {
stack.push(c);
} else {
//当前优先级大于栈中的, 说明上一个操作数不是上一个操作符的操作数, 所以将运算符入栈
if (big(c, stack.peek())) {
stack.push(c);
} else {
//如果当前优先级小于等于, 说明存在之前要计算完毕的表达式, 就需要反复弹出, 直到栈为空或者再出现大于的情况
while (!stack.isEmpty() && !big(c, stack.peek())) {
stringBuilder.append(stack.pop());
}
//弹干净之后说明又有一段新的表达式, 加入栈中
stack.push(c);
}
}
break;
default:
stringBuilder.append(c);
break;
}
}
//全部处理完之后, 如果还有栈中的运算符, 一定是前边剩下的, 也全部弹出加在字符串后边即可.
while (!stack.isEmpty()) {
stringBuilder.append(stack.pop());
}
return stringBuilder.toString();
}
//第一个操作符的优先级大于第二个操作符
private boolean big(Character c1, Character c2) {
return (c1 == '*' || c1 == '/') && (c2 == '+' || c2 == '-');
}
逻辑还是对的, 像System.out.println(test.change("a*b*c-d*e"));, 运算结果是: ab*c*de*-, 按照结合律ab=y, 这个式子是 yc*de*, yc=x, 变成 xde*-, 这个时候就是运算 de*=z, 最后就是 xz-, 正确.
栈的应用 - 中缀运算表达式转后缀 - 扩展运算符
然后还需要引入括号, 由于括号括住的部分一定需要先行计算完成, 因此将左括号看成一个运算符, 优先级比其他运算符都低, 之后的所有运算符继续按照正常顺序来判定. 直到出现一个右括号, 就反复弹栈, 直到弹出左括号.
还需要引入的就是幂, 幂是右结合的, 意味着所有运算符里幂运算是优先级最高的, 而且再加上右结合, 意味着直接压栈即可.
最后总结出了如下规律:
- 操作数: 拼接在字符串之后
- +-*/四则运算符: 比较大小关系, 如果优先级相等或者小于, 说明栈顶的运算符属于前边两个操作数, 弹栈拼接再将当前压栈. 如果优先级高于, 说明上一个操作数不属于栈顶的运算符, 而属于当前运算符, 将当前运算符压栈
- 遇到左括号: 将左括号压栈即可
- 遇到右括号: 首先右括号不压栈, 直接丢掉. 从栈中弹出所有运算符, 直到遇到左括号, 左括号也弹出, 但是不要将左括号拼接到字符串中
- 遇到幂运算符: 直接压栈, 表示优先级最高.
所以栈这个后进先出, 还真的要好好理解一下如何应用先进先出的思想.
可以继续修改代码如下:
public String change(String expression) {
if (expression == null) {
return "";
}
LinkedListStack<Character> stack = new LinkedListStack<>();
StringBuilder stringBuilder = new StringBuilder();
int length = expression.length();
for (int i = 0; i < length; i++) {
char c = expression.charAt(i);
switch (c) {
//幂优先级最高, 直接入栈. 左括号作为分隔符, 也直接入栈
case '^':
case '(':
stack.push(c);
break;
//加减乘除, 只需要判断当前的加减乘除与栈中的运算符(加减乘除,幂,左括号)进行判断
//如果大于, 直接压栈
//如果小于, 反复弹到当前运算符小于等于栈顶运算符, 然后压栈
//可见最终一定要压栈当前运算符, 只是在压栈前看优先级, 当前运算符优先级高, 就要保留, 如果级别低或者相等, 说明在当前运算符之前需要把高于这个运算符优先级的都弹回去
case '+':
case '-':
case '*':
case '/':
//栈不为空且当前运算符不大于(即小于等于)栈顶运算符, 反复弹栈并将运算符拼接到字符串上
while (!stack.isEmpty() && !big(c, stack.peek())) {
stringBuilder.append(stack.pop());
}
stack.push(c);
break;
//右括号处理, 一个右括号, 必定和之前的左括号搭配, 只要程序不错误, 栈中此时至少会有一个左括号
//因此需要不断检查栈顶, 只要不是左括号, 就弹栈并且拼接, 直到左括号出现, 说明两个括号之间的内容都已经处理完毕
//之后就抛弃栈里的左括号
case ')':
while (stack.peek() != '(') {
stringBuilder.append(stack.pop());
}
stack.pop();
break;
//不是运算符就直接拼接上去
default:
stringBuilder.append(c);
break;
}
System.out.println("当前的栈是: " + Arrays.toString(stack.toArray()));
}
//处理完之后, 如果还有没有拼上去的运算符, 就按照顺序拼上去, 优先级不会错
while (!stack.isEmpty()) {
stringBuilder.append(stack.pop());
}
return stringBuilder.toString();
}
//解析方法依赖于四则运算符与(四则运算符or左括号or幂运算符号)的大小比较, 所以这个方法很重要
public boolean big(Character c1, Character c2) {
//第一种情况, 四则运算相互比较, 只有一种情况是优先级高, 就是c1是乘or除, c2是加or减. 其他的所有情况都不是大于
boolean condition1 = (c1 == '*' || c1 == '/') && (c2 == '+' || c2 == '-');
//第二种情况, 只要第一个是幂运算, 始终高, 因为幂是左结合, 必定高
boolean condition2 = (c1 == '^');
//第三种情况, 比较括号, 由于括号一定是后来的优先级要高于之前的, 因此不管前边是什么, 哪怕也是一个括号, 一定比已经存在栈中的括号要高, 所以只需要c2是括号即可.
boolean condition3 = (c2 == '(');
//最后三种条件满足任意一种, 都判定为c1优先级大于c2.
return condition1 || condition2 || condition3;
}
栈的应用 - 计算后缀表达式的值
通过比较中缀表达式和后缀表达式, 可以发现后缀表达式的运算符和操作数出现的顺序就决定了优先顺序, 无需像中缀表达式一样使用括号来强调优先级.
后缀表达式特别适合使用栈来进行计算, 只需要按照从左向右解析, 每次遇到运算符就弹出两个操作数, 计算完毕之后, 将结果放入栈中即可.
public static double evaluatePostfix(String expression) {
Stack<Double> value = new LinkedListStack<>();
int length = expression.length();
for (int i = 0; i < length; i++) {
char c = expression.charAt(i);
switch (c){
case '+':
case '-':
case '*':
case '/':
case '^':
double secondOp = value.pop();
double firstOp = value.pop();
//先弹出来的是第二个操作数, 后弹出来的是第一个操作数, 这里要注意顺序
//依赖私有静态方法evaluate
value.push(evaluate(firstOp, secondOp, c));
break;
default:
value.push(Double.parseDouble(String.valueOf(c)));
break;
}
}
System.out.println("当前的栈是: " + Arrays.toString(value.toArray()));
double result = value.pop();
//这里要注意, 正常结束的话, 栈中只会有一个结果, 如果栈弹出结果之后还有结果, 说明表达式有误.
if (!value.isEmpty()) {
throw new RuntimeException("表达式有误");
}
return result;
}
//私有静态方法evaluate, 用来实际求值并返回, 如果有错误, 因为是表达式的问题, 直接抛异常即可.
private static double evaluate(double firstOp, double secondOp, char operator) {
switch (operator) {
case '+':
return firstOp + secondOp;
case '-':
return firstOp - secondOp;
case '*':
return firstOp * secondOp;
case '/':
return firstOp / secondOp;
case '^':
return Math.pow(firstOp, secondOp);
default:
throw new RuntimeException("不支持运算符: " + operator);
}
}
有了将中缀表达式转换成后缀表达式的函数和对后缀表达式进行求值的函数, 就可以对中缀表达式进行求值了, 只要将上边两个方法结合起来, 先把中缀表达式转换成后缀表达式, 再对后缀表达式求值.
System.out.println(Postfix.evaluatePostfix(Postfix.convertToPostfix("6/3*(1+(9-7))")));
不过还有更好的办法, 可以发现从中缀表达式转换成后缀表达式使用了一次栈, 求值后缀表达式的时候又使用了一次栈. 可以直接通过使用双栈来计算后缀表达式.
栈的应用 - 双栈计算中缀表达式
各种算法真的是争奇斗艳, 使用一个栈不行, 就使用两个栈, 一个栈保存操作数, 一个栈保存操作符.
其核心算法是, 将操作数压入A栈, 遇到运算符, 如果运算符比栈顶运算符优先级高, 就压入B栈, 如果优先级小于或者等于, 就从B栈中弹出之前的操作符, 但是在弹出操作符的时候, 也要弹出两个操作数, 将结果计算完毕之后放回栈中.
这样反复操作直到表达式末尾, 然后不断弹出运算符和两个操作数, 计算完成之后放入栈中, 直到B栈为空.
遇到幂的方法不变, 遇到括号的时候, 则需要一直弹出直到左括号结束, 逻辑和刚才解析后缀表达式的时候非常相似.
来自己编写出来, 这次改成Integer返回类型, 因为对于不大的表达式, 单字符没有必要去解析成double:
public static int evaluateInfix(String expression) {
Stack<Character> operatorStack = new LinkedListStack<>();
Stack<Integer> valueStack = new LinkedListStack<>();
int length = expression.length();
for (int i = 0; i < length; i++) {
char c = expression.charAt(i);
switch (c) {
case '+':
case '-':
case '*':
case '/':
//运算符栈为空就压栈
if (operatorStack.isEmpty()) {
operatorStack.push(c);
//运算符栈不为空, 比较大小, 当前运算符优先级高就压栈
} else if (big(c, operatorStack.peek())) {
operatorStack.push(c);
} else {
//当前运算符优先级低, 就不断弹出之前的都算完, 最后再压入自己
while (!operatorStack.isEmpty() && !big(c, operatorStack.peek())) {
int secondOp = valueStack.pop();
int firstOp = valueStack.pop();
valueStack.push(evaluate(firstOp, secondOp, operatorStack.pop()));
}
operatorStack.push(c);
}
break;
//对于幂运算是最高级,左括号是分隔符, 都无条件压入栈中
case '^':
case '(':
operatorStack.push(c);
break;
//右括号逻辑与原来一样, 说明到了一个结果的末尾, 只要反复弹栈计算, 直到左括号, 也弹出不要, 此时值栈中的数据就是括号中计算的结果.
case ')':
while (operatorStack.peek() != '(') {
int secondOp = valueStack.pop();
int firstOp = valueStack.pop();
valueStack.push(evaluate(firstOp, secondOp, operatorStack.pop()));
}
operatorStack.pop();
break;
//不是上述运算符, 就是值, 全部压入值栈中
default:
valueStack.push(Integer.parseInt(String.valueOf(c)));
break;
}
}
//表达式解析完成之后, 运算符栈中一定是按照优先级排列好的运算符, 只需要不断弹栈求值
while (!operatorStack.isEmpty()) {
int secondOp = valueStack.pop();
int firstOp = valueStack.pop();
valueStack.push(evaluate(firstOp, secondOp, operatorStack.pop()));
}
int result = valueStack.pop();
//最后加上一个判断, 值栈应该正好弹空, 否则报运行时错误.
if (valueStack.isEmpty()) {
return result;
} else {
throw new RuntimeException("表达式有误");
}
}
这一章书上都没有具体实现, 只给出了算法, 自己经过跟踪Debug, 成功的都实现出来了. 剩下就是利用这些思路, 去做一下练习了.
