Java中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式實(shí)現(xiàn)方法詳解

更新時間：2019年03月23日 11:09:44 作者：水中魚之1999

這篇文章主要介紹了Java中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式實(shí)現(xiàn)方法,結(jié)合實(shí)例形式分析了Java中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式的相關(guān)算法原理與具體實(shí)現(xiàn)技巧,需要的朋友可以參考下

本文實(shí)例講述了Java中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式實(shí)現(xiàn)方法。分享給大家供大家參考，具體如下：

本文先給出思路與方法，最后將給出完整代碼

項(xiàng)目實(shí)戰(zhàn)：

http://www.dhdzp.com/article/158335.htm

算法綜述：

一、中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式：

1.中綴表達(dá)式要轉(zhuǎn)后綴表達(dá)式，首先需要兩個Stack（棧），其中一個應(yīng)用于存放字符，另一個用于存放數(shù)字。

2.讀到數(shù)字直接存入數(shù)字棧中，讀到字符時，要咸魚棧內(nèi)前一元素（字符）進(jìn)行比較，當(dāng)當(dāng)前（要存入的字符）優(yōu)先級大于遷移字符時才存入，否則（>=）要仿佛將棧內(nèi)元素彈出，并依次存入數(shù)字棧中。

提示：‘（' 的優(yōu)先級默認(rèn)比所有字符都小。所有字符都可以存在它后面；同時夜筆所有字符都大，可以存在所有字符后面

3.遇到 ‘）'時將棧內(nèi)所有字符依次彈出，并存入數(shù)字棧中，知道遇到 ‘（' 為止

4.當(dāng)所有字符、數(shù)字訪問完畢時，棧內(nèi)很可能還會有剩余的字符，這是將他們一次彈出，并純?nèi)鐢?shù)字棧中

小技巧：

1.存放‘+'，‘-'時，如果只有當(dāng)前一個數(shù)位空或者‘（' 時才進(jìn)行存入操作，否則均彈出。

2.存放 ‘*'，‘/' 時，只有當(dāng)前一個數(shù)位 ‘*'，‘/' 時才彈出其他情況下，均存入。

附上代碼：

/*
 * 中綴轉(zhuǎn)后綴
 */
public void toPostfix() {
  // TODO Auto-generated method stub
  int sum = 0 ;//用于記入”（）“總個數(shù)
  int j = 0 ;//用于讀到”）“時循環(huán)出棧
  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();//進(jìn)入前先出一個
      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();
  }
}

二、后綴表達(dá)式計(jì)算

后綴表達(dá)式計(jì)算只遵循一個原則：

首先將表達(dá)式存在棧中

遇到符號時彈出兩個相應(yīng)的數(shù)字，進(jìn)行計(jì)算后再次存入棧內(nèi)

最后棧內(nèi)身下的唯一一個數(shù)，就是所要求的結(jié)果

  /*
   * 后綴表達(dá)式求值
   */
  public String postfix() {
    int a = 0 , b = 0;//棧中彈出的兩數(shù)
    int sum ;//求兩數(shù)運(yùn)算
    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();
  }
}

最后附上完整代碼

//注：代碼中有很多輸出 方便讀者實(shí)時查看運(yùn)算過程中 各內(nèi)容
// 這些輸出導(dǎo)致篇幅較長 大家看明白后 刪去即可
public class Calculate {
 private Stack<String> num; //后綴用棧 中轉(zhuǎn)后數(shù)字棧
 private Stack<String> charnum;//中轉(zhuǎn)后字符棧
 private String []calculate;//存字符串?dāng)?shù)組
 private int calculateLength;//字符串?dāng)?shù)組長度
 public Calculate() {
  // TODO Auto-generated constructor stub
  num = new Stack<>(); //后綴用棧 中轉(zhuǎn)后數(shù)字棧
  charnum = new Stack<>();//中轉(zhuǎn)后字符棧
  calculate = new String[1000];//存字符串?dāng)?shù)組
  calculateLength = 0 ;//字符串?dāng)?shù)組長度
 }
 //轉(zhuǎn)字符串?dāng)?shù)組
 public void toStringArray(String input) {
  boolean pointFalg = false;
  char charArray[] = input.toCharArray();
  double number = 0;//用于導(dǎo)入多位數(shù)
  int j = 0 ;//用于計(jì)入當(dāng)前字符串?dāng)?shù)組的位數(shù)
  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] ;
  }
 }
 //中綴轉(zhuǎn)后綴
 public void toPostfix() {
  // TODO Auto-generated method stub
  System.out.println("789");
  int sum = 0 ;//用于記入”（）“總個數(shù)
  int j = 0 ;//用于讀到”）“時循環(huán)出棧
  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();//進(jìn)入前先出一個
    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("匹配結(jié)束" + 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("#");
 }
 //后綴計(jì)算
 public String postfix() {
  BigDecimal a , b ;//棧中彈出的兩數(shù)
  BigDecimal sum ;//求兩數(shù)運(yùn)算
  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();
 }
}

結(jié)果如下：

一、前綴轉(zhuǎn)后綴并輸出

其中over前為轉(zhuǎn)化后的后綴表達(dá)式

over后為計(jì)算結(jié)果

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());
  }
}

二、后綴直接輸出

注意后綴表達(dá)式時

為了實(shí)現(xiàn)多位數(shù)運(yùn)算，連續(xù)輸入一串?dāng)?shù)時，輸入完一個數(shù)加空格

如：要計(jì)算："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());
  }
}

輸出結(jié)果：