Java中缀表达式转后缀表达式实现方法详解

作者:水中鱼之1999 时间:2021-08-25 02:57:20 

本文实例讲述了Java中缀表达式转后缀表达式实现方法。分享给大家供大家参考,具体如下:

本文先给出思路与方法,最后将给出完整代码

项目实战:

https://www.jb51.net/article/158335.htm

算法综述:

一、中缀表达式转后缀表达式:

1.中缀表达式要转后缀表达式,首先需要两个Stack(栈),其中一个应用于存放字符,另一个用于存放数字。

2.读到数字直接存入数字栈中,读到字符时,要咸鱼栈内前一元素(字符)进行比较,当当前(要存入的字符)优先级大于迁移字符时才存入,否则(>=)要仿佛将栈内元素弹出,并依次存入数字栈中。

提示:‘(' 的优先级默认比所有字符都小。所有字符都可以存在它后面;同时夜笔所有字符都大,可以存在所有字符后面

3.遇到 ‘)'时将栈内所有字符依次弹出,并存入数字栈中,知道遇到 ‘(' 为止

4.当所有字符、数字访问完毕时,栈内很可能还会有剩余的字符,这是将他们一次弹出,并纯如数字栈中

小技巧:

1.存放‘+',‘-'时,如果只有当前一个数位空或者‘(' 时才进行存入操作,否则均弹出。

2.存放 ‘*',‘/' 时,只有当前一个数位 ‘*',‘/' 时才弹出其他情况下,均存入。

附上代码:


/*
* 中缀转后缀
*/
public void toPostfix() {
 // TODO Auto-generated method stub
 int sum = 0 ;//用于记入”()“总个数
 int j = 0 ;//用于读到”)“时循环出栈
 String outStack = null;
 charnum.push(null);
 for( int i = 0 ; i < calculateLength ; i ++){
   if ( calculate[i].equals("(")) {
     charnum.push(calculate[i]);
     sum ++ ;
   }else if ( calculate[i].equals(")") ) {
     outStack = charnum.pop();//进入前先出一个
     while ( !outStack.equals("(") ){
       num.push(outStack);
       outStack = charnum.pop();
     }//最后一次outStack正好接到”(“不入栈
     sum ++ ;
   }else if (calculate[i].equals("*")) {
     outStack = charnum.pop();
     charnum.push(outStack);
     while( ( outStack == "*" || outStack == "/" ) && !(outStack == null) ){
       num.push(outStack);
       charnum.pop();//由于前第三行又将outStack存入栈中,座椅此处再次弹出
       outStack = charnum.pop();
       charnum.push(outStack);
     }
     charnum.push("*");
   }else if (calculate[i].equals("/")) {
     outStack = charnum.pop();
     charnum.push(outStack);
     while( ( outStack == "*" || outStack == "/" ) && !(outStack == null) ){
       num.push(outStack);
       charnum.pop();//由于前第三行又将outStack存入栈中,座椅此处再次弹出
       outStack = charnum.pop();
       charnum.push(outStack);
     }
     charnum.push("/");
   }else if (calculate[i].equals("+")) {
     outStack = charnum.pop();
     charnum.push(outStack);
     while( !(outStack=="(") && !(outStack == null) ){
       num.push(outStack);
       charnum.pop();
       outStack = charnum.pop();
       charnum.push(outStack);
     }
     charnum.push("+");
   }else if (calculate[i].equals("-")) {
     outStack = charnum.pop();
     charnum.push(outStack);
     while( !(outStack=="(") && !(outStack == null) ){
       num.push(outStack);
       charnum.pop();
       outStack = charnum.pop();
       charnum.push(outStack);
     }
     charnum.push("-");
   }else {
     num.push(calculate[i]);
   }
 }
 outStack = charnum.pop();
 while ( outStack != null ) {
   num.push(outStack);
   outStack = charnum.pop();
   }
 calculateLength = calculateLength - sum ;
 Stack<String> zanshi = new Stack<>();
 for(int i = 0 ; i < calculateLength ; i ++ ){
   zanshi.push(num.pop());
 }
 CalculateToZero();
 for(int i = 0 ; i < calculateLength ;i ++ ){
   calculate[i] = zanshi.pop();
 }
}

二、后缀表达式计算

后缀表达式计算只遵循一个原则:

首先将表达式存在栈中

遇到符号时弹出两个相应的数字,进行计算后再次 存入栈内

最后栈内身下的唯一一个数,就是所要求的结果


 /*
  * 后缀表达式求值
  */
 public String postfix() {
   int a = 0 , b = 0;//栈中弹出的两数
   int sum ;//求两数运算
   for (int i = 0; i < calculateLength ; i++ ) {
     if (i == 0) {
       num.push(calculate[i]);
     }else if (calculate[i].equals("+") ) {
       b = Integer.parseInt(num.pop());
       a = Integer.parseInt(num.pop());
       sum = a + b ;
       num.push(String.valueOf(sum));
     }else if (calculate[i].equals("-") ) {
       b = Integer.parseInt(num.pop());
       a = Integer.parseInt(num.pop());
       sum = a - b ;
       num.push(String.valueOf(sum));
     }else if (calculate[i].equals("*") ) {
       b = Integer.parseInt(num.pop());
       a = Integer.parseInt(num.pop());
       sum = a * b ;
       num.push(String.valueOf(sum));
     }else if (calculate[i].equals("/") ) {
       b = Integer.parseInt(num.pop());
       a = Integer.parseInt(num.pop());
       sum = a / b ;
       num.push(String.valueOf(sum));
     }else if (calculate[i].equals("%") ) {
       b = Integer.parseInt(num.pop());
       a = Integer.parseInt(num.pop());
       sum = a / b ;
       num.push(String.valueOf(sum));
     }else {
       num.push(calculate[i]);
     }
   }
   return num.pop();
 }
}

