欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

java栈实现中缀转后缀并计算后缀表达式

程序员文章站 2022-03-10 19:55:32
...

https://www.bilibili.com/video/av54029771?p=42
java栈实现中缀转后缀并计算后缀表达式

public class PolandNotation {
   public static void main(String[] args) {
      // 完成将一个中缀表达式转成后缀表达式的功能
      // 1. 1+((2+3)*4)-5 => 1 2 3 + 4 * + 5 -
      // 2. 因直接对str进行操作,不方便,所以将中缀表达式转为list进行操作,
      //    即 1+((2+3)*4)-5 => [1,+,(,(,2,+,3,),*,4,),-,5]
      String expression = "1+((2+3)*4)-5";
      List<String> inFixList = toInFixExpressionString(expression);
      System.out.println(inFixList);

      // 3.将中缀表达式list转为后缀表达式的list
      // [1,+,(,(,2,+,3,),*,4,),-,5] ==》 [1,2,3,+,4,*,+,5,-]
      List<String> suffixList = parseSuffixExpressionList(inFixList);
      System.out.println(suffixList);

     
   }

   //将表达式字符串(没有空格)转为list返回,支持()
   public static List<String> toInFixExpressionString(String s){
      List<String> list = new ArrayList<String>();
      int i = 0;//遍历字符串的索引
      StringBuilder str =new StringBuilder();//用于多位数拼接
      char c;//接受每一个扫描的字符

      while (i<s.length()){
         //如果是非数字,则直接加入list
         if((c=s.charAt(i))<48||(c=s.charAt(i))>57){
            list.add(c+"");
            i++;
         }else{
            //如果是数字,进行多位数拼接
            while (i<s.length()&&(c=s.charAt(i))>=48&&(c=s.charAt(i))<=57){
               str.append(c);
               i++;
            }
            list.add(str.toString());
            str.delete(0,str.length());
         }
      }

      return list;

   }


   // 中缀表达式转后缀表达式
   public static List<String> parseSuffixExpressionList(List<String> ls){
      //定义两个栈
      Stack<String> s1 = new Stack<>(); // 符号栈
      List<String> s2 = new ArrayList<>();//存放结果的集合,没有pop操作所以不用栈

      for (String item : ls) {
         if(item.matches("\\d+")){//遇到操作数
            s2.add(item);
         } else if (item.equals("(")) {//遇到(
            s1.add(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());
            }
            s1.push(item);
         }
      }
      while (s1.size() != 0) {
         s2.add(s1.pop());
      }
      return s2;
   }
}

// 返回运算符优先级的类
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;
   }
}

java栈实现中缀转后缀并计算后缀表达式

 // 对逆波兰表达式进行计算
   public static int calculate(List<String> list){
      // 只需要一个栈即可。
      Stack<String> stack = new Stack<>();
      for (String s : list) {
         // 从左到右扫描
         if(s.matches("\\d+")){//使用正则表达式进行判断,用于判断多位数
            stack.push(s);
         }else{
            int num2 = Integer.parseInt(stack.pop());
            int num1 = Integer.parseInt(stack.pop());
            int res = 0;
            if(s.equals("+")){
               res=num1+num2;
            } else if (s.equals("-")) {
               res = num1-num2;
            } else if (s.equals("*")) {
               res = num1*num2;
            } else if (s.equals("/")) {
               res = num1/num2;
            }
            stack.push(res+"");
         }
      }
      return Integer.parseInt(stack.pop());
   }
}
public static void main(String[] args) {
		// 完成将一个中缀表达式转成后缀表达式的功能
		// 1. 1+((2+3)*4)-5 => 1 2 3 + 4 * + 5 -
		// 2. 因直接对str进行操作,不方便,所以将中缀表达式转为list进行操作,
		//    即 1+((2+3)*4)-5 => [1,+,(,(,2,+,3,),*,4,),-,5]
		String expression = "1+((2+3)*4)-5";
		List<String> inFixList = toInFixExpressionString(expression);
		System.out.println(inFixList);

		// 3.将中缀表达式list转为后缀表达式的list
		// [1,+,(,(,2,+,3,),*,4,),-,5] ==》 [1,2,3,+,4,*,+,5,-]
		List<String> suffixList = parseSuffixExpressionList(inFixList);
		System.out.println(suffixList);

		int calculate = calculate(suffixList);
		System.out.println(suffixList+"计算结果为"+calculate);//16
	}
相关标签: 数据结构 java