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 text {

 stack<string> num = new stack<>(); //后缀用栈 中转后数字栈

 stack<string> charnum = new stack<>();//中转后字符栈

 string []calculate = new string[1000];//存字符串数组

 int calculatelength = 0 ;//字符串数组长度

 public text() {
 // todo auto-generated constructor stub
 }

 //转字符串数组
 public void tostringarray(string input) {
 char chararray[] = input.tochararray();
 int number = 0;//用于导入多位数
 int j = 0 ;//用于计入当前字符串数组的位数
 system.out.println(chararray.length);
 for(int i = 0 ; i < chararray.length ; 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 {
 string str=string.valueof(chararray[i]);
 number = number * 10 + integer.parseint(str);system.out.println("123");
 if( (i + 1) == chararray.length || chararray[i+1] < '0' || chararray[i+1] > '9'){

 if ( (i + 1) != chararray.length && chararray[i+1] == ' ') {
 system.out.println("456");i++;
 }
 calculate[j++] = string.valueof(number);
 system.out.println(number);
 number = 0 ;
 }
 }

 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 == 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 == 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() {
 int a = 0 , b = 0;//栈中弹出的两数
 int 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 = 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();
 }
}

结果如下：

一、前缀转后缀并输出

其中over前为转化后的后缀表达式

over后为计算结果

public class main {
 public static void main(string[] args) {
 text text = new text();
 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) {
 text text = new text();
 text.tostringarray("1 2 3 1-2+*+3-");
 text.outputcalculate();
 system.out.println(text.postfix());
 }
}

输出结果：

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。

原文链接：https://blog.csdn.net/qq_43377749/article/details/84483862