最后附上完整代码


//注:代码中有很多输出 方便读者实时查看运算过程中 各内容
// 这些输出导致篇幅较长 大家看明白后 删去即可
public class Calculate {
private Stack<String> num; //后缀用栈 中转后数字栈
private Stack<String> charnum;//中转后字符栈
private String []calculate;//存字符串数组
private int calculateLength;//字符串数组长度
public Calculate() {
 // TODO Auto-generated constructor stub
 num = new Stack<>(); //后缀用栈 中转后数字栈
 charnum = new Stack<>();//中转后字符栈
 calculate = new String[1000];//存字符串数组
 calculateLength = 0 ;//字符串数组长度
}
//转字符串数组
public void toStringArray(String input) {
 boolean pointFalg = false;
 char charArray[] = input.toCharArray();
 double number = 0;//用于导入多位数
 int j = 0 ;//用于计入当前字符串数组的位数
 int sizeOfArray = charArray.length;
 int pointBelow =1
   ;
 for(int i = 0 ; i < sizeOfArray ; i++){
  if(charArray[i] == '('){
   calculate[j++] = "(";
  }else if(charArray[i] == ')'){
   calculate[j++] = ")";
  }else if (charArray[i] == '+') {
   calculate[j++] = "+";
  }else if (charArray[i] == '-') {
   calculate[j++] = "-";
  }else if (charArray[i] == '*') {
   calculate[j++] = "*";
  }else if (charArray[i] == '/') {
   calculate[j++] = "/";
  }else if (charArray[i] == '%') {
   calculate[j++] = "%";
  }else if (charArray[i] == '#') {
   calculate[j++] = "#";
  }else if (charArray[i] == '.') {
   System.out.println("find new . :");
   pointBelow = 1;
//        sizeOfArray -- ;
   pointFalg = true;
  }else {
   String str=String.valueOf(charArray[i]);
   if (pointFalg == false) {
    System.out.println("1:" + number);
    number = number * 10 + Double.parseDouble(str);
   }else {
    System.out.println("2:" + charArray[i]);
    number = number + Double.parseDouble(str) * Math.pow(0.1, pointBelow);
   }
   System.out.println("3:" + number + "i==" + i);
   if( (i + 1) == sizeOfArray ||( charArray[i+1] < '0' || charArray[i+1] > '9' ) && charArray[i+1] != '.'){
    if ( (i + 1) != sizeOfArray && charArray[i+1] == ' ') {
     i++;
    }
    calculate[j++] = String.valueOf(number);
    System.out.println("number:" + number);
    number = 0 ;
    pointFalg = false;
   }
  }
  System.out.println("---z->" + calculate[i]);
 }
 calculateLength = j-- ;//不--会将‘#'存入
}
public void outPutCalculate() {
 for(int i = 0 ; i < calculateLength ; i ++ ){
  System.out.println(calculate[i]);
 }
}
public void CalculateToZero() {
 for(int i = 0 ; i < calculateLength ; i ++ ){
  calculate[i]= calculate[999] ;
 }
}
//中缀转后缀
public void toPostfix() {
 // TODO Auto-generated method stub
 System.out.println("789");
 int sum = 0 ;//用于记入”()“总个数
 int j = 0 ;//用于读到”)“时循环出栈
 String outStack = null;
 charnum.push(null);
 System.out.println(calculateLength);
 for( int i = 0 ; i < calculateLength ; i ++){
  System.out.println(calculate[i]);//-----------------------------
  if ( calculate[i].equals("(")) {
   charnum.push(calculate[i]);
   System.out.println("1-1 charpush " + calculate[i]);//-----------------------------
   sum ++ ;
  }else if ( calculate[i].equals(")") ) {
   System.out.println("2-1 charpush " + calculate[i]);//-----------------------------
   outStack = charnum.pop();//进入前先出一个
   System.out.println("2-1 charpush " + outStack);//-----------------------------
   while ( !outStack.equals("(") ){
    System.out.println("2-2 charpush " + outStack);//-----------------------------
    num.push(outStack);
    outStack = charnum.pop();
   }//最后一次outStack正好接到”(“不入栈
   System.out.println("qiangxing 1 = " + outStack );
//          outStack = charnum.pop();
   System.out.println("qiangxing 2 = " + outStack );
   sum ++ ;
  }else if (calculate[i].equals("*")) {
   outStack = charnum.pop();
   charnum.push(outStack);
   System.out.println("3-2 charpush " + outStack);//-----------------------------
   while( ( outStack == "*" || outStack == "/" || outStack == "%" ) && !(outStack == null) ){
    System.out.println("3-1 charpush " + outStack);//-----------------------------
    num.push(outStack);
    charnum.pop();//由于前第三行又将outStack存入栈中,座椅此处再次弹出
    outStack = charnum.pop();
    charnum.push(outStack);
   }
   System.out.println("3-3 charpush " + outStack);//-----------------------------
   charnum.push("*");
  }else if (calculate[i].equals("%")) {
   outStack = charnum.pop();
   charnum.push(outStack);
   System.out.println("3-2 charpush " + outStack);//-----------------------------
   while( ( outStack == "*" || outStack == "/" || outStack == "%" ) && !(outStack == null) ){
    System.out.println("3-1 charpush " + outStack);//-----------------------------
    num.push(outStack);
    charnum.pop();//由于前第三行又将outStack存入栈中,座椅此处再次弹出
    outStack = charnum.pop();
    charnum.push(outStack);
   }
   System.out.println("3-3 charpush " + outStack);//-----------------------------
   charnum.push("%");
  }else if (calculate[i].equals("/")) {
   System.out.println("5-1-0 charpush " + "1-1-1-1-1-1-1-1");//-----------------------------
   outStack = charnum.pop();
   System.out.println("5-1-1 charpush " + "2-2-2-2-2-2-22-2");//-----------------------------
   charnum.push(outStack);
   System.out.println("4-1 charpush " + outStack);//-----------------------------
   while( ( outStack == "*" || outStack == "/" || outStack == "%") && !(outStack == null) ){
    System.out.println("4-2 charpush " + outStack);//-----------------------------
    num.push(outStack);
    charnum.pop();//由于前第三行又将outStack存入栈中,座椅此处再次弹出
    outStack = charnum.pop();
    charnum.push(outStack);
   }
   System.out.println("4-3 charpush " + outStack);//-----------------------------
   System.out.println("5-1-2 charpush " + outStack);//-----------------------------
   charnum.push("/");
  }else if (calculate[i].equals("+")) {
   outStack = charnum.pop();
   charnum.push(outStack);
   System.out.println("5-1 charpush " + outStack);//-----------------------------
   while( !(outStack=="(") && !(outStack == null) ){
    System.out.println("5-2 charpush " + outStack);//-----------------------------
    num.push(outStack);
    charnum.pop();
    outStack = charnum.pop();
    charnum.push(outStack);
   }
   System.out.println("5-3 charpush " + outStack);//-----------------------------
   charnum.push("+");
  }else if (calculate[i].equals("-")) {
   outStack = charnum.pop();
   charnum.push(outStack);
   System.out.println("6-1 charpush " + outStack);//-----------------------------
   while( !(outStack=="(") && !(outStack == null) ){
    System.out.println("6-2 charpush " + outStack);//-----------------------------
    num.push(outStack);
    charnum.pop();
    outStack = charnum.pop();
    charnum.push(outStack);
   }
   System.out.println("6-3 charpush " + outStack);//-----------------------------
   charnum.push("-");
  }else {
   System.out.println("7-7 " + calculate[i]);
   num.push(calculate[i]);
  }
 }
 System.out.println("匹配结束" + outStack);
 outStack = charnum.pop();
 System.out.println("finish 1 == " + outStack);
 while ( outStack != null ) {
  num.push(outStack);
  outStack = charnum.pop();
  System.out.println("finish 2 == " + outStack);
 }
 calculateLength = calculateLength - sum ;
 System.out.println( "0.0.0.0 charpush " );//-----------------------------
 System.out.println("sum = " + sum + " calculate = " +
   calculateLength + "calculateLength-sum = " + (calculateLength-sum));
 System.out.println("over ~~~~~0 ");
 Stack<String> zanshi = new Stack<>();
//      num.pop();
 for(int i = 0 ; i < calculateLength ; i ++ ){
  zanshi.push(num.pop());
//        System.out.println(num.pop());
 }
 CalculateToZero();
 System.out.println("over ~~~~~1 ");
 for(int i = 0 ; i < calculateLength ;i ++ ){
  calculate[i] = zanshi.pop();
 }
 System.out.println("over ~~~~~2 ");
 for(int i = 0 ; i < calculateLength ;i ++ ){
  System.out.println(calculate[i]);
 }
 System.out.println("over ~~~~~3 ");
//      num.push("#");
}
//后缀计算
public String postfix() {
 BigDecimal a , b ;//栈中弹出的两数
 BigDecimal sum ;//求两数运算
 for (int i = 0; i < calculateLength ; i++ ) {
//        System.out.println("目前符号:" + calculate[i]);
  if (i == 0) {
   num.push(calculate[i]);
  }else if (calculate[i].equals("+") ) {
   b = new BigDecimal(num.pop());
   a = new BigDecimal(num.pop());
   sum = a.add(b) ;
   num.push(String.valueOf(sum));
  }else if (calculate[i].equals("-") ) {
   b = new BigDecimal(num.pop());
   a = new BigDecimal(num.pop());
   sum = a.subtract(b) ;
   num.push(String.valueOf(sum));
  }else if (calculate[i].equals("*") ) {
   b = new BigDecimal(num.pop());
   a = new BigDecimal(num.pop());
   sum = a.multiply(b) ;
   num.push(String.valueOf(sum));
  }else if (calculate[i].equals("/") ) {
   b = new BigDecimal(num.pop());
   a = new BigDecimal(num.pop());
   sum = a.divide(b,10,RoundingMode.HALF_UP) ;
   num.push(String.valueOf(sum));
  }else if (calculate[i].equals("%") ) {
   b = new BigDecimal(num.pop());
   a = new BigDecimal(num.pop());
   sum = a.divideAndRemainder(b)[1] ;
   num.push(String.valueOf(sum));
  }else {
   num.push(calculate[i]);
  }
 }
 return num.pop();
}
}

