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

2024-09-29 05:18:45

本文实例讲述了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());
  }
}

二、后缀直接输出

注意后缀表达式时

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

如：要计算："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数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

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

详解Java包装类及自动装箱拆箱

Java包装类基本类型大小包装器类型 boolean / Boolean char 16bit Boolean byte 8bit Byte short /16bit Short int 32bit Integer long 64bit Long float 32bit Float double 64bit Double void / Void Java 的包装类有两个主要的目的: Java包装类将基本数据类型的值"包装"到对象中,对基本数据类型的操作变为了对对象进行操作,从而使
Java双重检查加锁单例模式的详解

什么是DCL DCL(Double-checked locking)被设计成支持延迟加载,当一个对象直到真正需要时才实例化: class SomeClass { private Resource resource = null; public Resource getResource() { if (resource == null) resource = new Resource(); return resource; } } 为什么需要推迟初始化?可能创建对象是一个昂贵的操作,有时在已知的运
Java ThreadLocal的设计理念与作用

Java中的ThreadLocal类允许我们创建只能被同一个线程读写的变量.因此,如果一段代码含有一个ThreadLocal变量的引用,即使两个线程同时执行这段代码,它们也无法访问到对方的ThreadLocal变量. 如何创建ThreadLocal变量以下代码展示了如何创建一个ThreadLocal变量: private ThreadLocal myThreadLocal = new ThreadLocal(); 我们可以看到,通过这段代码实例化了一个ThreadLocal对象.我们只需要实例
java_IO向文件中写入和读取内容代码实例

使用java中OutStream()向文件中写入内容 package Stream; import java.io.File; import java.io.FileNotFoundException; import java.io.FileOutputStream; import java.io.IOException; import java.io.OutputStream; public class OutStreamDemo01 { public static void main(Str
详解JAVA中的Collection接口和其主要实现的类

Collection是最基本的集合接口,一个Collection代表一组Object,即Collection的元素(Elements).一些Collection允许相同的元素而另一些不行.一些能排序而另一些不行.Java SDK不提供直接继承自Collection的类,Java SDK提供的类都是继承自Collection的"子接口"如List和Set,详细信息可见官方文档http://tool.oschina.net/uploads/apidocs/jdk-zh/java/util/
深入理解Java多线程与并发编程

一.多线程三大特性多线程有三大特性:原子性.可见性.有序性. 原子性 (跟数据库的事务特性中的原子性类似,数据库的原子性体现是dml语句执行后需要进行提交): 理解:即一个操作或多个操作,要么全部执行并且执行的过程中不会被任何因素打断,要么都不执行. 一个很经典的例子就是银行账户转账问题: 比如从账户A向账户B转1000元,那么必然包括2个操作:从账户A减去1000元,往账户B加上1000元.这2个操作必须要具备原子性才能保证不出现一些意外的问题. 我们操作数据也是如此,比如i = i+1:其
浅谈java String不可变的好处

一.java内部String类的实现: java 8: public final class String implements java.io.Serializable, Comparable<String>, CharSequence { /** The value is used for character storage. */ private final char value[]; } java 9 及之后:(使用coder标识了编码) public final class Stri
详解Java中Thread 和Runnable区别

Thread 和Runnable 关系 Thread类是接口Runnable的一个实现类. public class Thread implements Runnable 源码分析 Thread Threa类运行的时候调用start()方法,源代码如下: 调用start()方法,实际运行的是start0方法,方法声明如下: private native void start0() native表明这个方法是个原生函数,即这个函数是用C/C++实现的,被编译成DLL,由Java调用. native
Javascript的this详解

在理解javascript的this之前,首先先了解一下作用域. 作用域分为两种: 1.词法作用域:引擎在当前作用域或者嵌套的子作用域查找具有名称标识符的变量.(引擎如何查找和在哪查找.定义过程发生在代码书写阶段) 2.动态作用域:在运行时被动态确定的作用域. 词法作用域和动态作用域的区别是:词法作用域是在写代码或定义时确定的:动态作用域是在运行时确定的. this的绑定规则 this是在调用时被绑定,取决于函数的调用位置.由此可以知道,一般情况下(非严格模式下),this都会根据函数调用(调用
4位吸血鬼数字的java实现思路与实例讲解

这个问题来源于Java编程思想一书,所谓"吸血鬼数字"就是指位数为偶数的数字,可以由一对数字相乘而得到,而这对数字各包含乘积的一半位数字,其中从偶数位数字中选取的数字可以任意排列.例如: 1260=21*60,1827=21*87,2187=27*81-- 先列出结果: 一共7个: 1260=21*60,1395=15*93,1435=41*35,1530=51*30,1827=87*21,2187=27*81,6880=86*80 第一种思路对所有的4位数进行穷举,假设这个4位数是a

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

相关推荐

随机推荐