最近学习栈，写点东西，以备后查，主要从七个方面来介绍：（1）栈的介绍 （2）栈的逻辑分析和数组实现 （3）利用栈实现综合计算器 （4）前缀，中缀，后缀介绍，（5）中缀转后缀的逻辑分析和代码实现 （6）逆波兰计算器的实现 （7）总结
前面简单介绍了队列和链表，并通过代码实现了他们的增删改查，如果我们想通过一端来增删数据，另一并不改变，应该怎么实现呢？
计算式：7*2*2-5+1-5*3-3=?
计算机底层是如何运算得到结果的？注意不是简单的把算式列出运算，计算机怎么理解这个算式的（对计算机而言，它接收到的就是一个字符串），我们讨论的是这个问题。–>栈
（1）栈的介绍
栈是一种线性数据结构，只能通过访问其一段来存储或读取数据，可以将堆栈看成餐厅中的一叠盘子，将新盘子放在最上面，并从最上面取走盘子，最后一个堆在上面的盘子也是第一个被取走的，因此堆栈被称为先进后出结构（LIFO），一般而言，把允许操作的一端称为栈顶(Top)，不可操作的一端称为栈底(Bottom)，同时把插入元素的操作称为入栈(Push),删除元素的操作称为出栈(Pop)。若栈中没有任何元素，则称为空栈，栈的结构如下图：
- 栈的英文为(stack)
- 栈是一个先入后出(FILO-First In Last Out)的有序列表。
- 栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。
- 根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除
以羽毛球筒为例，羽毛球筒就是一个栈，刚开始羽毛球筒是空的，也就是空栈，然后我们一个一个放入羽毛球，也就是一个一个push进栈，当我们需要使用羽毛球的时候，从筒里面拿，也就是pop出栈，但是第一个拿到的羽毛球是我们最后放进去的。
入栈的实现：
出栈操作：
堆栈的应用场景：
- 子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。
- 处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。
- 表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)。
- 二叉树的遍历。 图形的深度优先(depth一first)搜索法。
（2）栈的逻辑分析和数组实现
对于一个栈而言，常有的操作为：
- isFull()------------是否为满
- isEmputy()------检查堆栈是否为空
- push()---------入栈
- pop()----------出战
- list()-------遍历栈
栈的逻辑分析：
栈的数组代码实现：
package JAVADATASTRTUCRE;
import java.util.Scanner;
/**
* Created with IntelliJ IDEA.
* User: yongping Li
* Date: 2020/11/19
* Time: 20:05
* Description: 栈的数组实现
*/
public class ArrayStatckDemo {
public static void main(String[] args) {
//栈的测试
ArrayStatck arrayStatck = new ArrayStatck(4);
String key="";
boolean loop=true;
Scanner scanner=new Scanner(System.in);
while (loop){
System.out.println("show:表示显示栈");
System.out.println("exit:表示退出程序");
System.out.println("push:表示添加数据");
System.out.println("pop:表示出栈");
key=scanner.next();
switch (key){
case "show":
arrayStatck.list();
break;
case "push":
System.out.println("请输入一个数");
int value =scanner.nextInt();
arrayStatck.push(value);
break;
case "pop":
try {
int res=arrayStatck.pop();
System.out.println("出栈的数据为"+res);
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
case "exit":
scanner.close();
loop=false;
break;
default:
break;
}
System.out.println("程序退出");
}
}
}
//定义一个类，表示栈结构
class ArrayStatck{
private int maxSize;
private int[] statck;
private int top=-1;//栈顶为-1
//构造器
public ArrayStatck(int maxSize){
this.maxSize=maxSize;
statck=new int[maxSize];
}
//栈满
public boolean isFull(){
return top==maxSize-1;
}
//栈空
public boolean isEmpty(){
return top==-1;
}
//入栈
public void push(int value){
//先判断栈是否为满
if(isFull()){
System.out.println("栈满");
return;
}
top++;
statck[top]=value;
}
//出栈
public int pop(){
//判断栈是否为空
if(isEmpty()){
//抛出异常
throw new RuntimeException("没有数据");
}
int value =statck[top];
top--;
return value;
}
//遍历栈，需要从栈顶开始显示数据
public void list(){
if(isEmpty()){
System.out.println("没有数据！！");
}
for(int i=top;i >=0 ; i --){
System.out.printf("statck[%d]=%d\n",i,statck[i]);
}
}
}
运行结果：
show:表示显示栈
exit:表示退出程序
push:表示添加数据
pop:表示出栈
push
请输入一个数
12
程序退出
show:表示显示栈
exit:表示退出程序
push:表示添加数据
pop:表示出栈
show
statck[0]=12
程序退出
show:表示显示栈
exit:表示退出程序
push:表示添加数据
pop:表示出栈
pop
出栈的数据为12
程序退出
show:表示显示栈
exit:表示退出程序
push:表示添加数据
pop:表示出栈
show
没有数据！！
程序退出
show:表示显示栈
exit:表示退出程序
push:表示添加数据
pop:表示出栈
exit
程序退出
Process finished with exit code 0
栈的数组和链表实现：
逻辑分析：
代码分析
package DataStrtureDemo;
import java.util.ArrayList;
import java.util.LinkedList;
/**
* Created with IntelliJ IDEA.
* User: yongping Li
* Date: 2020/11/20
* Time: 9:35
* Description: 堆栈的数组和链表实现
*/
public class LLstatckDemo {
public static void main(String[] args) {
//测试代码
Stack S=new Stack();
S.push(5);
S.push(43);
System.out.println(S.isEmpty());
System.out.println(S.getSize());
System.out.println(S.pop());
LLStack ll=new LLStack();
System.out.println(ll.isEmpty());
ll.push(3);
System.out.println(ll.topEl());
}
}
//堆栈的链表实现
class LLStack{
LinkedList list=new LinkedList();
public LLStack(){
}
public void clear(){
list.clear();
}
public boolean isEmpty(){
return list.isEmpty();
}
public Object topEl(){
if(isEmpty()){
throw new RuntimeException("栈为空");
}
return list.getLast();
}
public Object pop(){
if(isEmpty()){
throw new RuntimeException("栈为空");
}
return list.removeLast();
}
public void push(Object o){
list.addLast(o);
}
public String toString (){
return list.toString();
}
}
//堆栈的数组实现
class Stack{
ArrayList pool=new ArrayList();
public Stack(){
}
public Stack(int n){
pool.ensureCapacity(n);
}
public void clear(){
pool.clear();
}
public boolean isEmpty(){
return pool.isEmpty();
}
public int getSize(){
if(isEmpty()){
throw new RuntimeException("栈为空");
}
return pool.size();
}
public Object pop(){
if(isEmpty()){
throw new RuntimeException("栈为空");
}
return pool.remove(pool.size()-1);
}
public void push(Object o){
pool.add(o);
}
public String toString(){
return pool.toString();
}
}
运行结果为：
（3）利用栈实现综合计算器
逻辑分析：
思路分析：
使用栈完成表达式的计算 思路
1. 通过一个 index 值（索引），来遍历我们的表达式
2. 如果我们发现是一个数字, 就直接入数栈
3. 如果发现扫描到是一个符号, 就分如下情况
3.1 如果发现当前的符号栈为 空，就直接入栈
3.2 如果符号栈有操作符，就进行比较,如果当前的操作符的优先级小于或者等于栈中的操作符， 就需要从数栈中pop出两个数,在从符号栈中pop出一个符号，进行运算，将得到结果，入数栈，然后将当前的操作符入符号栈， 如果当前的操作符的优先级大于栈中的操作符， 就直接入符号栈.
4. 当表达式扫描完毕，就顺序的从 数栈和符号栈中pop出相应的数和符号，并运行. 5. 最后在数栈只有一个数字，就是表达式的结果
代码实现：
package JAVADATASTRTUCRE;
/**
* Created with IntelliJ IDEA.
* User: yongping Li
* Date: 2020/11/20
* Time: 17:34
* Description: 利用堆栈实现综合计算器
*/
public class Calculator {
public static void main(String[] args) {
String expression="73+2*6-2+6/2";
//创建栈
ArrayStatck2 numStack = new ArrayStatck2(10);
ArrayStatck2 operStack = new ArrayStatck2(10);
//定义辅助变量
int index=0;//用于扫描
int num1=0;
int num2=0;
int oper=0;
int res=0;
char ch=' ';
String keepNum="";
//利用while循环扫描experssion
while (true){
//依次得到experssion的每一个字符
ch=expression.substring(index,index+1).charAt(0);
//判断ch是什么，然后处理，数字或符号
if(operStack.isOper(ch)){//是否为运算符
//判断当前符号栈是否为空
if(!operStack.isEmpty()){
//处理
if(operStack.priority(ch)<=operStack.priority(operStack.peak())){
num1=numStack.pop();
num2=numStack.pop();
oper=operStack.pop();
res=numStack.cal(num1,num2,oper);
numStack.push(res);
operStack.push(ch);
}else {
operStack.push(ch);
}
}else{
operStack.push(ch);
}
}else{
// numStack.push(ch-48);//表达式中的数据为'1',需要减去48变成1，详见ascl
//处理多位数
keepNum+=ch;
//如果ch为表达式的最后一位，则直接入栈
if(index==expression.length()-1){
numStack.push(Integer.parseInt(keepNum));
}else {
//判断下一位是否为数字，若为数字，继续扫描，若为
//运算符，入数栈
if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
//如果后一位是操作符，则入栈
numStack.push(Integer.parseInt(keepNum));
//keepNum清空
keepNum = "";
}
}
}
index++;
//判断是否扫描到最后
if(index>=expression.length()){
break;
}
}
//计算结果
while (true){
//如果符号栈为空，则数栈中只有一个结果
if(operStack.isEmpty()){
break;
}
num1=numStack.pop();
num2=numStack.pop();
oper=operStack.pop();
res=numStack.cal(num1,num2,oper);
numStack.push(res);
}
System.out.println("表达式"+expression+"的运行结果为："+numStack.pop());
}
}
//创建一个栈
class ArrayStatck2{
private int maxSize;//栈大小
private int[] statck;
private int top=-1;//栈顶为-1
//构造器
public ArrayStatck2(int maxSize){
this.maxSize=maxSize;
statck=new int[maxSize];
}
//栈满
public boolean isFull(){
return top==maxSize-1;
}
//栈空
public boolean isEmpty(){
return top==-1;
}
//入栈
public void push(int value){
//先判断栈是否为满
if(isFull()){
System.out.println("栈满");
return;
}
top++;
statck[top]=value;
}
//出栈
public int pop(){
//判断栈是否为空
if(isEmpty()){
//抛出异常
throw new RuntimeException("没有数据");
}
int value =statck[top];
top--;
return value;
}
//查看栈顶的值
public int peak(){
return statck[top];
}
//遍历栈，需要从栈顶开始显示数据
public void list(){
if(isEmpty()){
System.out.println("没有数据！！");
}
for(int i=top;i >=0 ; i --){
System.out.printf("statck[%d]=%d\n",i,statck[i]);
}
}
//返回运算符的优先级
//优先级使用数字表示，则优先级越高
public int priority(int oper){
if(oper=='*'||oper=='/'){
return 1;
}else if (oper=='+'||oper=='-'){
return 0;
}else{
return -1;
}
}
//判断是否为运算符
public boolean isOper(char value){
return value=='*'|| value=='+'|| value=='-'||value=='/';
}
//计算方法
public int cal(int num1,int num2,int oper){
int res=0;//存储计算结果
switch (oper){
case '+':
res=num1+num2;
break;
case'-':
res=num2-num1;
break;
case'*':
res=num1*num2;
break;
case '/':
res=num2/num1;
break;
default:
break;
}
return res;
}
}
运行结果为：
计算 73+2*6-2+6/2
（4）前缀中缀后缀表达式的简单介绍
前缀表达式，指的是不包含括号，运算符放在两个运算对象的前面，严格从右向左进行（不再考虑运算符的优先规则），所有的计算按运算符出现的顺序。
例如：(3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6。
前缀表达式的计算机计算：
从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 和 次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果
例如: (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6 , 针对前缀表达式求值步骤如下:
- 从右至左扫描，将6、5、4、3压入堆栈
- 遇到+运算符，因此弹出3和4（3为栈顶元素，4为次顶元素），计算出3+4的值，得7，再将7入栈
- 接下来是×运算符，因此弹出7和5，计算出7×5=35，将35入栈
- 最后是-运算符，计算出35-6的值，即29，由此得出最终结果
中缀表达式：
中缀表达式就是常见的运算表达式，如(3+4)×5-6 中缀表达式的求值是我们人最熟悉的，
但是对计算机来说却不好操作(前面我们讲的案例就能看的这个问题)，因此，在计算结果时，往往会将中缀表达式转成其它表达式来操作(一般转成后缀表达式.)
后缀表达式：
后缀表达式又称逆波兰表达式,与前缀表达式相似，只是运算符位于操作数之后中，指的是不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则）。
举例说明： (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 –
|
正常的表达式
|
逆波兰表达式
|
|
a+b
|
a b +
|
|
a+(b-c)
|
a b c - +
|
|
a+(b-c)*d
|
a b c – d * +
|
|
a+d*(b-c)
|
a d b c - * +
|
|
a=1+3
|
a 1 3 + =
|
后缀表达式的计算机计算：
从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 和 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果
例如: (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 - , 针对后缀表达式求值步骤如下:
- 从左至右扫描，将3和4压入堆栈；
- 遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈；
- 将5入栈； 接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；
- 将6入栈； 最后是-运算符，计算出35-6的值，即29，由此得出最终结果
中缀表达式转化为前缀表达式：
将中缀表达式转换为前缀表达式：
遵循以下步骤：
(1) 初始化两个栈：运算符栈S1和储存中间结果的栈S2；
(2) 从右至左扫描中缀表达式；
(3) 遇到操作数时，将其压入S2；
(4) 遇到运算符时，比较其与S1栈顶运算符的优先级：
(4-1) 如果S1为空，或栈顶运算符为右括号“)”，则直接将此运算符入栈；
(4-2) 否则，若优先级比栈顶运算符的较高或相等，也将运算符压入S1；
(4-3) 否则，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较；
(5) 遇到括号时：
(5-1) 如果是右括号“)”，则直接压入S1；
(5-2) 如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃；
(6) 重复步骤(2)至(5)，直到表达式的最左边；
(7) 将S1中剩余的运算符依次弹出并压入S2；
(8) 依次弹出S2中的元素并输出，结果即为中缀表达式对应的前缀表达式。
例如，将中缀表达式“1+((2+3)×4)-5”转换为前缀表达式的过程如下：
中缀表达式转化为前缀表达式，后缀表达式
（5）中缀表达式转后缀表达式的逻辑分析和代码实现
中缀表达式转后缀表达式的逻辑分析：
1) 初始化两个栈：运算符栈s1和储存中间结果的栈s2；
2) 从左至右扫描中缀表达式；
3) 遇到操作数时，将其压s2；
4) 遇到运算符时，比较其与s1栈顶运算符的优先级：
1.如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
2.否则，若优先级比栈顶运算符的高，也将运算符压入s1；
3.否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4.1)与s1中新的栈顶运算符相比较；
5) 遇到括号时：
(1) 如果是左括号“(”，则直接压入s1 (2) 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
6) 重复步骤2至5，直到表达式的最右边
7) 将s1中剩余的运算符依次弹出并压入s2
8) 依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
举例说明: 将中缀表达 式“1+((2+3)×4)-5”转 换为后缀表达式的过 程如下 因此结果为 "1 2 3 + 4 × + 5 –"
代码实现：
package JAVADATASTRTUCRE;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
* Created with IntelliJ IDEA.
* User: yongping Li
* Date: 2020/11/23
* Time: 16:00
* Description: 中缀转后缀的测试
*/
public class NotationTest {
public static void main(String[] args) {
//中缀表达式转化为后缀表达式
//1+(2+3)*4-5 =>1 2 3 + 4 * + 5 -
String expression="1+(2+3)*4-5";
System.out.println("中缀表达式为"+expression);
List<String> infixExpressionList =toFixExpressionList(expression);
System.out.println("数组中的表达式为"+infixExpressionList);
List<String> parseSufferExpression= parseSuffixExperssionList(infixExpressionList);
System.out.println("后缀表达式为："+parseSufferExpression);
//定义一个逆波兰表达式
// String suffiixExpression = "4 5 * 8 - 60 + 8 2 / +";
//先将"3 4 + 5 * 6 -" 放入ArrayList中，
//将ArrayList 传递一个方法，遍历ArrayList配合栈完成计算
// List<String> s=getListString(suffiixExpression);
//System.out.println(s);
int res=calculate(parseSufferExpression);
System.out.println("输出的结果为"+res);
}
//将波兰表表达式依次将数据保存到数组中
public static List<String> getListString(String suffixExpression){
//j将suffisExression分割
String []split=suffixExpression.split(" ");
List<String> list =new ArrayList<String>();
for(String ele:split){
list.add(ele);
}
return list;
}
//将中缀表达式转化为后缀表达式
//s="1+(2+3)*4-5"
public static List<String> toFixExpressionList(String s){
//定义一个List，存放中缀表达式
List<String> ls=new ArrayList<>();
int i=0;//定义一个指针，用于遍历中缀表达式
String str;//多位数的拼接
char c;
do {
//若c非数字，则放入ls（可能为字符或其他）
//ascll中 数字介于48与57之间
if((c=s.charAt(i))<48||(c=s.charAt(i))<57){
ls.add(""+c);
i++;
}else{//若为数，考虑多位数 0[48] -->9[57]
str="";
while(i<s.length()&&(c=s.charAt(i))>=48&&(c=s.charAt(i))<=57){
str +=c;//拼接
i++;
}
}
}while (i<s.length());
return ls;
}
public static List<String> parseSuffixExperssionList(List<String> ls){
//定义两个栈
Stack<String> s1=new Stack<String>();
List<String> s2=new ArrayList<String>();
//遍历ls
for(String item:ls){
//加入s2
//数字匹配
if(item.matches("\\d+")){
s2.add(item);
}else if(item.equals("(")){
s1.push(item);
}else if(item.equals(")")){
//右括号
while(!s1.peek().equals("(")){
s2.add(s1.pop());
}
s1.pop();//弹出（，消除括号
}else{
while (s1.size()!=0 && Operation.getValue(s1.peek()) >=Operation.getValue(item)){
s2.add(s1.pop());
}
//将item压入栈中
s1.push(item);
}
}
//将S1中的数据加入到是s2中
while (s1.size()!=0){
s2.add(s1.pop());
}
//顺序输出，即为后缀表达式
return s2;
}
//完成逆波兰表达式
public static int calculate(List<String> ls){
Stack<String> statck=new Stack<String>();
//遍历ls
for(String item:ls){
//利用正则表达式取数
if(item.matches("\\d+")){//匹配多位数
//入栈
statck.push(item);
}else{
//pop两个数，并运算，在入栈
int num1=Integer.parseInt(statck.pop());
int num2=Integer.parseInt(statck.pop());
int res=0;
if(item.equals("+")){
res=num1+num2;
}else if(item.equals("-")){//后出栈减去先出栈
res=num2-num1;
}else if(item.equals("*")){
res=num1*num2;
}else if(item.equals("/")){
res=num2/num1;
}else{
throw new RuntimeException("运算符有误");
}
//将res入栈
statck.push(""+res);
}
}
//将栈中的结果返回
return Integer.parseInt(statck.pop());
}
}
//比较有限集
class Operation{
private static int ADD=1;
private static int SUB=1;
private static int MUL=2;
private static int DIV=2;
public static int getValue(String operation){
int result=0;
switch(operation){
case "+":
result=ADD;
break;
case "-":
result=SUB;
break;
case "*":
result=MUL;
break;
case "/":
result=DIV;
break;
default:
System.out.println("运算符不存在");
break;
}
return result;
}
}
运行结果为：
中缀转后缀的另一种实现方式：
package JAVADATASTRTUCRE;
import java.util.Scanner;
/**
* Created with IntelliJ IDEA.
* User: yongping Li
* Date: 2020/11/28
* Time: 20:28
* Description: 中缀表达式转化为后缀表达式
*/
public class testInfixToSuffix {
public static void main(String[] args) {
String input;
System.out.println("Enter infix:");
Scanner scanner = new Scanner(System.in);
input = scanner.nextLine();
InfixToSuffix in = new InfixToSuffix(input);
MyCharStack my = in.doTrans();
my.displayStack();
}
}
class InfixToSuffix {
private MyCharStack s1;//定义运算符栈
private MyCharStack s2;//定义存储结果栈
private String input;
//默认构造方法，参数为输入的中缀表达式
public InfixToSuffix(String in){
input = in;
s1 = new MyCharStack(input.length());
s2 = new MyCharStack(input.length());
}
//中缀表达式转换为后缀表达式，将结果存储在栈中返回，逆序显示即后缀表达式
public MyCharStack doTrans(){
for(int j = 0 ; j < input.length() ; j++){
System.out.print("s1栈元素为：");
s1.displayStack();
System.out.print("s2栈元素为：");
s2.displayStack();
char ch = input.charAt(j);
System.out.println("当前解析的字符:"+ch);
switch (ch) {
case '+':
case '-':
gotOper(ch,1);
break;
case '*':
case '/':
gotOper(ch,2);
break;
case '(':
s1.push(ch);//如果当前字符是'(',则将其入栈
break;
case ')':
gotParen(ch);
break;
default:
//1、如果当前解析的字符是操作数，则直接压入s2
//2、
s2.push(ch);
break;
}//end switch
}//end for
while(!s1.isEmpty()){
s2.push(s1.pop());
}
return s2;
}
public void gotOper(char opThis,int prec1){
while(!s1.isEmpty()){
char opTop = s1.pop();
if(opTop == '('){//如果栈顶是'(',直接将操作符压入s1
s1.push(opTop);
break;
}else{
int prec2;
if(opTop == '+' || opTop == '-'){
prec2 = 1;
}else{
prec2 = 2;
}
if(prec2 < prec1){//如果当前运算符比s1栈顶运算符优先级高，则将运算符压入s1
s1.push(opTop);
break;
}else{//如果当前运算符与栈顶运算符相同或者小于优先级别，那么将S1栈顶的运算符弹出并压入到S2中
//并且要再次再次转到while循环中与 s1 中新的栈顶运算符相比较；
s2.push(opTop);
}
}
}//end while
//如果s1为空，则直接将当前解析的运算符压入s1
s1.push(opThis);
}
//当前字符是 ')' 时，如果栈顶是'(',则将这一对括号丢弃，否则依次弹出s1栈顶的字符，压入s2，直到遇到'('
public void gotParen(char ch){
while(!s1.isEmpty()){
char chx = s1.pop();
if(chx == '('){
break;
}else{
s2.push(chx);
}
}
}
}
//自定义一个栈
class MyCharStack {
private char[] array;
private int maxSize;
private int top;
public MyCharStack(int size){
this.maxSize = size;
array = new char[size];
top = -1;
}
//压入数据
public void push(char value){
if(top < maxSize-1){
array[++top] = value;
}
}
//弹出栈顶数据
public char pop(){
return array[top--];
}
//访问栈顶数据
public char peek(){
return array[top];
}
//查看指定位置的元素
public char peekN(int n){
return array[n];
}
//为了便于后面分解展示栈中的内容，我们增加了一个遍历栈的方法(实际上栈只能访问栈顶元素的)
public void displayStack(){
System.out.print("Stack(bottom-->top):");
for(int i = 0 ; i < top+1; i++){
System.out.print(peekN(i));
System.out.print(' ');
}
System.out.println("");
}
//判断栈是否为空
public boolean isEmpty(){
return (top == -1);
}
//判断栈是否满了
public boolean isFull(){
return (top == maxSize-1);
}
}
运行结果为：
Enter infix:
A*(B+C)-D/(E+F)
s1栈元素为：Stack(bottom-->top):
s2栈元素为：Stack(bottom-->top):
当前解析的字符:A
s1栈元素为：Stack(bottom-->top):
s2栈元素为：Stack(bottom-->top):A
当前解析的字符:*
s1栈元素为：Stack(bottom-->top):*
s2栈元素为：Stack(bottom-->top):A
当前解析的字符:(
s1栈元素为：Stack(bottom-->top):* (
s2栈元素为：Stack(bottom-->top):A
当前解析的字符:B
s1栈元素为：Stack(bottom-->top):* (
s2栈元素为：Stack(bottom-->top):A B
当前解析的字符:+
s1栈元素为：Stack(bottom-->top):* ( +
s2栈元素为：Stack(bottom-->top):A B
当前解析的字符:C
s1栈元素为：Stack(bottom-->top):* ( +
s2栈元素为：Stack(bottom-->top):A B C
当前解析的字符:)
s1栈元素为：Stack(bottom-->top):*
s2栈元素为：Stack(bottom-->top):A B C +
当前解析的字符:-
s1栈元素为：Stack(bottom-->top):-
s2栈元素为：Stack(bottom-->top):A B C + *
当前解析的字符:D
s1栈元素为：Stack(bottom-->top):-
s2栈元素为：Stack(bottom-->top):A B C + * D
当前解析的字符:/
s1栈元素为：Stack(bottom-->top):- /
s2栈元素为：Stack(bottom-->top):A B C + * D
当前解析的字符:(
s1栈元素为：Stack(bottom-->top):- / (
s2栈元素为：Stack(bottom-->top):A B C + * D
当前解析的字符:E
s1栈元素为：Stack(bottom-->top):- / (
s2栈元素为：Stack(bottom-->top):A B C + * D E
当前解析的字符:+
s1栈元素为：Stack(bottom-->top):- / ( +
s2栈元素为：Stack(bottom-->top):A B C + * D E
当前解析的字符:F
s1栈元素为：Stack(bottom-->top):- / ( +
s2栈元素为：Stack(bottom-->top):A B C + * D E F
当前解析的字符:)
Stack(bottom-->top):A B C + * D E F + / -
Process finished with exit code 0
结果分析：
后缀表达式的计算：
代码实现：
package JAVADATASTRTUCRE;
/**
* Created with IntelliJ IDEA.
* User: yongping Li
* Date: 2020/11/28
* Time: 20:44
* Description: 后缀表达式的计算
*/
public class CalSuffix {
private MyIntStack1 stack;
private String input;
public CalSuffix(String input){
this.input = input;
stack = new MyIntStack1(input.length());
}
public int doCalc(){
int num1,num2,result;
for(int i = 0 ; i < input.length() ; i++){
char c = input.charAt(i);
if(c >= '0' && c <= '9'){
stack.push((char) (c-'0'));//如果是数字，直接压入栈中
}else{
num2 = stack.pop();//注意先出来的为第二个操作数
num1 = stack.pop();
switch (c) {
case '+':
result = num1+num2;
break;
case '-':
result = num1-num2;
break;
case '*':
result = num1*num2;
break;
case '/':
result = num1/num2;
break;
default:
result = 0;
break;
}//end switch
stack.push((char) result);
}//end else
}//end for
result = stack.pop();
return result;
}
public static void main(String[] args) {
//中缀表达式：1*(2+3)-5/(2+3) = 4
//后缀表达式：123+*123+/-
CalSuffix cs = new CalSuffix("123+*523+/-");
System.out.println(cs.doCalc()); //4
}
}
//自定义一个栈
class MyIntStack1 {
private char[] array;
private int maxSize;
private int top;
public MyIntStack1(int size){
this.maxSize = size;
array = new char[size];
top = -1;
}
//压入数据
public void push(char value){
if(top < maxSize-1){
array[++top] = value;
}
}
//弹出栈顶数据
public char pop(){
return array[top--];
}
//访问栈顶数据
public char peek(){
return array[top];
}
//查看指定位置的元素
public char peekN(int n){
return array[n];
}
//为了便于后面分解展示栈中的内容，我们增加了一个遍历栈的方法(实际上栈只能访问栈顶元素的)
public void displayStack(){
System.out.print("Stack(bottom-->top):");
for(int i = 0 ; i < top+1; i++){
System.out.print(peekN(i));
System.out.print(' ');
}
System.out.println("");
}
//判断栈是否为空
public boolean isEmpty(){
return (top == -1);
}
//判断栈是否满了
public boolean isFull(){
return (top == maxSize-1);
}
}
运行结果为：
（6）逆波兰计算器的实现
package com.atguigu.stack;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class PolandNotation {
public static void main(String[] args) {
//完成将一个中缀表达式转成后缀表达式的功能
//说明
//1. 1+((2+3)×4)-5 => 转成 1 2 3 + 4 × + 5 –
//2. 因为直接对str 进行操作，不方便，因此 先将 "1+((2+3)×4)-5" =》 中缀的表达式对应的List
// 即 "1+((2+3)×4)-5" => ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]
//3. 将得到的中缀表达式对应的List => 后缀表达式对应的List
// 即 ArrayList [1,+,(,(,2,+,3,),*,4,),-,5] =》 ArrayList [1,2,3,+,4,*,+,5,–]
String expression = "1+((2+3)*4)-5";//注意表达式
List<String> infixExpressionList = toInfixExpressionList(expression);
System.out.println("中缀表达式对应的List=" + infixExpressionList); // ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]
List<String> suffixExpreesionList = parseSuffixExpreesionList(infixExpressionList);
System.out.println("后缀表达式对应的List" + suffixExpreesionList); //ArrayList [1,2,3,+,4,*,+,5,–]
System.out.printf("expression=%d", calculate(suffixExpreesionList)); // ?
/*
//先定义给逆波兰表达式
//(30+4)×5-6 => 30 4 + 5 × 6 - => 164
// 4 * 5 - 8 + 60 + 8 / 2 => 4 5 * 8 - 60 + 8 2 / +
//测试
//说明为了方便，逆波兰表达式 的数字和符号使用空格隔开
//String suffixExpression = "30 4 + 5 * 6 -";
String suffixExpression = "4 5 * 8 - 60 + 8 2 / +"; // 76
//思路
//1. 先将 "3 4 + 5 × 6 - " => 放到ArrayList中
//2. 将 ArrayList 传递给一个方法，遍历 ArrayList 配合栈 完成计算
List<String> list = getListString(suffixExpression);
System.out.println("rpnList=" + list);
int res = calculate(list);
System.out.println("计算的结果是=" + res);
*/
}
//即 ArrayList [1,+,(,(,2,+,3,),*,4,),-,5] =》 ArrayList [1,2,3,+,4,*,+,5,–]
//方法：将得到的中缀表达式对应的List => 后缀表达式对应的List
public static List<String> parseSuffixExpreesionList(List<String> ls) {
//定义两个栈
Stack<String> s1 = new Stack<String>(); // 符号栈
//说明：因为s2 这个栈，在整个转换过程中，没有pop操作，而且后面我们还需要逆序输出
//因此比较麻烦，这里我们就不用 Stack<String> 直接使用 List<String> s2
//Stack<String> s2 = new Stack<String>(); // 储存中间结果的栈s2
List<String> s2 = new ArrayList<String>(); // 储存中间结果的Lists2
//遍历ls
for(String item: ls) {
//如果是一个数，加入s2
if(item.matches("\\d+")) {
s2.add(item);
} else if (item.equals("(")) {
s1.push(item);
} else if (item.equals(")")) {
//如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
while(!s1.peek().equals("(")) {
s2.add(s1.pop());
}
s1.pop();//!!! 将 ( 弹出 s1栈， 消除小括号
} else {
//当item的优先级小于等于s1栈顶运算符, 将s1栈顶的运算符弹出并加入到s2中，再次转到(4.1)与s1中新的栈顶运算符相比较
//问题：我们缺少一个比较优先级高低的方法
while(s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item) ) {
s2.add(s1.pop());
}
//还需要将item压入栈
s1.push(item);
}
}
//将s1中剩余的运算符依次弹出并加入s2
while(s1.size() != 0) {
s2.add(s1.pop());
}
return s2; //注意因为是存放到List, 因此按顺序输出就是对应的后缀表达式对应的List
}
//方法：将 中缀表达式转成对应的List
// s="1+((2+3)×4)-5";
public static List<String> toInfixExpressionList(String s) {
//定义一个List,存放中缀表达式 对应的内容
List<String> ls = new ArrayList<String>();
int i = 0; //这时是一个指针，用于遍历 中缀表达式字符串
String str; // 对多位数的拼接
char c; // 每遍历到一个字符，就放入到c
do {
//如果c是一个非数字，我需要加入到ls
if((c=s.charAt(i)) < 48 || (c=s.charAt(i)) > 57) {
ls.add("" + c);
i++; //i需要后移
} else { //如果是一个数，需要考虑多位数
str = ""; //先将str 置成"" '0'[48]->'9'[57]
while(i < s.length() && (c=s.charAt(i)) >= 48 && (c=s.charAt(i)) <= 57) {
str += c;//拼接
i++;
}
ls.add(str);
}
}while(i < s.length());
return ls;//返回
}
//将一个逆波兰表达式， 依次将数据和运算符 放入到 ArrayList中
public static List<String> getListString(String suffixExpression) {
//将 suffixExpression 分割
String[] split = suffixExpression.split(" ");
List<String> list = new ArrayList<String>();
for(String ele: split) {
list.add(ele);
}
return list;
}
//完成对逆波兰表达式的运算
/*
* 1)从左至右扫描，将3和4压入堆栈；
2)遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈；
3)将5入栈；
4)接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；
5)将6入栈；
6)最后是-运算符，计算出35-6的值，即29，由此得出最终结果
*/
public static int calculate(List<String> ls) {
// 创建给栈, 只需要一个栈即可
Stack<String> stack = new Stack<String>();
// 遍历 ls
for (String item : ls) {
// 这里使用正则表达式来取出数
if (item.matches("\\d+")) { // 匹配的是多位数
// 入栈
stack.push(item);
} else {
// pop出两个数，并运算， 再入栈
int num2 = Integer.parseInt(stack.pop());
int num1 = Integer.parseInt(stack.pop());
int res = 0;
if (item.equals("+")) {
res = num1 + num2;
} else if (item.equals("-")) {
res = num1 - num2;
} else if (item.equals("*")) {
res = num1 * num2;
} else if (item.equals("/")) {
res = num1 / num2;
} else {
throw new RuntimeException("运算符有误");
}
//把res 入栈
stack.push("" + res);
}
}
//最后留在stack中的数据是运算结果
return Integer.parseInt(stack.pop());
}
}
//编写一个类 Operation 可以返回一个运算符 对应的优先级
class Operation {
private static int ADD = 1;
private static int SUB = 1;
private static int MUL = 2;
private static int DIV = 2;
//写一个方法，返回对应的优先级数字
public static int getValue(String operation) {
int result = 0;
switch (operation) {
case "+":
result = ADD;
break;
case "-":
result = SUB;
break;
case "*":
result = MUL;
break;
case "/":
result = DIV;
break;
default:
System.out.println("不存在该运算符" + operation);
break;
}
return result;
}
}
（7）总结
栈是一种简单的数据结构，通过一端口实现入栈和出栈，这样一种先进后出的数据结构可用于数据的逆序打印，可以实现综合计算机。