结果如下:

一、前缀转后缀并输出

其中over前为转化后的后缀表达式

over后为计算结果


public class Main {
 public static void main(String[] args) {
   Calculate text = new Calculate();
   text.toStringArray("1+2*(3-1+2)-3");
   text.outPutCalculate();
   text.toPostfix();
   System.out.println(text.postfix());
 }
}

Java中缀表达式转后缀表达式实现方法详解

二、后缀直接输出

注意后缀表达式时

为了实现多位数运算,连续输入一串数时 ,输入完一个数加空格

如:要计算:"1+2*(3-1+2)-3"  则输入:"1 2 3 1-2+*+3-"

例:


public class Main {
 public static void main(String[] args) {
   Calculate text = new Calculate();
   text.toStringArray("1 2 3 1-2+*+3-");
   text.outPutCalculate();
   System.out.println(text.postfix());
 }
}

输出结果:

Java中缀表达式转后缀表达式实现方法详解

希望本文所述对大家java程序设计有所帮助。

来源:https://blog.csdn.net/qq_43377749/article/details/84483862

标签:Java,中缀表达式,后缀表达式
0
投稿

猜你喜欢

  • Spring与Mybatis基于注解整合Redis的方法

    2022-09-19 09:19:56
  • jvm垃圾回收之GC调优工具分析详解

    2023-08-17 12:40:20
  • java 单例模式的实例详解

    2023-10-08 05:14:08
  • 关于C#中的Invoke示例详解

    2023-06-20 10:17:14
  • Android中使用 AutoCompleteTextView 实现手机号格式化附带清空历史的操作

    2021-07-05 17:08:43
  • flutter使用tauri实现一个一键视频转4K软件

    2022-10-23 05:46:42
  • C语言实现哈夫曼编码

    2022-07-25 07:35:04
  • c#继承与多态使用示例

    2021-11-24 16:48:33
  • Java多线程编程中ThreadLocal类的用法及深入

    2022-03-17 03:21:29
  • Java JNDI案例详解

    2022-06-09 07:56:35
  • C#分屏控件用法实例

    2022-02-04 20:01:57
  • Spring Boot 2.0.0 终于正式发布-重大修订版本

    2021-08-12 08:25:51
  • WPF基于物理像素绘制图形

    2022-01-06 20:25:18
  • Android游戏开发 自定义手势--输入法手势技术

    2021-08-01 07:52:12
  • Spring @value用法示例详解

    2022-09-29 03:03:48
  • java导出大批量(百万以上)数据的excel文件

    2023-11-16 13:13:22
  • Java学习基础之安装JDK/配置JDK环境&IEDA工具安装

    2023-02-09 13:02:40
  • java文件读写工具类分享

    2023-07-30 21:04:19
  • 实例讲解Java的Spring框架中的控制反转和依赖注入

    2023-04-24 17:44:49
  • 一款适用于Android平台的俄罗斯方块

    2023-02-25 02:38:35
  • asp之家 软件编程 m.aspxhome.com