Day558.栈 -数据结构和算法Java

栈 一、基本介绍 二、通过数组实现栈结构 1、思路分析图 2、代码实现

public class ArrayStackDemo {
 public static void main(String[] args) {
  ArrayStack arrayStack = ne ArrayStack(3);
  arrayStack.push(1);
  arrayStack.push(2);
  arrayStack.push(3);

  arrayStack.list();
  System.out.println("====");

  arrayStack.pop();
  arrayStack.list();

 }
}

class ArrayStack{
 private int maxSize;//栈大小
 private int[] stack;//数组存放数据
 private int  = -1;//栈顶

 public ArrayStack(int maxSize){
  this.maxSize = maxSize;
  this.stack = ne int[maxSize];
 }

 //判断栈顶，是否栈满
 public boolean isFull(){
  return this. == maxSize-1;
 }

 //判断栈，是否为空
 public boolean isFree(){
  return this. == -1;
 }

 //入栈
 public void push(int value){
  if (isFull()){
   System.out.println("栈满了");
   return;
  }
  ++;
  stack[] = value;
 }

 //出栈
 public int pop(){
  if (isFree()){
   thro ne RuntimeException("栈为空");
  }
  int vale = stack[];
  --;
  return vale;
 }

 //显示栈
 public void list(){
  if (isFree()){
   thro ne RuntimeException("栈为空");
  }
  //反向遍历
  for (int i = ; i >=0; i--) {
   System.out.println(stack[i]);
  }
 }
}

---

三、前缀/中缀/后缀表达式 1、前缀表达式

2、中缀表达式 3、后缀表达式

---

四、栈实现综合计算器（中缀表达式） 1、只能处理单位数的版本

以下的实现方式无法处理多位数的情况

package .achang.stack;


public class Calculator {
 public static void main(String[] args) {
  //表达式
  String expression = "3+26-3";
  //创建两个栈，一个是数栈，一个是表达式栈
  ArrayStack2 numStack = ne ArrayStack2(10);
  ArrayStack2 operStack = ne ArrayStack2(10);
  //定义需要的相关变量
  int index = 0;//用于扫描表达式的索引
  int num1 = 0;
  int num2 = 0;
  int oper = 0;
  int result = 0;
  char ch = ' ';//将每次扫描的得到的char保存到ch中

  hile (true) {
   //依次得到expression中每一个字符
   ch = expression.substring(index, index + 1).charAt(0);
   //判断ch是什么来做相应的处理
   if (operStack.isOper(ch)) {//【如果是运算符】
    //判断符号栈是否为空
    if (operStack.isFree()) {
     operStack.push(ch);
    } else {
     //如果符号栈有操作符，就进行比较，如果当前的操作符的优先级小于或者等于符号栈中的操作符，就需要从数栈中pop两个数，
     //在从符号栈中pop一个符号，进行运算，计算出结果，并将结果push到数栈中，然后把当前的操作符加入到符号栈中
     if (operStack.rank(ch) <= operStack.rank(operStack.peek())) {
      num1 = numStack.pop();
      num2 = numStack.pop();
      oper = operStack.pop();
      result = numStack.calculate(num1, num2, oper);
      numStack.push(result);
      operStack.push(ch);
     } else {
      //如果当前的操作符优先级大于栈中的操作符，就直接入符号栈
      operStack.push(ch);
     }
    }
   } else {//【如果是数字】
    numStack.push(ch - 48);//将ASCII玛的数字转为对应的数值
   }
   //让index+1，并判断是否扫描到expression了
   index++;
   if (index >= expression.length()){
    break;
   }
  }

  //当表达式扫描完毕后，就顺序从数栈和符号栈中pop出相应的数和符号，并运行
  hile (true){
   //如果符号栈为空，则计算结束，数栈中只有一个数字，且是计算的结果
   if (operStack.isFree()){
    break;
   }
   num1 = numStack.pop();
   num2 = numStack.pop();
   oper = operStack.pop();
   result = numStack.calculate(num1, num2, oper);
   numStack.push(result);
  }
  System.out.printf("表达式 %s = %d",expression,numStack.pop());
 }

}

//栈
class ArrayStack2 {
 private int maxSize;//栈大小
 private int[] stack;//数组存放数据
 private int  = -1;//栈顶

 public ArrayStack2(int maxSize) {
  this.maxSize = maxSize;
  this.stack = ne int[maxSize];
 }

 //查看栈顶的元素，但不弹出栈
 public int peek() {
  return stack[];
 }

 //返回运算符优先级,优先级越大，数字越大
 public int rank(int oper) {
  if (oper == '' || oper == '/') {
   return 1;
  } else if (oper == '+' || oper == '-') {
   return 0;
  } else {
   return -1;//目前假定只有 +-/符号
  }
 }

