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()); } }
二、后缀直接输出
注意后缀表达式时
为了实现多位数运算,连续输入一串数时 ,输入完一个数加空格
如:要计算:"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程序设计有所帮助。