java實現中綴表達式轉后綴的方法

發布時間：2020-10-14 04:58:25 來源：腳本之家閱讀：143 作者：水中魚之1999 欄目：編程語言

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

算法綜述：

一、中綴表達式轉后綴表達式：

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

java實現中綴表達式轉后綴的方法

二、后綴直接輸出

注意后綴表達式時

為了實現多位數運算，連續輸入一串數時，輸入完一個數加空格

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

輸出結果：

java實現中綴表達式轉后綴的方法

以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持億速云。

向AI問一下細節

中文字幕av专区_日韩电影在线播放_精品国产精品久久一区免费式_av在线免费观看网站

java實現中綴表達式轉后綴的方法

猜你喜歡

中文字幕av专区_日韩电影在线播放_精品国产精品久久一区免费式_av在线免费观看网站

java實現中綴表達式轉后綴的方法

猜你喜歡

最新資訊

相關推薦

相關標簽