 //判断是否是运算符
 public boolean isOper(char val) {
  return val == '+' || val == '-' || val == '/' || val == '';
 }

 //计算方法
 public int calculate(int num1, int num2, int oper) {
  int result = 0;
  sitch (oper) {
   case '+':
    result = num1 + num2;
    break;
   case '-':
    result = num2 - num1;
    break;
   case '':
    result = num1  num2;
    break;
   case '/':
    result = num2 / num1;
    break;
  }
  return result;
 }

 //判断栈顶，是否栈满
 public boolean isFull() {
  return this. == maxSize - 1;
 }

 //判断栈，是否为空
 public boolean isFree() {
  return this. == -1;
 }

 //入栈
 public void push(int value) {
  if (isFull()) {
   System.out.println("栈满了");
   return;
  }
  ++;
  stack[] = value;
 }

 //出栈
 public int pop() {
  if (isFree()) {
   thro ne RuntimeException("栈为空");
  }
  int vale = stack[];
  --;
  return vale;
 }

 //显示栈
 public void list() {
  if (isFree()) {
   thro ne RuntimeException("栈为空");
  }
  //反向遍历
  for (int i = ; i >= 0; i--) {
   System.out.println(stack[i]);
  }
 }
}

---

2、多位数处理

package .achang.stack;


public class Calculator {
 public static void main(String[] args) {
  //表达式
  String expression = "30+26-3";
  //创建两个栈，一个是数栈，一个是表达式栈
  ArrayStack2 numStack = ne ArrayStack2(10);
  ArrayStack2 operStack = ne ArrayStack2(10);
  //定义需要的相关变量
  int index = 0;//用于扫描表达式的索引
  int num1 = 0;
  int num2 = 0;
  int oper = 0;
  int result = 0;
  char ch = ' ';//将每次扫描的得到的char保存到ch中
  String keepNum = "";//用过拼接多位数

  hile (true) {
   //依次得到expression中每一个字符
   ch = expression.substring(index, index + 1).charAt(0);
   //判断ch是什么来做相应的处理
   if (operStack.isOper(ch)) {//【如果是运算符】
    //判断符号栈是否为空
    if (operStack.isFree()) {
     operStack.push(ch);
    } else {
     //如果符号栈有操作符，就进行比较，如果当前的操作符的优先级小于或者等于符号栈中的操作符，就需要从数栈中pop两个数，
     //在从符号栈中pop一个符号，进行运算，计算出结果，并将结果push到数栈中，然后把当前的操作符加入到符号栈中
     if (operStack.rank(ch) <= operStack.rank(operStack.peek())) {
      num1 = numStack.pop();
      num2 = numStack.pop();
      oper = operStack.pop();
      result = numStack.calculate(num1, num2, oper);
      numStack.push(result);
      operStack.push(ch);
     } else {
      //如果当前的操作符优先级大于栈中的操作符，就直接入符号栈
      operStack.push(ch);
     }
    }
   } else {//【如果是数字】
    //numStack.push(ch - 48);//将ASCII玛的数字转为对应的数值
    keepNum += ch;

    //如果ch已经是expression的一位，则直接入栈
    if (index == expression.length() - 1) {
     numStack.push(Integer.parseInt(keepNum));
    } else {
     //判断下一个字符是不是数字，如果是数字，则继续扫描，如果是运算符，则入数栈
     //往后面看一位，不是index++
     if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
      //如果后一位是运算符，则入栈
      numStack.push(Integer.parseInt(keepNum));
      keepNum = "";//清空
     }
    }
   }
   //让index+1，并判断是否扫描到expression了
   index++;
   if (index >= expression.length()) {
    break;
   }
  }

  //当表达式扫描完毕后，就顺序从数栈和符号栈中pop出相应的数和符号，并运行
  hile (true) {
   //如果符号栈为空，则计算结束，数栈中只有一个数字，且是计算的结果
   if (operStack.isFree()) {
    break;
   }
   num1 = numStack.pop();
   num2 = numStack.pop();
   oper = operStack.pop();
   result = numStack.calculate(num1, num2, oper);
   numStack.push(result);
  }
  System.out.printf("表达式 %s = %d", expression, numStack.pop());
 }

}

//栈
class ArrayStack2 {
 private int maxSize;//栈大小
 private int[] stack;//数组存放数据
 private int  = -1;//栈顶

 public ArrayStack2(int maxSize) {
  this.maxSize = maxSize;
  this.stack = ne int[maxSize];
 }

 //查看栈顶的元素，但不弹出栈
 public int peek() {
  return stack[];
 }

 //返回运算符优先级,优先级越大，数字越大
 public int rank(int oper) {
  if (oper == '' || oper == '/') {
   return 1;
  } else if (oper == '+' || oper == '-') {
   return 0;
  } else {
   return -1;//目前假定只有 +-/符号
  }
 }

