网站建设 手机和pc,梁山做网站价格,凡科网络,用网站制作自己app软件1 概述 栈#xff08;Stack#xff09;是限定仅在表尾进行插入和删除操作的线性表。 允许插入和删除的一端称为栈顶#xff08;top#xff09;#xff0c;另一端称为栈底#xff08;bottom#xff09;#xff0c;不含任何数据元素的栈称为空栈#xff0c;栈又称为后进…1 概述 栈Stack是限定仅在表尾进行插入和删除操作的线性表。 允许插入和删除的一端称为栈顶top另一端称为栈底bottom不含任何数据元素的栈称为空栈栈又称为后进先出Last In First Out的线性表简称LIFO结构。 栈的插入操作叫作进栈也称压栈、入栈栈的删除操作叫作出栈也有的叫作弹栈。
2 栈的抽象数据类型
ADT 栈(Stack)Data同线性表。元素具有相同的类型相邻元素具有前驱和后继关系。Operationinit(int maxSize)初始化操作建立一个空栈destroy()若栈存在则销毁它clear()清空栈isEmpty()若栈为空返回true否则返回falsegetTop()若栈存在且非空则返回栈顶元素push(DataType e)进栈pop()出栈length()返回栈的元素个数
endADT3 顺序存储结构
3.1 概述 基于栈的特殊性我们可以考虑使用数组来实现栈令数组的下标为0的元素作为栈底元素并定义一个top指针来指向栈顶元素在数组中的位置 3.2 进栈操作 把数据添加到top指向的下标的下一个下标然后把top下移一位即可 代码实现如下
/*** 进栈操作** param value 待进栈的值* throws RuntimeException 栈满时抛出* author Korbin* date 2023-01-10 11:32:41**/
public void push(T value) {if (top maxSize - 1) {throw new RuntimeException(fulled);}data[top] value;
}3.3 出栈操作 返回top所在的当前元素并令top减1即可 /*** 出栈** return 出栈的元素* throws RuntimeException 栈空时抛出异常* author Korbin* date 2023-01-10 11:34:49**/
public T pop() {if (top -1) {throw new RuntimeException(empty stack);}return data[top--];
}3.4 完整代码
import java.util.Arrays;/*** 栈* p* 线性栈顶的数据为一个数组数组的第一个元素索引为0为栈底* p* 栈是先进后出的数据结构** author Korbin* date 2023-01-10 11:21:07**/
public class StackT {/*** 栈内数据**/private T[] data;/*** 栈的最大长度**/private int maxSize;/*** 栈顶指针为数组索引* p* 值为-1时表示空栈**/private int top -1;/*** 清空栈**/public void clear() {init(maxSize);}/*** 获取栈顶指针** return 栈顶指针* author Korbin* date 2023-01-10 11:45:08**/public T getTop() {if (top -1) {throw new RuntimeException(empty stack);}return data[top];}/*** 初始化** param maxSize 栈的长度* author Korbin* date 2023-01-10 11:38:41**/SuppressWarnings(unchecked)public void init(int maxSize) {this.maxSize maxSize;data (T[]) new Object[maxSize];top -1;}/*** 栈是否为空栈空栈返回true否则返回false* p* top为-1时为空栈**/public boolean isEmpty() {return top -1;}/*** 栈的元素个数**/public int length() {return top 1;}/*** 出栈** return 出栈的元素* throws RuntimeException 栈空时抛出异常* author Korbin* date 2023-01-10 11:34:49**/public T pop() {if (top -1) {throw new RuntimeException(empty stack);}return data[top--];}/*** 进栈操作** param value 待进栈的值* throws RuntimeException 栈满时抛出* author Korbin* date 2023-01-10 11:32:41**/public void push(T value) {if (top maxSize - 1) {throw new RuntimeException(fulled);}data[top] value;}Overridepublic String toString() {return Stack{ data Arrays.toString(data) , stackSize maxSize , top top };}}4 两栈共享空间
4.1 概述 顺序存储的栈使用数组存储数据将下标为0的元素作为栈底元素并定义了top指向栈顶元素定义maxSize确认栈中最大可以存储的元素个数。 这种实现方式可能造成maxSize定义较大但实际使用的空间较小的情况因此为了尽可能节省或者说尽可能利用上存储空间如果有两个栈是相同的数据类型时可以将两个栈一起放置在一个数组中栈A以下标为0的元素为栈底栈B以下标为maxSize-1的元素为栈底双向进行操作以最大利用定义好的数组空间。 实现方式并不复杂只是由原来的只管理一个top变成管理两个top只要top1和top2不“见面”那么数组就可以一直被使用因此当top1 1 top2时才表示栈满了这时两个top“见面”了。
4.2 代码实现
import java.util.Arrays;/*** 双向顺序栈* p* 一个数组中包含两个栈栈1的栈顶索引为0,栈2的栈顶索引为n-1* p* 当栈1的栈顶索引为-1时表示栈1为空栈* p* 当栈2的栈顶索引为n时表示栈2为空栈** author Korbin* date 2023-01-10 11:54:20**/
public class BidirectionalStackT {/*** 栈内数据**/private T[] data;/*** 栈的最大长度**/private int maxSize;/*** 栈1的栈顶指针为数组索引* p* 值为-1时表示空栈**/private int top1 -1;/*** 栈2的栈顶指针为数组索引* p* 值为stackSize时表示空栈**/private int top2 -1;/*** 清空栈** param stackNumber 栈的数量只能为1或2* throws RuntimeException 当栈为空或stackNumber不为1和2时抛出异常* author Korbin* date 2023-01-16 10:14:32**/public void clear(int stackNumber) {if (stackNumber 1) {for (int i 0; i top1; i) {data[i] null;}top1 -1;} else if (stackNumber 2) {for (int i maxSize - 1; i top2; i--) {data[i] null;}top2 maxSize;} else {throw new RuntimeException(error stack number);}}/*** 获取栈1的栈顶指针** param stackNumber 栈的数量只能为1或2* return 栈顶指针* throws RuntimeException 当栈为空或stackNumber不为1和2时抛出异常* author Korbin* date 2023-01-10 11:45:08**/public T getTop(int stackNumber) {if (stackNumber 1) {if (top1 -1) {throw new RuntimeException(empty stack);}return data[top1];} else if (stackNumber 2) {if (top2 maxSize) {throw new RuntimeException(empty stack);}return data[top2];} else {throw new RuntimeException(error stack number);}}/*** 初始化** param maxSize 栈的长度* author Korbin* date 2023-01-10 11:38:41**/SuppressWarnings(unchecked)public void init(int maxSize) {this.maxSize maxSize;this.top1 -1;this.top2 maxSize;data (T[]) new Object[maxSize];}/*** 栈是否为空** param stackNumber 栈的数量只能为1或2* return 为空返回true不为空返回false* throws RuntimeException 当栈为空或stackNumber不为1和2时抛出异常* author Korbin* date 2023-01-16 10:16:29**/public boolean isEmpty(int stackNumber) {if (stackNumber 1) {return top1 -1;} else if (stackNumber 2) {return top2 maxSize;} else {throw new RuntimeException(error stack number);}}/*** 返回栈的元素个数** param stackNumber 栈的数量只能为1或2* return 栈的元素个数* throws RuntimeException 当栈为空或stackNumber不为1和2时抛出异常* author Korbin* date 2023-01-16 10:18:19**/public int length(int stackNumber) {if (stackNumber 1) {return top1 1;} else if (stackNumber 2) {return maxSize - top2;} else {throw new RuntimeException(error stack number);}}/*** 出栈** param stackNumber 栈的数量只能为1或2* return 出栈的值* throws RuntimeException 当栈为空或stackNumber不为1和2时抛出异常* author Korbin* date 2023-01-10 12:06:56**/public T pop(int stackNumber) {if (stackNumber 1) {// 栈1出栈if (top1 -1) {throw new RuntimeException(empty stack);}T result data[top1];data[top1] null;top1--;return result;} else if (stackNumber 2) {// 栈2出栈if (top2 maxSize) {throw new RuntimeException(empty stack);}T result data[top2];data[top2] null;top2;return result;} else {throw new RuntimeException(error stack number);}}/*** 进栈** param value 待进栈的值* param stackNumber 栈的数量为1或2* throws RuntimeException 栈满或者stackNumber不为1和2时抛出异常* author Korbin* date 2023-01-10 12:03:48**/public void push(T value, int stackNumber) {if (top1 1 top2) {throw new RuntimeException(fulled);}if (stackNumber 1) {// 栈1进栈data[top1] value;} else if (stackNumber 2) {// 栈2进栈data[--top2] value;} else {throw new RuntimeException(error stack number);}}Overridepublic String toString() {return BidirectionalStack{ data Arrays.toString(data) , stackSize maxSize , top1 top1 , top2 top2 };}}5 栈的链式存储结构
5.1 概述 栈的链式存储结构简称为链栈处理方式是把栈顶放在单链表的头部用来代替头结点 栈的结点定义中用data表示存储的元素用next表示后继节点
import lombok.Data;/*** 链栈节点** author Korbin* date 2023-01-10 17:12:00**/
Data
public class StackNodeT {/*** 节点值**/private T data;/*** 后继节点**/private StackNodeT next;}5.2 进栈操作 链栈中定义了两个属性一为top指向栈顶元素一为count表示的是实际元素的数量。 因此链栈在进栈时只需要两步操作 (1) 定义一个新的结点令其的后继结点指向top结点 (2) 令top指向新定义的结点 /*** 进栈** param value 待进栈的节点值* author Korbin* date 2023-01-10 17:31:45**/
public void push(T value) {StackNodeT newNode new StackNode();newNode.setData(value);newNode.setNext(top);top newNode;count;
}5.3 出栈操作 令top指向其后继结点即可
/*** 出栈** return 出栈的节点* throws RuntimeException 栈为空时抛出异常* author Korbin* date 2023-01-10 17:38:10**/
public StackNodeT pop() {if (count 0) {throw new RuntimeException(empty stack);}StackNodeT result top;top top.getNext();count--;return result;
}5.4 完整代码
/*** 链栈即链式存储的栈** author Korbin* date 2023-01-10 17:21:26**/
public class LinkStackT {/*** 节点数量**/private int count 0;/*** 栈顶指针**/private StackNodeT top null;/*** 清空链栈** author Korbin* date 2023-01-16 10:34:55**/public void clear() {init();}/*** 获取栈顶节点** return 栈顶节点* author Korbin* date 2023-01-10 17:34:41**/public StackNodeT getTop() {return top;}/*** 初始化链栈** author Korbin* date 2023-01-16 10:34:55**/public void init() {top null;count 0;}/*** 是否为空栈是则返回true否则返回false** return 空栈返回true否则返回false* author Korbin* date 2023-01-16 10:35:29**/public boolean isEmpty() {return count 0;}/*** 获取总节点数** return 总节点数* author Korbin* date 2023-01-10 17:32:14**/public int length() {return count;}/*** 出栈** return 出栈的节点* throws RuntimeException 栈为空时抛出异常* author Korbin* date 2023-01-10 17:38:10**/public StackNodeT pop() {if (count 0) {throw new RuntimeException(empty stack);}StackNodeT result top;top top.getNext();count--;return result;}/*** 进栈** param value 待进栈的节点值* author Korbin* date 2023-01-10 17:31:45**/public void push(T value) {StackNodeT newNode new StackNode();newNode.setData(value);newNode.setNext(top);top newNode;count;}Overridepublic String toString() {StringBuilder builder new StringBuilder([);if (null ! top) {StackNodeT tmp top;builder.append(tmp.getData()).append(,);while (null ! tmp.getNext()) {builder.append(tmp.getNext().getData()).append(,);tmp tmp.getNext();}}builder.append(]);return builder.toString();}}BTW用Java来描述数据结构可能不是一个好的方式——所有内存的处理都忽略了——也可能是我还学不到家。
6 栈的应用-四则运算表达式求值
6.1 中缀表示法、前缀表示法、后缀表示法 通常我们看到的四则运算称为中缀表示法比如
a b * c - (d e)前缀表示法又称波兰表示法即把运算符放在前面操作数写在后面前缀表示法是一种没有括号的表示法将中缀表示法转化成前缀表示法的步骤为 (1) 首先按照运算符的优先级对所有的运算单位加括号 (2) 转前缀则将符号移动到对应括号之前 (3) 去掉括号 如上述表达式我们先将所有运算单位加上括号我们知道上述表达式的运算过程应为 (1) 计算d e (2) 计算b * c (3) 计算a (b * c) (4) 计算(a (b * c)) - (d e) 因此把所有运算单元都加上括号后表达式变为
((a (b * c)) - ( d e ))注意每一步都要加上括号。 然后我们把每个运算符都移到到其对应的括号前面表达式变成
-((a *(b c)) ( d e ))再把括号省略掉得到前缀表达式
- a * b c d e后缀表达式转换方式类似先加括号
((a (b * c)) - ( d e ))然后把运算符移到对应括号后面
((a (b c)*) ( d e ))-然后去掉括号得到结果
a b c * d e -6.2 中缀表达式转前缀表达式的代码实现 代码实现时与手动算法不同遵循如下过程 (1) 初始化两个栈运算符栈S1和储存中间结果的栈S2 (2) 从右至左扫描中缀表达式 (3) 遇到操作数时将其压入S2 (4) 遇到运算符时比较其与S1栈顶运算符的优先级 1) 如果S1为空或栈顶运算符为右括号“)”则直接将此运算符入栈 2) 否则若优先级比栈顶运算符的较高或相等也将运算符压入S1 3) 否则将S1栈顶的运算符弹出并压入到S2中然后从S1中取出栈顶元素再将待处理的元素与栈顶运行符比较处理方式与第(4)点相同 (5) 遇到括号时 1) 如果是右括号“)”则直接压入S1 2) 如果是左括号“(”则依次弹出S1栈顶的运算符并压入S2直到遇到右括号为止此时将这一对括号丢弃 (6) 重复步骤(2)至(5)直到表达式的最左边 (7) 将S1中剩余的运算符依次弹出并压入S2 (8) 依次弹出S2中的元素并输出结果即为中缀表达式对应的前缀表达式。 以以下表达式为例
a b * c - (d e)首先是两个空栈S1和S2 然后是倒序迭代给定的字符串首先是“)”右括号直接压入S1 然后是“e”操作数直接压入S2 然后是“”运算符与S1的栈顶元素“)”比较直接入S1栈 然后是“d”操作数直接压入S2 然后是“(”依次弹出S1的栈顶元素直到遇到“)”并抛弃这一对括号 然后是“-”与S1的栈顶元素比较因S1的栈顶元素是空因此直接进入S1栈 然后是“c”操作数直接压入S2 然后是“*”与S的栈顶元素“-”比较优先级较高因此压入S1 然后是“b”操作数直接压入S2 然后是“”与S1的栈顶元素“*”比较优先级较低因此先将S1的栈顶元素弹出放到S2 然后与S1新的栈顶元素“-”相比优先级相同因此直接将“”压入S1 然后是“a”操作数直接压入S2 中缀表达式的所有字符都已读取完这时将S1的所有元素依次弹出压入S2 再将S2依次读出得到前缀表达式结果
- a * b c d e我们用两栈共享空间的方式来实现代码 /*** 判断字符串是否是数字** param val 待判断的字符串* return 是数字则返回true否则返回false* author Korbin* date 2023-01-16 16:53:26**/
private boolean isData(String val) {Pattern p Pattern.compile(^[a-zA-Z0-9]$);return p.matcher(val).find();
}/*** 中缀表达式转前缀表达式** param infix 中缀表达式* return 前缀表达式* author Korbin* date 2023-01-16 11:49:29**/
public String infix2Prefix(String[] infix) {// 定义一个双向栈// 左边栈为S1为运算符栈// 右边栈为S2为中间结果栈BidirectionalStackString stack new BidirectionalStack();stack.init(infix.length);for (int i infix.length - 1; i 0; i--) {// 从右至左迭代中缀表达式String curStr infix[i];// 取出运行符栈的栈顶元素String topOperator null;try {topOperator stack.getTop(1);} catch (Exception e) {// do nothing}// 如果为操作数直接入中间结果栈if (isData(curStr)) {// 操作数stack.push(curStr, 2);} else if (curStr.equals(()) {// 左括号while (null ! topOperator !topOperator.equals())) {// 弹出运算符栈的元素并压入中间结果栈直到遇到右括号为止stack.push(stack.pop(1), 2);try {topOperator stack.getTop(1);} catch (Exception e) {// do nothingtopOperator null;}}if (null ! topOperator) {// 抛弃右括号stack.pop(1);}} else if (curStr.equals())) {// 右括号// 直接进入运算符栈stack.push(curStr, 1);} else if (curStr.equals() || curStr.equals(-) || curStr.equals(*) || curStr.equals(/)) {// 运算符boolean inserted false;while (!inserted) {if (null topOperator || topOperator.equals())) {// 运算符栈顶为空或栈顶元素为右括号// 直接入栈到运算符栈并结束stack.push(curStr, 1);inserted true;} else if (curStr.equals(*) || curStr.equals(/) || topOperator.equals() ||topOperator.equals(-)) {// 优先级比栈顶运算符的较高或相等// 即待比较的字符为乘或除或者运算符栈顶元素为加或减时// 直接入栈到运算符栈并结束stack.push(curStr, 1);inserted true;} else {// 弹出运算符栈的元素并压入中间结果栈然后继续比较运算符栈的栈顶元素stack.push(stack.pop(1), 2);try {topOperator stack.getTop(1);} catch (Exception e) {// do nothingtopOperator null;}}}} else {// 其他情况例如为空时1直接入中间结果栈if (!curStr.equals( )) {stack.push(curStr, 2);}}}// 然后将运算符栈中的所有元素再压入中间结果栈while (!stack.isEmpty(1)) {stack.push(stack.pop(1), 2);}// 得到结果StringBuilder result new StringBuilder();while (!stack.isEmpty(2)) {result.append(stack.pop(2));}return result.toString();}6.3 中缀表达式转后缀表达式的代码实现 (1) 初始化两个栈运算符栈S1和储存中间结果的栈S2 (2) 从左至右扫描中缀表达式 (3) 遇到操作数时将其压入S2 (4) 遇到运算符时比较其与S1栈顶运算符的优先级 1) 如果S1为空或栈顶运算符为左括号“(”则直接将此运算符入栈 2) 否则若优先级比栈顶运算符的高也将运算符压入S1注意转换为前缀表达式时是优先级较高或相同而这里则不包括相同的情况 3) 否则将S1栈顶的运算符弹出并压入到S2中然后取出S1中新的栈顶元素再次转到(4)进行比较 (5) 遇到括号时 1) 如果是左括号“(”则直接压入S1 2) 如果是右括号“)”则依次弹出S1栈顶的运算符并压入S2直到遇到左括号为止此时将这一对括号丢弃 (6) 重复步骤(2)至(5)直到表达式的最右边 (7) 将S1中剩余的运算符依次弹出并压入S2 (8) 依次弹出S2中的元素并输出结果的逆序即为中缀表达式对应的后缀表达式转换为前缀表达式时不用逆序。
msp; 然后以以下表达式为例
a b * c - (d e)先定义两个空的栈 然后从头开始迭代先是“a”操作数直接压入S2 然后是“”运算符与S1的栈顶元素比较因S1的栈顶元素为空因此直接压入S1 然后是“b”操作数直接压入S2 然后是“*”运算符与S1的栈顶元素“”比较优先级较高直接压入S1 然后是“c”操作数直接压入S2 然后是“-”操作数与S1的栈顶元素“”比较发现优先级低因此将“”从S1弹出压入S2 继续与S1新的栈顶元素“”比较优先级相同将“”从S1弹出压入S2 继续与S1新的栈顶元素比较发现S1为空因此直接将“-”压入S1 然后是“(”直接压入S1 然后是“d”操作数直接压入S2 然后是“”运算符与S1的栈顶元素“(”比较因此是左括号因此直接压入S1 然后是“e”操作数直接压入S2 然后是“)”依次弹出S1的元素压入S2直到遇到左括号然后把这一对括号去掉 迭代完毕把S1剩余的元素依次压入S2 从S2中依次读取出结果
- e d * c b areverse得到后缀表达式结果
a b c * d e -代码如下所示
/*** 中缀表达式转后缀表达式** param infix 后缀表达式* return 前缀表达式* author Korbin* date 2023-01-16 11:49:29**/
public String infix2Suffix(String[] infix) {// 定义一个双向栈// 左边栈为S1为运算符栈// 右边栈为S2为中间结果栈BidirectionalStackString stack new BidirectionalStack();stack.init(infix.length);for (int i 0; i infix.length - 1; i) {// 从左至右迭代中缀表达式String curStr infix[i];// 取出运行符栈的栈顶元素String topOperator null;try {topOperator stack.getTop(1);} catch (Exception e) {// do nothing}// 如果为操作数直接入中间结果栈if (isData(curStr)) {// 操作数stack.push(curStr, 2);} else if (curStr.equals(()) {// 左括号// 直接进入运算符栈stack.push(curStr, 1);} else if (curStr.equals())) {// 右括号while (null ! topOperator !topOperator.equals(()) {// 弹出运算符栈的元素并压入中间结果栈直到遇到左括号为止stack.push(stack.pop(1), 2);try {topOperator stack.getTop(1);} catch (Exception e) {// do nothingtopOperator null;}}if (null ! topOperator) {// 抛弃右括号stack.pop(1);}} else if (curStr.equals() || curStr.equals(-) || curStr.equals(*) || curStr.equals(/)) {// 运算符boolean inserted false;while (!inserted) {if (null topOperator || topOperator.equals(()) {// 运算符栈顶为空或栈顶元素为左括号// 直接入栈到运算符栈并结束stack.push(curStr, 1);inserted true;} else if ((curStr.equals(*) || curStr.equals(/)) (topOperator.equals() || topOperator.equals(-))) {// 优先级比栈顶运算符的较高// 即运算符栈顶元素为加或减时// 直接入栈到运算符栈并结束stack.push(curStr, 1);inserted true;} else {// 弹出运算符栈的元素并压入中间结果栈然后继续比较运算符栈的栈顶元素stack.push(stack.pop(1), 2);try {topOperator stack.getTop(1);} catch (Exception e) {// do nothingtopOperator null;}}}} else {// 其他情况例如为空时1直接入中间结果栈if (!curStr.equals( )) {stack.push(curStr, 2);}}}// 然后将运算符栈中的所有元素再压入中间结果栈while (!stack.isEmpty(1)) {stack.push(stack.pop(1), 2);}// 得到结果StringBuilder result new StringBuilder();while (!stack.isEmpty(2)) {result.append(stack.pop(2));}return result.reverse().toString();
}6.4 使用前缀表达式计算四则运算 现有四则运算表达式
9 (3 - 1) * 3 10 / 2转化成前缀表达式后是 9 * - 3 1 3 / 10 2先初始化一个空栈然后从右向左开始处理规则是如果是数字则进栈如果是符号就将处于栈顶的两个数字出栈进行运算运算结果进栈一直到最终获得结果注意栈顶元素是“x”栈的第二个元素是“y”则当是运算符“zz”时运算方式应是“x zz y”。 如上述前缀表达式先是“2”直接进栈 然后是“10”直接进栈 然后是“/”取出栈顶的两个元素然后进行“10 / 2”处理得到5然后入栈 然后是“3”直接进栈 然后是“1”直接进栈 然后是“3”直接进栈 然后是“-”取出栈顶的两个元素进行“3 - 1”处理得到2然后入栈 然后是“*”取出栈顶的两个元素进行“2 * 3”处理得到6然后入栈 然后是“9”直接进栈 然后是“”取出栈顶的两个元素进行“9 6”处理得到15然后入栈 然后是“”取出栈顶的两个元素进行“15 5”处理得到20然后入栈 于是得到最终结果20。 代码如下所示
/*** 使用前缀表达式计算** param prefixExpression 前缀表达式* return 计算结果* author Korbin* date 2023-01-16 18:17:01**/
public double prefixCalc(String[] prefixExpression) {LinkStackString stack new LinkStack();int length prefixExpression.length;for (int i length - 1; i 0; i--) {String curStr prefixExpression[i];if (isData(curStr)) {// 如果是操作数则直接入栈stack.push(curStr);} else {// 否则使用第二个元素 运算符 栈顶元素得出结果后再将结果入栈double firstData Double.parseDouble(stack.pop().getData());double secondData Double.parseDouble(stack.pop().getData());double value 0;switch (curStr) {case :value firstData secondData;break;case -:value firstData - secondData;break;case *:value firstData * secondData;break;case /:value firstData / secondData;break;}stack.push(String.valueOf(value));}}return Double.parseDouble(stack.pop().getData());
}6.5 使用后缀表达式计算四则运算 现有四则运算表达式
9 (3 - 1) * 3 10 / 2转化成后缀表达式后是
9 3 1 - 3 * 10 2 / 先初始化一个空栈然后从左向右开始处理规则是如果是数字则进栈如果是符号就将处于栈顶的两个数字出栈进行运算运算结果进栈一直到最终获得结果注意栈顶元素是“x”栈的第二个元素是“y”则当是运算符“zz”时运算方式应是“y zz x”。 如上述后缀表达式先是“9”直接进栈 然后是“3”直接进栈 然后是“1”直接进栈 然后是“-”取出栈顶的两个值进行“3 - 1”处理得到2再进栈 然后是“3”直接进栈 然后是“*”取出栈顶的两个值进行“2 * 3”处理得到6再进栈 然后是“”取出栈顶的两个值进行“9 6”处理得到15再进栈 然后是“10”直接进栈 然后是“2”直接进栈 然后是“/”取出栈顶的两个值进行“10 / 2”处理得到5再进栈 然后是“”取出栈顶的两个值进行“15 5”处理得到20再进栈 这样就得到了最终结果。 代码如下所示
/*** 使用后缀表达式计算** param suffixExpression 后缀表达式* return 计算结果* author Korbin* date 2023-01-16 18:17:01**/
public double suffixCalc(String[] suffixExpression) {LinkStackString stack new LinkStack();int length suffixExpression.length;for (int i 0; i length - 1; i) {String curStr suffixExpression[i];if (isData(curStr)) {// 如果是操作数则直接入栈stack.push(curStr);} else {// 否则使用栈顶元素 运算符 第二个元素得出结果后再将结果入栈double secondData Double.parseDouble(stack.pop().getData());double firstData Double.parseDouble(stack.pop().getData());double value 0;switch (curStr) {case :value firstData secondData;break;case -:value firstData - secondData;break;case *:value firstData * secondData;break;case /:value firstData / secondData;break;}stack.push(String.valueOf(value));}}return Double.parseDouble(stack.pop().getData());
}6.6 总结 可见无论在中缀转前缀或中缀转后缀时或者在使用前缀或后缀进行计算时都可以使用栈来进行辅助计算。 注本文为程 杰老师《大话数据结构》的读书笔记其中一些示例和代码是笔者阅读后自行编制的。
