栈（Stack）
* 栈是一个先入后出（FILO-First In Last Out） 的有序列表；
*
栈是限制线性表中元素 的插入 与 删除 只能 在线性表的同一端进行的中特殊线性表。其插入与删除一端，称为栈顶（Top），另一端四固定不动的，称之为栈底（Botton）；
栈的应用场景：
* 子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。
* 处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。
* 表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)。
* 二叉树的遍历。 图形的深度优先(depth一first)搜索法
用数组模拟栈（结构图如下）
1.先入后出的一种有序列表 ：MaxTop (栈的最大容量)、Top(栈顶)
2.入栈
2.1遍历数组到最后一个元素，将其加入数组。（加入前需要判断栈（数组）是否已经满了）
3.出栈
3.1遍历数组到最后一个元素,将其从数组中删除。（删除前需要判断栈（数组）是否为空）
用数组模拟栈代码
import java.util.Arrays;
import java.util.Scanner;
/*
* 用数组模拟栈
* 栈
* 成员属性： Top 初始值为 -1 ； MaxSize：栈的最大容量 ； 数组stack
* 方法：出栈 ，入栈 , 显示栈
* 入栈：放入之前先判断是否栈满
* 出战：出栈之前需要判断栈是否为空
*/
public class ArrayStackDemo {
public static void main(String[] args) {
/*
arrayStack.enter(5);
arrayStack.enter(3);
arrayStack.enter(6);
System.out.println(arrayStack);
arrayStack.show();
System.out.println(arrayStack.out());
*/
//创建一个栈
ArrayStack arrayStack =new ArrayStack(5);
String key = " ";
Scanner scanner = new Scanner(System.in);
boolean loop =true; //用于循环开始于结束的标记
while(loop) {
System.out.println("enter: 入栈");
System.out.println("out : 出栈");
System.out.println("show : 显示栈");
System.out.println("exit :退出系统");
System.out.println("请输出功能选项：");
key = scanner.next();
switch (key) {
case "enter":
System.out.println("请输入入栈内容: ");
Object object1 = scanner.next();
arrayStack.enter(object1);
break;
case "out":
Object object2 = arrayStack.out();
System.out.println("出栈内容： \n" + object2);
break;
case "show":
System.out.println("栈中的内容： ");
arrayStack.show();
break;
case "exit":
System.out.println("退出系统~~~");
scanner.close();
loop = false;
break;
default:
break;
}
}
}
}
class ArrayStack{
int top;
int maxSize;
Object[] stack;
//构造器
public ArrayStack( int maxSize ) {
this.top = -1;
this.maxSize = maxSize;
this.stack = new Object [this.maxSize];
}
@Override
public String toString() {
return "ArrayStack [top=" + top + ", maxSize=" + maxSize + ", stack=" + Arrays.toString(stack) + "]";
}
//入栈
public void enter(Object data ) {
//判断数组是否已经满了
if(top == maxSize-1) { System.out.println("栈满");return;}
//若没有满，让栈顶移动一位（top=top+1），再存放数据 stack[top] = data;
top +=1;
stack[top] = data;
}
//显示栈
public void show() {
for(int i =top ; i >= 0 ;--i) {
System.out.println("stack[%d]".formatted(i) + " = " + stack[i] );
}
}
//出栈
public Object out() {
if(top == -1 ) {System.out.println("栈空");return null;}
Object value = stack[top] ;
stack[top]=null;
top--;
return value;
}
}
运行结果：
栈实现综合计算器：（运算符优先级自行给出）
简化思路: 3+2
6-2 、 30+2
6-2、 7
2
2-5+1-5+3-4
使用栈来完成表达式的计算思路（用两个栈来实现，一个存放数字，一个存放运算符）
*
1.遍历表达式：通过一个index辅助变量
*
2.如果index辅助变量指向是一个数字，就直接放入栈中
*
3.如果index辅助变量指向是一个符号，就要分情况：
*
3.1如果符号栈（operStack）为空，就直接 将其符号 加入 符号栈 中
*
3.2如果符号栈中不为空，就要进行符号优先级比较：
*
3.2.1如果当前的操作符的优先级 比 栈中的 操作符 的优先级 小 或者相等，则需要将数栈出两个数，符号栈也出一个符号，进行运算得到的结果res将其放入 数栈 中，然后将当前的符号 放入 符号栈 中
*
3.2.2如果当前的操作符的优先级 比 栈中的 操作符 的优先级 大，则直接入符号栈。
*
4.当表达式遍历完，就顺序得从 数栈 和符号栈出相应的数 和 符号，进行运算，得到表达式 最后的结果 ，并将其放入 数栈中
问题1：如何判断运算符的优先级。
自定义优先级： 利用数字大小，比较，数字越大，优先级越大。
问题2：由于遍历表达式得到的类型是String ，计算是需要转换类型 考虑到String类 、基本数据类型与包装类的转换问题
基本类数据类型 和 包装类—–>String类：
String str = String.valueof(基本数据类型和包装类);
String类 —-> char[] : str.toChar ;
String 类本事就是由char数构成 String 类只需要某一段字符：str.charAt(index); 或者 str.charAt(index1 ; index2);
String 类 ——–>基本类数据类型 和 包装类:
调用相对的包装类的parseXxx(string) int i2 = Integer.parseInt(str1); System.out.println(i2);
boolean b1 = Boolean.parseBoolean(str3); System.out.println(b1)；
问题3：当出现多位数情况（怎么放入栈）
由于表达式是逐个遍历的，当遍历到数时，循环判断下一个是否也是数字。若是需要将其拼接，再放入数栈。
栈实现综合计算器代码
import java.util.Arrays;
public class Calculator {
public static void main(String[] args) {
String expresion = "100/50+22*300+2*60-200" ;
//String类是一个字符数组 遍历表达式需要辅助变量
int index = 0 ;
char ch; //遍历表达式
int num1 ; //数栈取出的第一个数字
int num2 ; //数栈取出的第二个数字
String res ; //运算结果
char operation;
//遍历出来的字符需要放入两个栈中：数栈（numStack） 、 符号栈（operStack）
ArrayStack2 numStack = new ArrayStack2(10);
ArrayStack2 operStack = new ArrayStack2(10);
String string =""; //用于数字拼接
ch = expresion.charAt(index);
while(index <= expresion.length()-1) {
/*
//System.out.println(index +" " + (expresion.length()-1)) ;
//System.out.println(ch);
//numStack.show();
//operStack.show();
//if (index >= expresion.length()-1) {System.out.println("遍历表达式完毕");break;}
//进行判断是否为数字，或者是否符号
//若是数字，需要对接下来的表达式进行遍历进行判断是否也是数字
*/
if (numStack.isdigit(ch)) {
//先测试相连下一个是否为数字，若是，就继续判断接下来的表达式
while(numStack.isdigit(ch)) {
//若是到了表达式最后就结束循环
string += ch;
//System.out.println("shuzi"+ch);
index +=1;
if(index > expresion.length()-1) {break;}
ch = expresion.charAt(index);
}
numStack.enter(string);
//当拼接完，需要对string 清空，为保证下一个多位数的正确、
string = "";
}else if (operStack.isOper(ch)) {
//判断是否为空栈
if(operStack.top == -1 ) {
operStack.enter(ch);
index +=1;
ch = expresion.charAt(index);
//若不是空栈，需要进行比较运算符优先级大小
}else
if(operStack.priority(ch) <= operStack.priority(operStack.getTop())){
//System.out.println("numStack: " );
//numStack.show();
//若 当前的操作符的优先级 比 栈中的 操作符 的优先级 小 或者相等，需要将数栈出两个数，符号栈也出一个符号，进行运算得到的结果res将其放入 数栈 中，然后将当前的符号 放入 符号栈 中
num1 = Integer.parseInt((String) numStack.out());
num2 = Integer.parseInt((String)numStack.out()); //由于用Object 数组来模拟栈 ，需要类型转换
operation = (char) operStack.out();
//取出两个数，一个符号 进行运行
res =calculation(num1, num2, operation);
//得出结果将其放入数栈 ,再将当前符号放入 符号栈
numStack.enter(res);
operStack.enter(ch);
//遍历表达式的辅助变量后移
index +=1;
ch = expresion.charAt(index);
//若 当前的操作符的优先级 比 栈中的 操作符 的优先级 大，则直接入符号栈。
}
else {
operStack.enter(ch);
//遍历表达式的辅助变量后移
index +=1;
ch = expresion.charAt(index);
}
}
}
/*
* 一开始计算方法：使用int类型 ; 导致了计算结果放入数栈中 含有不同的类型数据，使最后的计算需要进行类型转换
* 类型的转换涉及了 基本数据类型 、包装类 、 String类
* 类型的转换并不是很难（自己的知识不熟悉），困难在于提取出来就需要判断，不知道用什么来保存进行判断，虽然可以直接判断但数据就没有得到保留进行计算
*/
//当表达式遍历完，数栈会还有两个数，符号栈还有一个数，将其取出来运算，再将最终结果放入数栈中
//System.out.println(numStack.out().getClass().toString() );
//if(numStack.out() instanceof String ) {System.out.println("numStack.out().getClass().toString() == \"Interge\"");}
//num1 = Integer.parseInt(( String)numStack.out());
//num2 = numStack.out();
//ch =(char)operStack.out();
//res = calculation(num1, num2, ch );
//numStack.enter(res);
//当遍历完表达式，就需要将数栈与符号栈依次序将其计算出来
numStack.show();
operStack.show();
while(true) {
if(operStack.top == -1) {break;}
num1 =Integer.parseInt((String)numStack.out()) ;
num2 =Integer.parseInt((String)numStack.out()) ;
operation = (char) operStack.out();
res = calculation(num1, num2, operation);
numStack.enter(res);
}
System.out.println("表达式：%s = ".formatted(expresion) + numStack.out());
}
public static String calculation(int num1 , int num2 , char operation) {
switch (operation) {
case '+':
return String.valueOf(num1 + num2);
case '-':
return String.valueOf(num2 - num1);
case '*':
return String.valueOf( num1 * num2);
case '/':
return String.valueOf(num2 / num1) ;
default:
throw new RuntimeException("该符号暂时没有定义算法");
}
}
}
//创建栈类
class ArrayStack2{
int top;
int maxSize;
Object[] stack;
//构造器
public ArrayStack2( int maxSize ) {
this.top = -1;
this.maxSize = maxSize;
this.stack = new Object [this.maxSize];
}
@Override
public String toString() {
return "ArrayStack [top=" + top + ", maxSize=" + maxSize + ", stack=" + Arrays.toString(stack) + "]";
}
//入栈
public void enter(Object data ) {
//判断数组是否已经满了
if(top == maxSize-1) { System.out.println("栈满");return;}
//若没有满，让栈顶移动一位（top=top+1），再存放数据 stack[top] = data;
top +=1;
stack[top] = data;
}
//显示栈
public void show() {
if(top == -1 ) {System.out.println("show栈空");return ;}
for(int i =top ; i >= 0 ;--i) {
System.out.println("stack[%d]".formatted(i) + " = " + stack[i] );
}
}
//出栈
public Object out() {
if(top == -1 ) {System.out.println("out栈空");return null;}
Object value = stack[top] ;
stack[top]=null;
top--;
return value;
}
//获取栈顶，但不是出栈，用于运算符优先级比较
public char getTop() {
return (char)stack[top];
}
//判断是否为运算符 参数待定可能是char类型 也可能是String
public boolean isOper(char ch ) {
return ch == '+' || ch == '-'|| ch == '*'|| ch == '/';
}
//判断是否为数字
public boolean isdigit(char ch ) {
return ch>='0' && ch <= '9';
}
//自定义运算符优先级 ，数越大 优先级越大
public int priority(char ch) {
if(ch =='+' || ch == '-') {
return 0;
}else if(ch == '*' || ch == '/') {
return 1;
}else {
return -1; //表示目前还没有自定义该符号的优先级大小
}
}
}
运行结果：
后缀表达式计算
中缀表达式转换为后缀表达式：
中缀表达式，就是平时看到计算表达式一样。比如 ： 4+5*(5+8)-4/2
后缀表达式：运算符在运算数后面。运算符前面两个数字是该运算符的运算数（本身表达式的数，以及优先级大的没计算出的数）。 比如：4+5*(5+8)-4/2 —-> 4 5 5 8 + * + 4 2 / –
代码具体步骤：
1）初始化两个栈，运算符栈stack1 和 储存后缀表达式的栈stack2；
2）从左向右扫描中缀表达式；
3）遇到数字直接stack2栈；
4）遇到运算符时，比较与stack1栈顶的运算符的优先级
4.1）如果stack1为空，或者遇到栈顶为”（“左括号运算符，就直接入栈stack1栈；
4.2）如果stacj1不为空，则当前的运算符与比较栈顶运算符优先级；
4.2.1）当前的运算符 比 栈顶运算符 的优先级 大 ；则直接入stack1栈；
4.2.2）当前的运算符 比 栈顶运算符 的优先级 小或者相等，则将栈顶的运算符弹出并且将其压入stack2栈中，此时当前运算符与 stack1的新的栈顶运算符进行比较。重复 4.2.1）和4.2.2）步骤；
5) 当遇到括号时：
5.1）如果遇到是”（ “ 左括号时，则直接入stack1栈 ；
5.2）如果遇到是” ）“有口号时，则stack1栈顶依次弹出运算符，并且将其压入stack2栈中，直到 stack1栈顶为” （ “ 左括号，同时将其” （ “ 弹出，但不放入stack2栈（此时就可以去掉括号）
6）重复2）-5）步骤，直到将中缀表达式扫面完
7）最后将stack1栈中的剩下的运算符依次压入stack2栈中；
8）后追表达式为stack2栈的逆序
后缀表达式计算：
1.初始化一个栈；
2.从左向右扫面后缀表达式；
3.遇到数字直接入栈；
4.遇到符号，弹出栈两个数字，进行计算，并将其结果入栈；
5.重复 3 – 4 步骤，直到扫描完后缀表达式，得出后缀表达式的结果；
后缀表达式计算代码
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/*
* 后缀表达式的计算
* 1.中缀表达式转换为后缀表达式
* 2.利用后缀表达式计算结果
*
*/
public class PolanNatation {
public static void main(String[] args) {
//String expression = "4+5*(5+8)-4/2";
//String expression = "(4+5)*(5+8)-4/2";
String expression = "200/4*4+5*(5+8)-4/2";
PolanCaculator polanCaculator = new PolanCaculator(expression);
polanCaculator.nifixTopostfix();
System.out.println(polanCaculator.postfixExpression);
String res = polanCaculator.caculator();
System.out.println("expression : %s =".formatted(expression) + res );
}
}
/*
* 中缀表达式转换为后缀表达式： 4+5*(5+8)-4/2 ----> 4 5 5 8 + * + 4 2 / -
* 中缀表达式 是由 字符换串 来储存
* 后缀表示用ArrayList 来储存，以便添加删除查询
* 转换原则：（符号由栈来保存，后缀表达式由 ArrayLisst）
* 需要遍历中缀表达式，
* 遇到数字直接添到 ArrayList 中保存；
* 遇到字符
* 情况1：栈中为空，或者遇到栈顶为 “（” 左括号时， 就直接入栈；
* 情况2：栈中不为空，当前的字符与栈顶的字符进行比较，情况如下：
* 情况2.1：当前的字符 比 栈顶的字符 的 优先级 大 ， 则直接入栈；
* 情况2.2：当前的字符 比 栈顶的字符 的 优先级 小或者相等，将栈顶的字符弹出，压入 ArrayList 中；再进行与新的栈顶进行比较，重复此步骤，直到 遇到优先级 ；
* 情况3:遇到 括号 时
* 情况3.1:遇到 “（” 左括号，则直接入栈；
* 情况3.2：遇到“）”右括号，次序 将 栈顶弹出，加入到ArrayList,直到栈顶为“（”时，将其弹出，此时不加入ArrayList中；
* 重复以上步骤；直到遍历完中缀表达式；
* 再依次将栈中的字符，依次加入ArrayList;
*/
class PolanCaculator{
String nifixExpression ;
List<String> postfixExpression = new ArrayList<String>();
//开始遍历中缀表达式；需要一个辅助变量
int index;
//需要一个栈来储存字符；
Stack<String> stack = new Stack<>();
Stack<String> caculatorstack = new Stack<>();
//构造器：需要给中缀表达式赋值
public PolanCaculator(String nifixString) {
this.nifixExpression =nifixString;
index = 0 ;
}
//开始遍历中缀表达式转换成后缀表达式
public void nifixTopostfix() {
String digit = ""; //用于数字的拼接
int newindex ; //用于查下一个字符是否还是数字
while (true) {
if (index > nifixExpression.length()-1 ) {
break;
}
// 遍历到最后一个完结束;
// 判断是否为数字或者运算符
/*
* 考虑多位数
*
*/
if (isDigitOper(nifixExpression.charAt(index))) {
newindex = index ;
//由于一个一个遍历，出现多位数被拆开，导致出现后缀表达式出现有误，需要一个循环判断下一个是否还是数字，是的话，将其拼接在一起
while(isDigitOper(nifixExpression.charAt(newindex))) {
digit += nifixExpression.charAt(newindex);
newindex += 1;
if(newindex > (nifixExpression.length()-1)) {break;}
}
postfixExpression.add(digit); // 由于利用charAt来遍历，charAt()返回一个char类型值
//添加完，digit必须要清空
digit="";
// 辅助变量后移
index = newindex;
/*
*没有考虑到多位数
if (isDigitOper(nifixExpression.charAt(index))) {
postfixExpression.add(String.valueOf(nifixExpression.charAt(index)));
index +=1;
*/
} else {
while (true) {
// 1.判断 栈是否为空，或者 栈顶为 “（” 左括号
if (isoperEmpty()) {
stack.add(String.valueOf(nifixExpression.charAt(index)));
index += 1;
break;
} else {
// 2. 栈不为空 ， 栈顶 也不为“（” 左括号 ，则需要进行比较优先级；
// 当 遇到 括号 不需要比较 优先级
// 若是遇到" （ "左括号，将其直接入栈
// 若是遇到" ）"右括号，将栈中在 "("左括号之前的符号此次弹出，并且将加入 ArrayList 中
if(String.valueOf(nifixExpression.charAt(index)).equals(")")) {
while (String.valueOf(nifixExpression.charAt(index)).equals(")")) {
if (stack.peek().equals("(")) {
//System.out.println(stack);
stack.pop();
index += 1;
break;
}else {
//System.out.println("弹出前" + stack);
postfixExpression.add(stack.pop());
///System.out.println("弹出后"+stack);
}
System.out.println(nifixExpression.charAt(index)); //由于在一开始由判断栈顶是否为“（ ” ,所以在这也需要一个循环
}
} else {
if (String.valueOf(nifixExpression.charAt(index)).equals("(")) {
stack.add(String.valueOf(nifixExpression.charAt(index)));
index += 1;
break;
} else if (priority(String.valueOf(nifixExpression.charAt(index))) > priority(stack.peek())) {
// 如果 当前的字符 比 栈顶的字符 优先级 大 ，则直接入栈
stack.add(String.valueOf(nifixExpression.charAt(index)));
index += 1;
break;
} else {
// 否则 当前的字符 比 栈顶的字符 优先级 小或者相等 ，则需要将栈顶弹出，并且将其加入到ArrayList
postfixExpression.add(stack.pop());
}
}
}
}
}
}
// 当遍历完中缀表达式时，需要将栈中的字符依次弹出，并且加入ArrayList中
for (int i = 0; i <= stack.size(); i++) {
postfixExpression.add(stack.pop());
}
}
//计算后缀表达式 :由于postfixExpression是含有多位数，不能使用isDigitOper来判断是否为数字 ，其实是可以的，因为多位数第一位也数字
public String caculator() {
String res = "";
for(String string : postfixExpression ) {
if( isDigitOper(string.charAt(0))) {
//System.out.println(string);
//若是数字，直接入栈
caculatorstack.add(string);
}else {
//System.out.println("zifu"+string);
//若是字符则，将战中的两个数弹出来计算
int num1 = Integer.parseInt( caculatorstack.pop());
int num2 = Integer.parseInt( caculatorstack.pop());
res = calculation(num1, num2, string);
System.out.println("res = " + res );
caculatorstack.add(res);
}
}
return res;
}
//判断是否为数字 ， 或者 运算符
public static boolean isDigitOper(char ch) {
//若是字符则返一个false
if(ch == '+' || ch == '-' || ch == '*' || ch =='/' || ch == '(' || ch == ')') {return false ;}
//若是数字则返回一个true
else if (ch >= '0' && ch <='9') {return true;}
else { throw new RuntimeException("该字符尚未定义参与运算"); }
}
//判断栈是否为空，或者 栈顶是否为"("
public boolean isoperEmpty() {
if(stack.isEmpty() || stack.peek().equals("(")) { return true;}
else {return false;}
}
//比较优先级
//自定义运算符优先级 ，数越大 优先级越大
public int priority(String string ) {
if(string.equals("+") || string.equals("-")) {
return 0;
}else if(string.equals("/") || string.equals("*")) {
return 1;
}else {
return -1; //表示目前还没有自定义该符号的优先级大小
}
}
//计算
public static String calculation(int num1 , int num2 , String operation) {
switch (operation) {
case "+":
return String.valueOf(num1 + num2);
case "-":
return String.valueOf(num2 - num1);
case "*":
return String.valueOf( num1 * num2);
case "/":
return String.valueOf(num2 / num1) ;
default:
throw new RuntimeException("该符号暂时没有定义算法");
}
}
}
运行结果：