 //判断是否是运算符
 public boolean isOper(char val) {
  return val == '+' || val == '-' || val == '/' || val == '';
 }

 //计算方法
 public int calculate(int num1, int num2, int oper) {
  int result = 0;
  sitch (oper) {
   case '+':
    result = num1 + num2;
    break;
   case '-':
    result = num2 - num1;
    break;
   case '':
    result = num1  num2;
    break;
   case '/':
    result = num2 / num1;
    break;
  }
  return result;
 }

 //判断栈顶，是否栈满
 public boolean isFull() {
  return this. == maxSize - 1;
 }

 //判断栈，是否为空
 public boolean isFree() {
  return this. == -1;
 }

 //入栈
 public void push(int value) {
  if (isFull()) {
   System.out.println("栈满了");
   return;
  }
  ++;
  stack[] = value;
 }

 //出栈
 public int pop() {
  if (isFree()) {
   thro ne RuntimeException("栈为空");
  }
  int vale = stack[];
  --;
  return vale;
 }

 //显示栈
 public void list() {
  if (isFree()) {
   thro ne RuntimeException("栈为空");
  }
  //反向遍历
  for (int i = ; i >= 0; i--) {
   System.out.println(stack[i]);
  }
 }
}

---

五、逆波兰计算器（后缀表达式）

package .achang.stack;

import java.util.Arrays;
import java.util.List;
import java.util.Objects;
import java.util.Stack;


public class PolandNotation {
 public static void main(String[] args) {
  //定义一个逆波兰表达式
  //( 3 + 4 )  5 - 6 = 3 4 + 5  6 - 
  String suffixexpression = "3 4 + 5  6 -";
  List strings = toList(suffixexpression);
  System.out.println(calculate(strings));
 }

 //将逆波兰表达式，转成一个ArrayList
 public static List toList(String suffixexpression){
  if (Objects.equals(suffixexpression, "")){
   return null;
  }
  String[] split = suffixexpression.split(" ");
  return Arrays.asList(split);
 }


 //逆波兰表达式的运算
 public static int calculate(List list){
  Stack stack = ne Stack<>();
  for (String item : list) {
   //判断正则表达式取出数
   if (item.matches("\d+")){//匹配多位数
    //入栈
    stack.push(item);
   }else {//运算符
    int num1 = Integer.parseInt(stack.pop());
    int num2 = Integer.parseInt(stack.pop());
    int result = 0;
    sitch (item) {
     case "+":
      result = num1 + num2;
      break;
     case "-":
      result = num2 - num1;
      break;
     case "":
      result = num1  num2;
      break;
     case "/":
      result = num2 / num1;
      break;
     default:
      thro ne RuntimeException("运算符有误");
    }
    stack.push(String.valueOf(result));
   }
  }
  return Integer.parseInt(stack.pop());
 }

}

---

六、中缀表达式—>后缀表达式 1、思路

---

2、代码实现

 public static void main(String[] args) {
  //中缀表达式 ---> 后缀表达式
  // 1 + ( ( 2 + 3 )  4 ) - 5 => 1 2 3 + 4  + 5 -
  String middleexpression = "1 + ( ( 2 + 3 )  4 ) - 5";
  List lastexpressionList = getLastexpressionByMiddleexpression(middleexpression);
  System.out.println(lastexpressionList);

 //根据中缀表达式 ---> 后缀表达式
 private static List getLastexpressionByMiddleexpression(String middleexpression) {
  List middleexpressionList = Arrays.asList(middleexpression.split(" "));
  Stack s1 = ne Stack<>();//符号栈
  ArrayList s2 = ne ArrayList<>();

  for (String item : middleexpressionList) {
   if (item.matches("\d+")){//判断是否为数字
    s2.add(item);
   }else if ("(".equals(item)){
    s1.push(item);
   }else if (")".equals(item)){
    hile (!s1.peek().equals("(")){
     s2.add(s1.pop());
    }
    s1.pop();
   }else{
    //当item的优先级小于等于栈顶运算符，将s1栈顶的运算符弹出压入s2，反复执行
    hile (s1.size() != 0 && getValue(s1.peek()) >= getValue(item)){
     s2.add(s1.pop());
    }
    //将item压入s1栈
    s1.push(item);
   }
  }
  //将s1中剩下的元素加入到s2中
  hile (s1.size()!=0){
   s2.add(s1.pop());
  }
  return s2;
 }

 //获取运算符优先级
 private static int getValue(String item) {
  sitch (item){
   case "+":
    return 1;
   case "-":
    return 1;
   case "":
    return 2;
   case "/":
    return 2;
   default:
    System.out.println("该运算符不存在");
    return 0;
  }
 }