本文实例讲述了java中缀表达式转后缀表达式实现方法。分享给大家供大家参考，具体如下：
本文先给出思路与方法，最后将给出完整代码
算法综述：
一、中缀表达式转后缀表达式：
1.中缀表达式要转后缀表达式，首先需要两个stack（栈），其中一个应用于存放字符，另一个用于存放数字。
2.读到数字直接存入数字栈中，读到字符时，要咸鱼栈内前一元素（字符）进行比较，当当前（要存入的字符）优先级大于迁移字符时才存入，否则（>=）要仿佛将栈内元素弹出，并依次存入数字栈中。
提示：‘（' 的优先级默认比所有字符都小。所有字符都可以存在它后面；同时夜笔所有字符都大，可以存在所有字符后面
3.遇到 ‘）'时将栈内所有字符依次弹出，并存入数字栈中，知道遇到 ‘（' 为止
4.当所有字符、数字访问完毕时，栈内很可能还会有剩余的字符，这是将他们一次弹出，并纯如数字栈中
小技巧：
1.存放‘+'，‘-'时，如果只有当前一个数位空或者‘（' 时才进行存入操作，否则均弹出。
2.存放 ‘*'，‘/' 时，只有当前一个数位 ‘*'，‘/' 时才弹出其他情况下，均存入。
附上代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
/* * 中缀转后缀 */ 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(); } } |
二、后缀表达式计算
后缀表达式计算只遵循一个原则：
首先将表达式存在栈中
遇到符号时弹出两个相应的数字，进行计算后再次 存入栈内
最后栈内身下的唯一一个数，就是所要求的结果
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
/* * 后缀表达式求值 */ 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(); } } |
最后附上完整代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 |
//注：代码中有很多输出 方便读者实时查看运算过程中 各内容 // 这些输出导致篇幅较长 大家看明白后 删去即可 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后为计算结果
|
1 2 3 4 5 6 7 8 9 |
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- "
例：
|
1 2 3 4 5 6 7 8 |
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程序设计有所帮助。
原文链接：https://blog.csdn.net/qq_43377749/article/details/84483862
查看更多关于Java中缀表达式转后缀表达式实现方法详解的详细内容...