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

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

程序员文章站 2023-12-19 19:16:22
本文实例讲述了java中缀表达式转后缀表达式实现方法。分享给大家供大家参考,具体如下: 本文先给出思路与方法,最后将给出完整代码 项目实战: 算法综述: 一...

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

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

项目实战:


算法综述:

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

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算法相关内容感兴趣的读者可查看本站专题:《java数据结构与算法教程》、《java操作dom节点技巧总结》、《java文件与目录操作技巧汇总》和《java缓存操作技巧汇总

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

上一篇:

下一篇: